From 2993617e416c0a3b307441a243e161efc27538da Mon Sep 17 00:00:00 2001
From: Hal Finkel <hfinkel@anl.gov>
Date: Tue, 14 Oct 2014 16:04:49 +0000
Subject: [PATCH] [LVI] Check for @llvm.assume dominating the edge branch

When LazyValueInfo uses @llvm.assume intrinsics to provide edge-value
constraints, we should check for intrinsics that dominate the edge's branch,
not just any potential context instructions. An assumption that dominates the
edge's branch represents a truth on that edge. This is specifically useful, for
example, if multiple predecessors assume a pointer to be nonnull, allowing us
to simplify a later null comparison.

The test case, and an initial patch, were provided by Philip Reames. Thanks!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@219688 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/LazyValueInfo.cpp                |  2 +
 .../JumpThreading/assume-edge-dom.ll          | 39 +++++++++++++++++++
 2 files changed, 41 insertions(+)
 create mode 100644 test/Transforms/JumpThreading/assume-edge-dom.ll

diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp
index 7ee35b212d3..ec2c798e6c6 100644
--- a/lib/Analysis/LazyValueInfo.cpp
+++ b/lib/Analysis/LazyValueInfo.cpp
@@ -954,6 +954,7 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
 
     // Try to intersect ranges of the BB and the constraint on the edge.
     LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
+    mergeAssumeBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator());
     mergeAssumeBlockValueConstantRange(Val, InBlock, CxtI);
     if (!InBlock.isConstantRange())
       return true;
@@ -971,6 +972,7 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
 
   // if we couldn't compute the value on the edge, use the value from the BB
   Result = getBlockValue(Val, BBFrom);
+  mergeAssumeBlockValueConstantRange(Val, Result, BBFrom->getTerminator());
   mergeAssumeBlockValueConstantRange(Val, Result, CxtI);
   return true;
 }
diff --git a/test/Transforms/JumpThreading/assume-edge-dom.ll b/test/Transforms/JumpThreading/assume-edge-dom.ll
new file mode 100644
index 00000000000..f1d0f41e250
--- /dev/null
+++ b/test/Transforms/JumpThreading/assume-edge-dom.ll
@@ -0,0 +1,39 @@
+; RUN: opt -S -jump-threading < %s | FileCheck %s
+
+declare i8* @escape()
+declare void @llvm.assume(i1)
+
+define i1 @test1(i1 %cond) {
+entry:
+    br i1 %cond, label %taken, label %not_taken
+
+; CHECK-LABEL: @test1
+; CHECK: br i1 %cond, label %no, label %yes
+; CHECK: ret i1 true
+
+taken:
+    %res1 = call i8* @escape()
+    %a = icmp eq i8* %res1, null
+    tail call void @llvm.assume(i1 %a)
+    br label %done
+not_taken:
+    %res2 = call i8* @escape()
+    %b = icmp ne i8* %res2, null
+    tail call void @llvm.assume(i1 %b)
+    br label %done
+
+; An assume that can be used to simplify this comparison dominates each
+; predecessor branch (although no assume dominates the cmp itself). Make sure
+; this still can be simplified.
+
+done:
+    %res = phi i8* [ %res1, %taken ], [ %res2, %not_taken ]
+    %cnd = icmp ne i8* %res, null
+    br i1 %cnd, label %yes, label %no
+
+yes:
+    ret i1 true
+no:
+    ret i1 false
+}
+
-- 
2.34.1