[SimplifyCFG] In sinkLastInstruction correctly set the debug location of the "common" instruction

[rob.lougher]

Summary

Consider the following simple if-then-else:

define i32 @test(i32 %a, i32 %b) !dbg !6 {
entry:
  %tobool = icmp ne i32 %a, 0, !dbg !8
  br i1 %tobool, label %if.then, label %if.else, !dbg !8

if.then:                                          ; preds = %entry
  %call = call i32 @foo(), !dbg !9
  %sub = sub nsw i32 %b, %call, !dbg !10
  br label %if.end, !dbg !11

if.else:                                          ; preds = %entry
  %call1 = call i32 @bar(), !dbg !12
  %sub2 = sub nsw i32 %b, %call1, !dbg !13
  br label %if.end

if.end:                                           ; preds = %if.else, %if.then
  %b.addr.0 = phi i32 [ %sub, %if.then ], [ %sub2, %if.else ]
  ret i32 %b.addr.0, !dbg !14
}

With the source location of the sub instructions described by:

!10 = !DILocation(line: 10, column: 7, scope: !6)
!13 = !DILocation(line: 12, column: 7, scope: !6)

If this is passed to simplify CFG, the two sub instructions will be sunk into the successor block (sinkLastInstruction):

if.end:                                           ; preds = %if.else, %if.then
  %call1.sink = phi i32 [ %call1, %if.else ], [ %call, %if.then ]
  %sub2 = sub nsw i32 %b, %call1.sink, !dbg !11
  ret i32 %sub2, !dbg !12

However, the "common" sub has the debug location of the second instruction:

!11 = !DILocation(line: 12, column: 7, scope: !5)

This is a problem for sample-based PGO as hits on the sub instruction will be counted towards the else-part of the if-then-else even when the if-part was executed (which may lead to incorrect decisions to re-order blocks). It will also affect the optimized debugging experience leading to odd stepping in the debugger.

The problem occurs because sinkLastInstruction arbitrarily selects one of the instructions and moves it to the successor. When it does this it does not update the debug location so it keeps its original location.

This patch fixes the issue by setting the debug location to the result of merging the debug locations of the commoned instructions. This uses the new API discussed in D26256 (which is still under discussion).

Thanks,
Rob.

[dblaikie]

(just out of curiosity/confirmation - I'd like to know that test fails without the check, I'm not 100% confident on my FileCheck emulation in my head to verify that it'll catch the bug)

[jmolloy]

LGTM too, FWIW!

[rob.lougher]

In D27590#617630, @dblaikie wrote:

Thanks for the review!

(just out of curiosity/confirmation - I'd like to know that test fails without the check, I'm not 100% confident on my FileCheck emulation in my head to verify that it'll catch the bug)

$ opt -simplifycfg simplifycfg_sink_last_inst.ll -S -o - | FileCheck simplifycfg_sink_last_inst.ll 
<stdin>:21:39: error: CHECK-NOT: string occurred!
 %sub2 = sub nsw i32 %b, %call1.sink, !dbg !11
                                      ^
simplifycfg_sink_last_inst.ll:28:14: note: CHECK-NOT: pattern specified here
; CHECK-NOT: !dbg
             ^

[rob.lougher]

In D27590#617635, @jmolloy wrote:

LGTM too, FWIW!

Thanks for the review! I can now commit as the dependent change is done.

llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp

 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/NoFolder.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
+#include "llvm/IR/DebugInfo.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
static bool sinkLastInstruction(ArrayRef<BasicBlock*> Blocks) {
   }
 
   // Arbitrarily use I0 as the new "common" instruction; remap its operands
   // and move it to the start of the successor block.
   for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O)
     I0->getOperandUse(O).set(NewOperands[O]);
   I0->moveBefore(&*BBEnd->getFirstInsertionPt());
 
-  // Update metadata and IR flags.
+  // The debug location for the "common" instruction is the merged locations of
+  // all the commoned instructions.  We start with the original location of the
+  // "common" instruction and iteratively merge each location in the loop below.
+  DILocation *Loc = I0->getDebugLoc();
+
+  // Update metadata and IR flags, and merge debug locations.
   for (auto *I : Insts)
     if (I != I0) {
+      Loc = DILocation::getMergedLocation(Loc, I->getDebugLoc());
       combineMetadataForCSE(I0, I);
       I0->andIRFlags(I);
     }
+  I0->setDebugLoc(Loc);
 
   if (!isa<StoreInst>(I0)) {
     // canSinkLastInstruction checked that all instructions were used by
     // one and only one PHI node. Find that now, RAUW it to our common
     // instruction and nuke it.
     assert(I0->hasOneUse());
     auto *PN = cast<PHINode>(*I0->user_begin());
     PN->replaceAllUsesWith(I0);

llvm/trunk/test/DebugInfo/Generic/simplifycfg_sink_last_inst.ll

+; RUN: opt -simplifycfg -S < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Simplify CFG will try to sink the last instruction in a series of basic
+; blocks, creating a "common" instruction in the successor block.  If the
+; debug locations of the commoned instructions have different file/line
+; numbers the debug location of the common instruction should not be set.
+
+; Generated from source:
+
+; extern int foo(void);
+; extern int bar(void);
+; 
+; int test(int a, int b) {
+;   if(a)
+;     b -= foo();
+;   else
+;     b -= bar();
+;   return b;
+; }
+
+; CHECK: define i32 @test
+; CHECK-LABEL: if.end:
+; CHECK: %[[PHI:.*]] = phi i32 [ %call1, %if.else ], [ %call, %if.then ]
+; CHECK: sub nsw i32 %b, %[[PHI]]
+; CHECK-NOT: !dbg
+; CHECK: ret i32
+
+define i32 @test(i32 %a, i32 %b) !dbg !6 {
+entry:
+  %tobool = icmp ne i32 %a, 0, !dbg !8
+  br i1 %tobool, label %if.then, label %if.else, !dbg !8
+
+if.then:                                          ; preds = %entry
+  %call = call i32 @foo(), !dbg !9
+  %sub = sub nsw i32 %b, %call, !dbg !10
+  br label %if.end, !dbg !11
+
+if.else:                                          ; preds = %entry
+  %call1 = call i32 @bar(), !dbg !12
+  %sub2 = sub nsw i32 %b, %call1, !dbg !13
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %b.addr.0 = phi i32 [ %sub, %if.then ], [ %sub2, %if.else ]
+  ret i32 %b.addr.0, !dbg !14
+}
+
+declare i32 @foo()
+declare i32 @bar()
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "", isOptimized: false, runtimeVersion: 0, emissionKind: LineTablesOnly, enums: !2)
+!1 = !DIFile(filename: "test.c", directory: "")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!6 = distinct !DISubprogram(name: "test", scope: !1, file: !1, line: 8, type: !7, isLocal: false, isDefinition: true, scopeLine: 8, flags: DIFlagPrototyped, isOptimized: false, unit: !0, variables: !2)
+!7 = !DISubroutineType(types: !2)
+!8 = !DILocation(line: 9, column: 6, scope: !6)
+!9 = !DILocation(line: 10, column: 10, scope: !6)
+!10 = !DILocation(line: 10, column: 7, scope: !6)
+!11 = !DILocation(line: 10, column: 5, scope: !6)
+!12 = !DILocation(line: 12, column: 10, scope: !6)
+!13 = !DILocation(line: 12, column: 7, scope: !6)
+!14 = !DILocation(line: 13, column: 3, scope: !6)