Reimplement discriminator assignment algorithm.

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.

Reviewers: dblaikie, davidxl, dnovillo

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D14738

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@253594 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Transforms/Utils/AddDiscriminators.cpp b/lib/Transforms/Utils/AddDiscriminators.cpp
index db2bf6a2a9f6ca5d0bd0dd480dd9424660e2b36d..ed9ff5a96c43f27629d1bd5f40a8d8c029eaa57d 100644 (file)
--- a/lib/Transforms/Utils/AddDiscriminators.cpp
+++ b/lib/Transforms/Utils/AddDiscriminators.cpp
@@ -52,7 +52,7 @@
 // http://wiki.dwarfstd.org/index.php?title=Path_Discriminators
 //===----------------------------------------------------------------------===//
 
 // 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/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DIBuilder.h"


@@ -65,6 +65,7 @@
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.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;
 
 
 using namespace llvm;
 


@@ -169,60 +170,44 @@ bool AddDiscriminators::runOnFunction(Function &F) {
   LLVMContext &Ctx = M->getContext();
   DIBuilder Builder(*M, /*AllowUnresolved*/ false);
 
   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.
-  for (BasicBlock &B : F) {
-    TerminatorInst *Last = B.getTerminator();
-    const DILocation *LastDIL = Last->getDebugLoc();
-    if (!LastDIL)
-      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())
-        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());
+  typedef std::pair<StringRef, unsigned> Location;
+  typedef DenseMap<const BasicBlock *, Metadata *> BBScopeMap;
+  typedef DenseMap<Location, BBScopeMap> LocationBBMap;

 
 

-        // 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);
+  LocationBBMap LBM;

 
 

-        // 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;
+  // 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()) {
+      if (isa<DbgInfoIntrinsic>(&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(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");
+      Changed = true;

     }
   }
 
     }
   }
 

diff --git a/test/Transforms/AddDiscriminators/diamond.ll b/test/Transforms/AddDiscriminators/diamond.ll
new file mode 100644 (file)
index 0000000..2ca638a
--- /dev/null
+++ b/test/Transforms/AddDiscriminators/diamond.ll
@@ -0,0 +1,72 @@
+; 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)

diff --git a/test/Transforms/AddDiscriminators/oneline.ll b/test/Transforms/AddDiscriminators/oneline.ll
index 9cb9e1dc61ea9674814ad308956e5ed274d26472..ebee3935dd66bce1d2c1644a3dd8dee034ccf66f 100644 (file)
--- a/test/Transforms/AddDiscriminators/oneline.ll
+++ b/test/Transforms/AddDiscriminators/oneline.ll
@@ -6,8 +6,8 @@
 ; #3 }
 
 ; i == 3:     discriminator 0
 ; #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 {
 ; return 99:  discriminator 3
 
 define i32 @_Z3fooi(i32 %i) #0 !dbg !4 {


@@ -93,10 +93,10 @@ attributes #1 = { nounwind readnone }
 !28 = !DILocation(line: 3, column: 1, scope: !4)
 
 ; CHECK: ![[THEN1]] = !DILocation(line: 2, column: 17, scope: ![[THENBLOCK:[0-9]+]])
 !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: ![[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)
 ; CHECK: ![[COMBINE]] = !DILocation(line: 2, column: 42, scope: ![[COMBINEBLOCK:[0-9]+]])
 ; CHECK: ![[COMBINEBLOCK]] = !DILexicalBlockFile({{.*}} discriminator: 3)