From c0bdb0c1e559efc26e57089d6bb21ef642d6b4ae Mon Sep 17 00:00:00 2001
From: Philip Reames <listmail@philipreames.com>
Date: Mon, 1 Feb 2016 22:57:53 +0000
Subject: [PATCH] [LVI] Add select handling

Teach LVI to handle select instructions in the exact same way it handles PHI nodes.  This is useful since various parts of the optimizer convert PHI nodes into selects and we don't want these transformations to cause inferior optimization.

Note that this patch does nothing to exploit the implied constraint on the inputs represented by the select condition itself.  That will be a later patch and is blocked on http://reviews.llvm.org/D14476

llvm-svn: 259429
---
 llvm/lib/Analysis/LazyValueInfo.cpp                | 49 +++++++++++++++
 .../CorrelatedValuePropagation/select.ll           | 69 ++++++++++++++++++++++
 2 files changed, 118 insertions(+)

diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp
index 0d1d34e..cdeaaa3 100644
--- a/llvm/lib/Analysis/LazyValueInfo.cpp
+++ b/llvm/lib/Analysis/LazyValueInfo.cpp
@@ -389,6 +389,8 @@ namespace {
                                  Value *Val, BasicBlock *BB);
     bool solveBlockValuePHINode(LVILatticeVal &BBLV,
                                 PHINode *PN, BasicBlock *BB);
+    bool solveBlockValueSelect(LVILatticeVal &BBLV,
+                               SelectInst *S, BasicBlock *BB);
     bool solveBlockValueConstantRange(LVILatticeVal &BBLV,
                                       Instruction *BBI, BasicBlock *BB);
     void mergeAssumeBlockValueConstantRange(Value *Val, LVILatticeVal &BBLV,
@@ -587,6 +589,13 @@ bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
     return true;
   }
 
+  if (auto *SI = dyn_cast<SelectInst>(BBI)) {
+    if (!solveBlockValueSelect(Res, SI, BB))
+      return false;
+    insertResult(Val, BB, Res);
+    return true;
+  }
+
   // If this value is a nonnull pointer, record it's range and bailout.
   PointerType *PT = dyn_cast<PointerType>(BBI->getType());
   if (PT && isKnownNonNull(BBI)) {
@@ -809,6 +818,46 @@ void LazyValueInfoCache::mergeAssumeBlockValueConstantRange(Value *Val,
   }
 }
 
+bool LazyValueInfoCache::solveBlockValueSelect(LVILatticeVal &BBLV,
+                                               SelectInst *SI, BasicBlock *BB) {
+
+  // Recurse on our inputs if needed
+  if (!hasBlockValue(SI->getTrueValue(), BB)) {
+    if (pushBlockValue(std::make_pair(BB, SI->getTrueValue())))
+      return false;
+    BBLV.markOverdefined();
+    return true;
+  }
+  LVILatticeVal TrueVal = getBlockValue(SI->getTrueValue(), BB);
+  // If we hit overdefined, don't ask more queries.  We want to avoid poisoning
+  // extra slots in the table if we can.
+  if (TrueVal.isOverdefined()) {
+    BBLV.markOverdefined();
+    return true;
+  }
+
+  if (!hasBlockValue(SI->getFalseValue(), BB)) {
+    if (pushBlockValue(std::make_pair(BB, SI->getFalseValue())))
+      return false;
+    BBLV.markOverdefined();
+    return true;
+  }
+  LVILatticeVal FalseVal = getBlockValue(SI->getFalseValue(), BB);
+  // If we hit overdefined, don't ask more queries.  We want to avoid poisoning
+  // extra slots in the table if we can.
+  if (FalseVal.isOverdefined()) {
+    BBLV.markOverdefined();
+    return true;
+  }
+
+  LVILatticeVal Result;  // Start Undefined.
+  Result.mergeIn(TrueVal, DL);
+  Result.mergeIn(FalseVal, DL);
+  assert(!Result.isOverdefined() && "Should have exited previously");
+  BBLV = Result;
+  return true;
+}
+
 bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
                                                       Instruction *BBI,
                                                       BasicBlock *BB) {
diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/select.ll b/llvm/test/Transforms/CorrelatedValuePropagation/select.ll
index be44bdc..bad8e6b 100644
--- a/llvm/test/Transforms/CorrelatedValuePropagation/select.ll
+++ b/llvm/test/Transforms/CorrelatedValuePropagation/select.ll
@@ -73,3 +73,72 @@ if.end:
   ret i32 %sel
 ; CHECK: ret i32 1
 }
+
+define i1 @test1(i32* %p, i1 %unknown) {
+; CHECK-LABEL: @test1
+  %pval = load i32, i32* %p
+  %cmp1 = icmp slt i32 %pval, 255
+  br i1 %cmp1, label %next, label %exit
+
+next:
+  %min = select i1 %unknown, i32 %pval, i32 5
+  ;; TODO: This pointless branch shouldn't be neccessary
+  br label %next2
+next2:
+; CHECK-LABEL: next2:
+; CHECK: ret i1 false
+  %res = icmp eq i32 %min, 255
+  ret i1 %res
+
+exit:
+; CHECK-LABEL: exit:
+; CHECK: ret i1 true
+  ret i1 true
+}
+
+; Check that we take a conservative meet
+define i1 @test2(i32* %p, i32 %qval, i1 %unknown) {
+; CHECK-LABEL: test2
+  %pval = load i32, i32* %p
+  %cmp1 = icmp slt i32 %pval, 255
+  br i1 %cmp1, label %next, label %exit
+
+next:
+  %min = select i1 %unknown, i32 %pval, i32 %qval
+  ;; TODO: This pointless branch shouldn't be neccessary
+  br label %next2
+next2:
+; CHECK-LABEL: next2
+; CHECK: ret i1 %res
+  %res = icmp eq i32 %min, 255
+  ret i1 %res
+
+exit:
+; CHECK-LABEL: exit:
+; CHECK: ret i1 true
+  ret i1 true
+}
+
+; Same as @test2, but for the opposite select input
+define i1 @test3(i32* %p, i32 %qval, i1 %unknown) {
+; CHECK-LABEL: test3
+  %pval = load i32, i32* %p
+  %cmp1 = icmp slt i32 %pval, 255
+  br i1 %cmp1, label %next, label %exit
+
+next:
+  %min = select i1 %unknown, i32 %qval, i32 %pval
+  ;; TODO: This pointless branch shouldn't be neccessary
+  br label %next2
+next2:
+; CHECK-LABEL: next2
+; CHECK: ret i1 %res
+  %res = icmp eq i32 %min, 255
+  ret i1 %res
+
+exit:
+; CHECK-LABEL: exit:
+; CHECK: ret i1 true
+  ret i1 true
+}
+
-- 
2.7.4