[JumpThreading] Simplify comparisons when simplifying branches

[reames]

Summary

If we have recognized that a conditional is constant at a particular location in the code (while trying to decide if we can simplify a conditional branch), we can eagerly replace that condition with a constant if it's definition is post dominated by the branch in question.

In practice, this ends up being a compile time savings at most. JumpThreading would have visited each using branch anyways. CVP would have visited the cmp itself again. Unless LVI gives up early, we shouldn't gain any addition power by doing this transformation early. What we do gain is simplicity and compile time.

[reames]

ping.

[apilipenko]

LGTM.

[hfinkel]

LGTM too (without the unrelated white-space change).

In the future, please post patches to phabricator with full context, see: http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface

lib/Transforms/Scalar/JumpThreading.cpp

855 ↗

(On Diff #24519)

Unrelated white-space change.

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

if (CondBr && CondConst && CondBr->isConditional() && PI != PE &&
 
         // If we terminated early, then one of the values didn't match.
         if (PI == PE) {
           unsigned ToRemove = Baseline == LazyValueInfo::True ? 1 : 0;
           unsigned ToKeep = Baseline == LazyValueInfo::True ? 0 : 1;
           CondBr->getSuccessor(ToRemove)->removePredecessor(BB, true);
           BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr);
           CondBr->eraseFromParent();
+          if (CondCmp->use_empty())
+            CondCmp->eraseFromParent();
+          else if (CondCmp->getParent() == BB) {
+            // If the fact we just learned is true for all uses of the
+            // condition, replace it with a constant value
+            auto *CI = Baseline == LazyValueInfo::True ?
+              ConstantInt::getTrue(CondCmp->getType()) :
+              ConstantInt::getFalse(CondCmp->getType());
+            CondCmp->replaceAllUsesWith(CI);
+            CondCmp->eraseFromParent();
+          }
           return true;
         }
       }
 
     } else if (CondBr && CondConst && CondBr->isConditional()) {
       // There might be an invariant in the same block with the conditional
       // that can determine the predicate.
 

llvm/trunk/test/Transforms/JumpThreading/thread-cmp.ll

+; RUN: opt -S -jump-threading %s | FileCheck %s
+; When simplify a branch based on LVI predicates, we should replace the 
+; comparison itself with a constant (when possible) in case it's otherwise used.
+
+define i32 @test(i32* %p) {
+; CHECK-LABEL: @test
+; CHECK: icmp eq
+; CHECK-NEXT: br i1 %cmp, label %exit2, label %exit1
+; CHECK-NOT: icmp ne
+entry:
+  %cmp = icmp eq i32* %p, null
+  br i1 %cmp, label %is_null, label %not_null
+is_null:
+  %cmp2 = icmp ne i32* %p, null
+  br i1 %cmp2, label %exit1, label %exit2
+not_null:
+  %cmp3 = icmp ne i32* %p, null
+  br i1 %cmp3, label %exit1, label %exit2
+exit1:
+  ret i32 0
+exit2:
+  ret i32 1
+}
+
+declare void @use(i1)
+
+; It would not be legal to replace %cmp2 (well, in this case it actually is, 
+; but that's a CSE problem, not a LVI/jump threading problem)
+define i32 @test_negative(i32* %p) {
+; CHECK-LABEL: @test
+; CHECK: icmp ne
+; CHECK: icmp eq
+; CHECK-NEXT: br i1 %cmp, label %exit2, label %exit1
+; CHECK-NOT: icmp ne
+entry:
+  %cmp2 = icmp ne i32* %p, null
+  call void @use(i1 %cmp2)
+  %cmp = icmp eq i32* %p, null
+  br i1 %cmp, label %is_null, label %not_null
+is_null:
+  br i1 %cmp2, label %exit1, label %exit2
+not_null:
+  br i1 %cmp2, label %exit1, label %exit2
+exit1:
+  ret i32 0
+exit2:
+  ret i32 1
+}
+
+; In this case, we can remove cmp2 because it's otherwise unused
+define i32 @test2(i32* %p) {
+; CHECK-LABEL: @test
+; CHECK-LABEL: entry:
+; CHECK-NEXT: icmp eq
+; CHECK-NEXT: br i1 %cmp, label %exit2, label %exit1
+; CHECK-NOT: icmp ne
+entry:
+  %cmp2 = icmp ne i32* %p, null
+  %cmp = icmp eq i32* %p, null
+  br i1 %cmp, label %is_null, label %not_null
+is_null:
+  br i1 %cmp2, label %exit1, label %exit2
+not_null:
+  br i1 %cmp2, label %exit1, label %exit2
+exit1:
+  ret i32 0
+exit2:
+  ret i32 1
+}