[LVI] Take guards into account

[apilipenko]

Summary

Teach LVI to gather control dependant constraints from guards.

[sanjoy]

lgtm with some minor comments

lib/Analysis/LazyValueInfo.cpp

868

Doesn't have to be this change, but please document BBI.

884

Can this be make conditional on if there are uses of the guard intrinsic? E.g. see HasGuards in ScalarEvolution -- that way clients of LLVM that don't use guards at all won't have to do this linear scan.

886

Optional -- we could rewrite this as a range for:

for (auto &I : make_range(std::reverse_iterator(BBI->getIterator()), BBI->getParent()->rend()))

(Not sure if that is clearly better)

890

Is this clang formatted?

lib/Analysis/LazyValueInfo.cpp

 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #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"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include <map>
 #include <stack>
 using namespace llvm;
namespace {
   bool solveBlockValueNonLocal(LVILatticeVal &BBLV, Value *Val, BasicBlock *BB);
   bool solveBlockValuePHINode(LVILatticeVal &BBLV, PHINode *PN, BasicBlock *BB);
   bool solveBlockValueSelect(LVILatticeVal &BBLV, SelectInst *S,
                              BasicBlock *BB);
   bool solveBlockValueBinaryOp(LVILatticeVal &BBLV, Instruction *BBI,
                                BasicBlock *BB);
   bool solveBlockValueCast(LVILatticeVal &BBLV, Instruction *BBI,
                            BasicBlock *BB);
-  void intersectAssumeBlockValueConstantRange(Value *Val, LVILatticeVal &BBLV,
+  void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
+                                                     LVILatticeVal &BBLV,
                                                      Instruction *BBI);
 
   void solve();
 
     bool isOverdefined(Value *V, BasicBlock *BB) const {
       auto ODI = OverDefinedCache.find(BB);
 
       if (ODI == OverDefinedCache.end())
         return false;
bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
   BBLV = Result;
   return true;
 }
 
 static LVILatticeVal getValueFromCondition(Value *Val, Value *Cond,
                                            bool isTrueDest = true);
 
 // 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;
 
   for (auto &AssumeVH : AC->assumptions()) {
     if (!AssumeVH)
       continue;
     auto *I = cast<CallInst>(AssumeVH);
     if (!isValidAssumeForContext(I, BBI, DT))
       continue;
 
     BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
   }
+
+  for (BasicBlock::iterator I = BBI->getIterator(),
+                            E = BBI->getParent()->begin();
+       I != E; I--) {
+    Value *Condition = nullptr;
+    if (!match(&*I, m_Intrinsic<Intrinsic::experimental_guard>(
+               m_Value(Condition))))
+      continue;
+
+    BBLV = intersect(BBLV, getValueFromCondition(Val, Condition));
+  }
 }
 
 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())))
if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
       // More work to do before applying this transfer rule.
       return false;
 
   const unsigned OperandBitWidth =
     DL.getTypeSizeInBits(BBI->getOperand(0)->getType());
   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();
   }
 
   const unsigned ResultBitWidth =
     cast<IntegerType>(BBI->getType())->getBitWidth();
 
   // NOTE: We're currently limited by the set of operations that ConstantRange
if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
       // More work to do before applying this transfer rule.
       return false;
 
   const unsigned OperandBitWidth =
     DL.getTypeSizeInBits(BBI->getOperand(0)->getType());
   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();
   }
 
   ConstantInt *RHS = cast<ConstantInt>(BBI->getOperand(1));
   ConstantRange RHSRange = ConstantRange(RHS->getValue());
 
   // NOTE: We're currently limited by the set of operations that ConstantRange
if (pushBlockValue(std::make_pair(BBFrom, Val)))
       return false;
     // No new information.
     Result = LocalResult;
     return true;
   }
 
   // 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
   // (and that cached result might be used with queries using a different
   // context instruction), because when this function is called from the solve*
   // 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;
 }
 
 LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB,
                                                   Instruction *CxtI) {
   DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
         << BB->getName() << "'\n");
 
   assert(BlockValueStack.empty() && BlockValueSet.empty());
   if (!hasBlockValue(V, BB)) {
     pushBlockValue(std::make_pair(BB, V));
     solve();
   }
   LVILatticeVal Result = getBlockValue(V, BB);
-  intersectAssumeBlockValueConstantRange(V, Result, CxtI);
+  intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
 
   DEBUG(dbgs() << "  Result = " << Result << "\n");
   return Result;
 }
 
 LVILatticeVal LazyValueInfoCache::getValueAt(Value *V, Instruction *CxtI) {
   DEBUG(dbgs() << "LVI Getting value " << *V << " at '"
         << CxtI->getName() << "'\n");
 
   if (auto *C = dyn_cast<Constant>(V))
     return LVILatticeVal::get(C);
 
   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;
 }
 
 LVILatticeVal LazyValueInfoCache::
 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
                Instruction *CxtI) {

test/Transforms/CorrelatedValuePropagation/guards.ll

+; 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
+}