[LVI] Take guards into account

Teach LVI to gather control dependant constraints from guards.

Reviewed By: sanjoy

Differential Revision: https://reviews.llvm.org/D23358

llvm-svn: 278518

2 files changed, 124 insertions, 11 deletions

diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp
index 7a940481e6f..04cce6b29d3 100644
--- a/llvm/lib/Analysis/LazyValueInfo.cpp
+++ b/llvm/lib/Analysis/LazyValueInfo.cpp
@@ -26,6 +26,7 @@
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/ValueHandle.h"
@@ -471,8 +472,9 @@ namespace {
                                BasicBlock *BB);
   bool solveBlockValueCast(LVILatticeVal &BBLV, Instruction *BBI,
                            BasicBlock *BB);
-  void intersectAssumeBlockValueConstantRange(Value *Val, LVILatticeVal &BBLV,
-                                              Instruction *BBI);
+  void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
+                                                     LVILatticeVal &BBLV,
+                                                     Instruction *BBI);
 
   void solve();
 
@@ -864,9 +866,8 @@ static LVILatticeVal getValueFromCondition(Value *Val, Value *Cond,
 
 // If we can determine a constraint on the value given conditions assumed by
 // the program, intersect those constraints with BBLV
-void LazyValueInfoCache::intersectAssumeBlockValueConstantRange(Value *Val,
-                                                            LVILatticeVal &BBLV,
-                                                            Instruction *BBI) {
+void LazyValueInfoCache::intersectAssumeOrGuardBlockValueConstantRange(
+        Value *Val, LVILatticeVal &BBLV, Instruction *BBI) {
   BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
   if (!BBI)
     return;
@@ -880,6 +881,20 @@ void LazyValueInfoCache::intersectAssumeBlockValueConstantRange(Value *Val,
 
     BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
   }
+
+  // If guards are not used in the module, don't spend time looking for them
+  auto *GuardDecl = BBI->getModule()->getFunction(
+          Intrinsic::getName(Intrinsic::experimental_guard));
+  if (!GuardDecl || GuardDecl->use_empty())
+    return;
+
+  for (BasicBlock::iterator I = BBI->getIterator(),
+                            E = BBI->getParent()->begin(); I != E; I--) {
+    Value *Cond = nullptr;
+    if (!match(&*I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
+      continue;
+    BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
+  }
 }
 
 bool LazyValueInfoCache::solveBlockValueSelect(LVILatticeVal &BBLV,
@@ -1043,7 +1058,8 @@ bool LazyValueInfoCache::solveBlockValueCast(LVILatticeVal &BBLV,
   ConstantRange LHSRange = ConstantRange(OperandBitWidth);
   if (hasBlockValue(BBI->getOperand(0), BB)) {
     LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
-    intersectAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI);
+    intersectAssumeOrGuardBlockValueConstantRange(BBI->getOperand(0), LHSVal,
+                                                  BBI);
     if (LHSVal.isConstantRange())
       LHSRange = LHSVal.getConstantRange();
   }
@@ -1120,7 +1136,8 @@ bool LazyValueInfoCache::solveBlockValueBinaryOp(LVILatticeVal &BBLV,
   ConstantRange LHSRange = ConstantRange(OperandBitWidth);
   if (hasBlockValue(BBI->getOperand(0), BB)) {
     LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
-    intersectAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI);
+    intersectAssumeOrGuardBlockValueConstantRange(BBI->getOperand(0), LHSVal,
+                                                  BBI);
     if (LHSVal.isConstantRange())
       LHSRange = LHSVal.getConstantRange();
   }
@@ -1363,7 +1380,8 @@ 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);
-  intersectAssumeBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator());
+  intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock,
+                                                BBFrom->getTerminator());
   // We can use the context instruction (generically the ultimate instruction
   // the calling pass is trying to simplify) here, even though the result of
   // this function is generally cached when called from the solve* functions
@@ -1372,7 +1390,7 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
   // functions, the context instruction is not provided. When called from
   // LazyValueInfoCache::getValueOnEdge, the context instruction is provided,
   // but then the result is not cached.
-  intersectAssumeBlockValueConstantRange(Val, InBlock, CxtI);
+  intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
 
   Result = intersect(LocalResult, InBlock);
   return true;
@@ -1389,7 +1407,7 @@ LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB,
     solve();
   }
   LVILatticeVal Result = getBlockValue(V, BB);
-  intersectAssumeBlockValueConstantRange(V, Result, CxtI);
+  intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
 
   DEBUG(dbgs() << "  Result = " << Result << "\n");
   return Result;
@@ -1405,7 +1423,7 @@ LVILatticeVal LazyValueInfoCache::getValueAt(Value *V, Instruction *CxtI) {
   LVILatticeVal Result = LVILatticeVal::getOverdefined();
   if (auto *I = dyn_cast<Instruction>(V))
     Result = getFromRangeMetadata(I);
-  intersectAssumeBlockValueConstantRange(V, Result, CxtI);
+  intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
 
   DEBUG(dbgs() << "  Result = " << Result << "\n");
   return Result;
diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/guards.ll b/llvm/test/Transforms/CorrelatedValuePropagation/guards.ll
new file mode 100644
index 00000000000..401cb2549dd
--- /dev/null
+++ b/llvm/test/Transforms/CorrelatedValuePropagation/guards.ll
@@ -0,0 +1,95 @@
+; RUN: opt -correlated-propagation -S < %s | FileCheck %s
+
+declare void @llvm.experimental.guard(i1,...)
+
+define i1 @test1(i32 %a) {
+; CHECK-LABEL: @test1(
+; CHECK: %alive = icmp eq i32 %a, 8
+; CHECK-NEXT: %result = or i1 false, %alive
+  %cmp = icmp ult i32 %a, 16
+  call void(i1,...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  %dead = icmp eq i32 %a, 16
+  %alive = icmp eq i32 %a, 8
+  %result = or i1 %dead, %alive
+  ret i1 %result
+}
+
+define i1 @test2(i32 %a) {
+; CHECK-LABEL: @test2(
+; CHECK: continue:
+; CHECK-NEXT: %alive = icmp eq i32 %a, 8
+; CHECK-NEXT: %result = or i1 false, %alive
+  %cmp = icmp ult i32 %a, 16
+  call void(i1,...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  br label %continue
+
+continue:
+  %dead = icmp eq i32 %a, 16
+  %alive = icmp eq i32 %a, 8
+  %result = or i1 %dead, %alive
+  ret i1 %result
+}
+
+define i1 @test3(i32 %a, i1 %flag) {
+; CHECK-LABEL: @test3(
+; CHECK: continue:
+; CHECK-NEXT: %alive.1 = icmp eq i32 %a, 16
+; CHECK-NEXT: %alive.2 = icmp eq i32 %a, 8
+; CHECK-NEXT: %result = or i1 %alive.1, %alive.2
+  br i1 %flag, label %true, label %false
+
+true:
+  %cmp = icmp ult i32 %a, 16
+  call void(i1,...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  br label %continue
+
+false:
+  br label %continue
+
+continue:
+  %alive.1 = icmp eq i32 %a, 16
+  %alive.2 = icmp eq i32 %a, 8
+  %result = or i1 %alive.1, %alive.2
+  ret i1 %result
+}
+
+define i1 @test4(i32 %a, i1 %flag) {
+; CHECK-LABEL: @test4(
+; CHECK: continue:
+; CHECK-NEXT: %alive = icmp eq i32 %a, 12
+; CHECK-NEXT: %result = or i1 false, %alive
+  br i1 %flag, label %true, label %false
+
+true:
+  %cmp.t = icmp ult i32 %a, 16
+  call void(i1,...) @llvm.experimental.guard(i1 %cmp.t) [ "deopt"() ]
+  br label %continue
+
+false:
+  %cmp.f = icmp ult i32 %a, 12
+  call void(i1,...) @llvm.experimental.guard(i1 %cmp.f) [ "deopt"() ]
+  br label %continue
+
+continue:
+  %dead = icmp eq i32 %a, 16
+  %alive = icmp eq i32 %a, 12
+  %result = or i1 %dead, %alive
+  ret i1 %result
+}
+
+define i1 @test5(i32 %a) {
+; CHECK-LABEL: @test5(
+; CHECK: continue:
+; CHECK-NEXT: %alive = icmp eq i32 %a.plus.8, 16
+; CHECK-NEXT: %result = or i1 false, %alive
+  %cmp = icmp ult i32 %a, 16
+  call void(i1,...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  %a.plus.8 = add i32 %a, 8
+  br label %continue
+
+continue:
+  %dead = icmp eq i32 %a.plus.8, 24
+  %alive = icmp eq i32 %a.plus.8, 16
+  %result = or i1 %dead, %alive
+  ret i1 %result
+}