[JumpThreading] Retain debug info when replacing branch instructions

[StephenTozer]

Summary

Fixes bug 37966: https://bugs.llvm.org/show_bug.cgi?id=37966

The Jump Threading pass will replace certain conditional branch
instructions with unconditional branches when it can prove that only one
branch can occur. Prior to this patch, it would not carry the debug
info from the old instruction to the new one.

This patch fixes the bug described by copying the debug info from the
conditional branch instruction to the new unconditional branch
instruction, and adds a regression test for the Jump Threading pass that
covers this case.

[brzycki]

LGTM. It's a simple and clean change.

[dblaikie]

The code change touches two places, but the test only seems to test one branch instruction - is one of the two code changes untested?

[StephenTozer]

In D58963#1419867, @dblaikie wrote:

The code change touches two places, but the test only seems to test one branch instruction - is one of the two code changes untested?

Yes; the second case seemed like it would need an additional, more complicated IR case to test, but the logic for performing the conditional-to-unconditional branch conversion is identical in both cases (could be extracted to a utility function perhaps?) and the semantic meaning is the same as well: "The condition at this state is guaranteed to be true/false, so remove the condition check".

[brzycki]

In D58963#1421264, @StephenTozer wrote:

In D58963#1419867, @dblaikie wrote:

The code change touches two places, but the test only seems to test one branch instruction - is one of the two code changes untested?

Yes; the second case seemed like it would need an additional, more complicated IR case to test, but the logic for performing the conditional-to-unconditional branch conversion is identical in both cases (could be extracted to a utility function perhaps?) and the semantic meaning is the same as well: "The condition at this state is guaranteed to be true/false, so remove the condition check".

Hi @StephenTozer,
I agree with @dblaikie it would be good to have a test-case for both locations. I do understand the logic is the same in both but the general rule is to add test-cases for all code path coverage in changed code. I added an assert() to your patch in the following location:

@@ -1245,7 +1247,9 @@ bool JumpThreadingPass::ProcessImpliedCondition(BasicBlock *BB) {
       BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);
       BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
       RemoveSucc->removePredecessor(BB);
-      BranchInst::Create(KeepSucc, BI);
+      BranchInst *UncondBI = BranchInst::Create(KeepSucc, BI);
+      UncondBI->setDebugLoc(BI->getDebugLoc());
+      assert(0 && "BMR");
       BI->eraseFromParent();
       DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, RemoveSucc}});
       return true;

and ran make check on the code. I found an implied condition test-case that is pretty short exercising this code path. Do you know how to add debug info to the IR to check the before and after states? Here's the test:

; RUN: opt -jump-threading -S < %s | FileCheck %s

declare void @side_effect(i32)

define void @test0(i32 %i, i32 %len) {
; CHECK-LABEL: @test0(
 entry:
  call void @side_effect(i32 0)
  %i.inc = add nuw i32 %i, 1
  %c0 = icmp ult i32 %i.inc, %len
  br i1 %c0, label %left, label %right

 left:
; CHECK: entry:
; CHECK: br i1 %c0, label %left0, label %right

; CHECK: left0:
; CHECK: call void @side_effect
; CHECK-NOT: br i1 %c1
; CHECK: call void @side_effect
  call void @side_effect(i32 0)
  %c1 = icmp ult i32 %i, %len
  br i1 %c1, label %left0, label %right

 left0:
  call void @side_effect(i32 0)
  ret void

 right:
  %t = phi i32 [ 1, %left ], [ 2, %entry ]
  call void @side_effect(i32 %t)
  ret void
}

[StephenTozer]

Added the test case for the second change, and reduced both it and the original test case as much as possible.

[brzycki]

Thank you @StephenTozer , LGTM.

[vsk]

Thanks, lgtm as well.

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

if (CondBr && CondConst) {
       LazyValueInfo::Tristate Ret =
         LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),
                             CondConst, CondBr);
       if (Ret != LazyValueInfo::Unknown) {
         unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0;
         unsigned ToKeep = Ret == LazyValueInfo::True ? 0 : 1;
         BasicBlock *ToRemoveSucc = CondBr->getSuccessor(ToRemove);
         ToRemoveSucc->removePredecessor(BB, true);
+        BranchInst *UncondBr =
           BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr);
+        UncondBr->setDebugLoc(CondBr->getDebugLoc());
         CondBr->eraseFromParent();
         if (CondCmp->use_empty())
           CondCmp->eraseFromParent();
         // We can safely replace *some* uses of the CondInst if it has
         // exactly one value as returned by LVI. RAUW is incorrect in the
         // presence of guards and assumes, that have the `Cond` as the use. This
         // is because we use the guards/assume to reason about the `Cond` value
         // at the end of block, but RAUW unconditionally replaces all uses
while (CurrentPred && Iter++ < ImplicationSearchThreshold) {
 
     bool CondIsTrue = PBI->getSuccessor(0) == CurrentBB;
     Optional<bool> Implication =
         isImpliedCondition(PBI->getCondition(), Cond, DL, CondIsTrue);
     if (Implication) {
       BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);
       BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
       RemoveSucc->removePredecessor(BB);
-      BranchInst::Create(KeepSucc, BI);
+      BranchInst *UncondBI = BranchInst::Create(KeepSucc, BI);
+      UncondBI->setDebugLoc(BI->getDebugLoc());
       BI->eraseFromParent();
       DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, RemoveSucc}});
       return true;
     }
     CurrentBB = CurrentPred;
     CurrentPred = CurrentBB->getSinglePredecessor();
   }
 

llvm/trunk/test/Transforms/JumpThreading/branch-debug-info.ll

+; RUN: opt %s -debugify -jump-threading -S | FileCheck %s
+; Tests Bug 37966
+
+define void @test0(i32 %i) {
+; CHECK-LABEL: @test0(
+; CHECK: left:
+; CHECK: br label %left, !dbg ![[DBG0:[0-9]+]]
+ entry:
+  %c0 = icmp ult i32 %i, 5
+  br i1 %c0, label %left, label %right
+
+ left:
+  br i1 %c0, label %left, label %right
+
+ right:
+  ret void
+}
+
+define void @test1(i32 %i, i32 %len) {
+; CHECK-LABEL: @test1(
+; CHECK: left:
+; CHECK: br label %right, !dbg ![[DBG1:[0-9]+]]
+ entry:
+  %i.inc = add nuw i32 %i, 1
+  %c0 = icmp ult i32 %i.inc, %len
+  br i1 %c0, label %left, label %right
+
+ left:
+  %c1 = icmp ult i32 %i, %len
+  br i1 %c1, label %right, label %left0
+
+ left0:
+  ret void
+
+ right:
+  ret void
+}
+
+; CHECK-DAG: ![[DBG0]] = !DILocation(
+; CHECK-DAG: ![[DBG1]] = !DILocation(
+