From 1505fa4376fb5c97625efa36d83beca49b864b2d Mon Sep 17 00:00:00 2001
From: Jiangning Liu <jiangning.liu@arm.com>
Date: Mon, 11 Aug 2014 05:02:04 +0000
Subject: [PATCH] In LVI(Lazy Value Info), originally value on a BB can only be
 caculated once, and the lattice will be updated to be a state other than
 "undefined". This limiation could miss some opportunities of lowering
 "overdefined" to be an even accurate value. So this patch ask the algorithm
 to try to lower the lattice value again even if the value has been lowered to
 be "overdefined".

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@215343 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/LazyValueInfo.cpp                  | 19 ++++++++++++--
 test/Transforms/JumpThreading/jump_threading.ll | 33 +++++++++++++++++++++++++
 2 files changed, 50 insertions(+), 2 deletions(-)
 create mode 100644 test/Transforms/JumpThreading/jump_threading.ll

diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp
index 9f919f7644a..281ff89bfe4 100644
--- a/lib/Analysis/LazyValueInfo.cpp
+++ b/lib/Analysis/LazyValueInfo.cpp
@@ -500,8 +500,23 @@ bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
   // cache needs updating, i.e. if we have solve a new value or not.
   OverDefinedCacheUpdater ODCacheUpdater(Val, BB, BBLV, this);
 
-  // If we've already computed this block's value, return it.
-  if (!BBLV.isUndefined()) {
+  // Once this BB is encountered, Val's value for this BB will not be Undefined
+  // any longer. When we encounter this BB again, if Val's value is Overdefined,
+  // we need to compute its value again.
+  // 
+  // For example, considering this control flow,
+  //   BB1->BB2, BB1->BB3, BB2->BB3, BB2->BB4
+  //
+  // Suppose we have "icmp slt %v, 0" in BB1, and "icmp sgt %v, 0" in BB3. At
+  // the very beginning, when analyzing edge BB2->BB3, we don't know %v's value
+  // in BB2, and the data flow algorithm tries to compute BB2's predecessors, so
+  // then we know %v has negative value on edge BB1->BB2. And then we return to
+  // check BB2 again, and at this moment BB2 has Overdefined value for %v in
+  // BB2. So we should have to follow data flow propagation algorithm to get the
+  // value on edge BB1->BB2 propagated to BB2, and finally %v on BB2 has a
+  // constant range describing a negative value.
+
+  if (!BBLV.isUndefined() && !BBLV.isOverdefined()) {
     DEBUG(dbgs() << "  reuse BB '" << BB->getName() << "' val=" << BBLV <<'\n');
     
     // Since we're reusing a cached value here, we don't need to update the 
diff --git a/test/Transforms/JumpThreading/jump_threading.ll b/test/Transforms/JumpThreading/jump_threading.ll
new file mode 100644
index 00000000000..f5a0ead3d90
--- /dev/null
+++ b/test/Transforms/JumpThreading/jump_threading.ll
@@ -0,0 +1,33 @@
+; RUN: opt < %s -jump-threading -S | FileCheck %s
+
+define i32 @test_jump_threading(i32* %arg1, i32 %arg2) {
+entry:
+  %cmp = icmp slt i32 %arg2, 0
+  br i1 %cmp, label %land.lhs.true, label %lor.rhs
+
+land.lhs.true:
+  %ident = getelementptr inbounds i32 * %arg1, i64 0
+  %0 = load i32* %ident, align 4
+  %cmp1 = icmp eq i32 %0, 1
+  br i1 %cmp1, label %lor.end, label %lor.rhs
+
+; CHECK: br i1 %cmp1, label %lor.end, label %lor.rhs.thread
+
+; CHECK: lor.rhs.thread:
+; CHECK-NEXT: br label %lor.end
+
+lor.rhs:
+  %cmp2 = icmp sgt i32 %arg2, 0
+  br i1 %cmp2, label %land.rhs, label %lor.end
+
+land.rhs:
+  %ident3 = getelementptr inbounds i32 * %arg1, i64 0
+  %1 = load i32* %ident3, align 4
+  %cmp4 = icmp eq i32 %1, 2
+  br label %lor.end
+
+lor.end:
+  %2 = phi i1 [ true, %land.lhs.true ], [ false, %lor.rhs ], [ %cmp4, %land.rhs ]
+  %lor.ext = zext i1 %2 to i32
+  ret i32 %lor.ext
+}
-- 
2.11.0