[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 ↗

(On Diff #67538)

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

884 ↗

(On Diff #67538)

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 ↗

(On Diff #67538)

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 ↗

(On Diff #67538)

Is this clang formatted?

llvm/trunk/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,
   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)));
   }
+
+  // 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,
                                                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) {

llvm/trunk/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
+}