From bb11d62a5a84877145c0e44cdd936e97d5b600e1 Mon Sep 17 00:00:00 2001
From: Philip Reames <listmail@philipreames.com>
Date: Mon, 31 Aug 2015 18:31:48 +0000
Subject: [LazyValueInfo] Look through Phi nodes when trying to prove a
 predicate

If asked to prove a predicate about a value produced by a PHI node, LazyValueInfo was unable to do so even if the predicate was known to be true for each input to the PHI. This prevented JumpThreading from eliminating a provably redundant branch.

The problematic test case looks something like this:
ListNode *p = ...;
while (p != null) {
  if (!p) return;
  x = g->x; // unrelated
  p = p->next
}

The null check at the top of the loop is redundant since the value of 'p' is null checked on entry to the loop and before executing the backedge. This resulted in us a) executing an extra null check per iteration and b) not being able to LICM unrelated loads after the check since we couldn't prove they would execute or that their dereferenceability wasn't effected by the null check on the first iteration.

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

llvm-svn: 246465
---
 llvm/test/Transforms/JumpThreading/phi-known.ll | 66 +++++++++++++++++++++++++
 1 file changed, 66 insertions(+)
 create mode 100644 llvm/test/Transforms/JumpThreading/phi-known.ll

(limited to 'llvm/test/Transforms/JumpThreading')

diff --git a/llvm/test/Transforms/JumpThreading/phi-known.ll b/llvm/test/Transforms/JumpThreading/phi-known.ll
new file mode 100644
index 00000000000..8eaf57f748a
--- /dev/null
+++ b/llvm/test/Transforms/JumpThreading/phi-known.ll
@@ -0,0 +1,66 @@
+; RUN: opt -S -jump-threading %s | FileCheck %s
+
+; Value of predicate known on all inputs (trivial case)
+; Note: InstCombine/EarlyCSE would also get this case
+define void @test(i8* %p, i8** %addr) {
+; CHECK-LABEL: @test
+entry:
+  %cmp0 = icmp eq i8* %p, null
+  br i1 %cmp0, label %exit, label %loop
+loop:
+; CHECK-LABEL: loop:
+; CHECK-NEXT: phi
+; CHECK-NEXT: br label %loop
+  %p1 = phi i8* [%p, %entry], [%p1, %loop]
+  %cmp1 = icmp eq i8* %p1, null
+  br i1 %cmp1, label %exit, label %loop
+exit:
+  ret void
+}
+
+; Value of predicate known on all inputs (non-trivial)
+define void @test2(i8* %p) {
+; CHECK-LABEL: @test2
+entry:
+  %cmp0 = icmp eq i8* %p, null
+  br i1 %cmp0, label %exit, label %loop
+loop:
+  %p1 = phi i8* [%p, %entry], [%p2, %backedge]
+  %cmp1 = icmp eq i8* %p1, null
+  br i1 %cmp1, label %exit, label %backedge
+backedge:
+; CHECK-LABEL: backedge:
+; CHECK-NEXT: phi
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: load
+; CHECK-NEXT: cmp
+; CHECK-NEXT: br 
+; CHECK-DAG: label %backedge
+  %addr = bitcast i8* %p1 to i8**
+  %p2 = load i8*, i8** %addr
+  %cmp2 = icmp eq i8* %p2, null
+  br i1 %cmp2, label %exit, label %loop
+exit:
+  ret void
+}
+
+; If the inputs don't branch the same way, we can't rewrite
+; Well, we could unroll this loop exactly twice, but that's
+; a different transform.
+define void @test_mixed(i8* %p) {
+; CHECK-LABEL: @test_mixed
+entry:
+  %cmp0 = icmp eq i8* %p, null
+  br i1 %cmp0, label %exit, label %loop
+loop:
+; CHECK-LABEL: loop:
+; CHECK-NEXT: phi
+; CHECK-NEXT: %cmp1 = icmp
+; CHECK-NEXT: br i1 %cmp1
+  %p1 = phi i8* [%p, %entry], [%p1, %loop]
+  %cmp1 = icmp ne i8* %p1, null
+  br i1 %cmp1, label %exit, label %loop
+exit:
+  ret void
+}
+
-- 
cgit v1.2.3