[LVI] Clarify invariants, common code, and fix latent bugs

[reames]

Summary

This patch includes a couple of small changes needed for a follow on patch. One them fixes a latent bug (which I believe is unreachable today).

Changes are:

1. Ensure that calling getValueInBlock with a constant works. It's trivial, but there's nothing preventing this getting called in the outer layers. Additionally, we've been apparently re-querying the outermost block on each access. This is a waste of compile time and (hopefully) will produce the same result as using the previously cached result.
2. Use the full power of the getValueInBlock interface for getValueAt when the query instruction is at the end of a block. I don't know of a test case which clearly illustrates this difference, but in principal, we may be able to remove a few extra comparisons after this change. The main reason for this is to better test existing code paths.
3. Fix a bug exposed by (2) where we weren't actually using the range metadata results within the getValueInBlock solving.

[sanjoy]

Some comments inline. Given that I'm not familiar with LVI, take the comments with a grain of salt.

lib/Analysis/LazyValueInfo.cpp

578

I think the same logic can be better stated by having Res be a Optional<LVILatticeVal> instead of LVILatticeVal. Using the undefined state this way is confusing as I'd normally assume a value to be undefined to mean that the code that uses it is dead.

1041

Does this mean the assert in pushBlockValue can be strengthened to assert(!hasBlockValue(V, BB)) (instead of just checking for a Constant)?

1061

If getValueInBlock computes the result at the end of BB, is CxtI a redundant parameter?

test/Transforms/CorrelatedValuePropagation/basic.ll

227

we can use assume facts to prove things about terminators

So CVP can simplify the %res use in the branch? If so, can you please add a CHECK line checking for the same?

lib/Analysis/LazyValueInfo.cpp

class LazyValueInfoCache {
     std::stack<std::pair<BasicBlock*, Value*> > BlockValueStack;
 
     /// Keeps track of which block-value pairs are in BlockValueStack.
     DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
 
     /// Push BV onto BlockValueStack unless it's already in there.
     /// Returns true on success.
     bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
+      assert(!isa<Constant>(BV.second) &&
+             "Constants should not need to be pushed!");
       if (!BlockValueSet.insert(BV).second)
         return false;  // It's already in the stack.
 
       BlockValueStack.push(BV);
       return true;
     }
 
     AssumptionCache *AC;  ///< A pointer to the cache of @llvm.assume calls.
class LazyValueInfoCache {
 
     void solve();
 
     ValueCacheEntryTy &lookup(Value *V) {
       return ValueCache[LVIValueHandle(V, this)];
     }
 
   public:
-    /// This is the query interface to determine the lattice
-    /// value for the specified Value* at the end of the specified block.
+    /// This is the query interface to determine the lattice value for the
+    /// specified Value* at the end of the specified block.  Note that this
+    /// routine caches results internally based on what's known to be true at
+    /// the end of BB, but may return more precise results if the context
+    /// instruction is not the terminator of BB. 
     LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB,
                                   Instruction *CxtI = nullptr);
 
     /// This is the query interface to determine the lattice
     /// value for the specified Value* at the specified instruction (generally
     /// from an assume intrinsic).
     LVILatticeVal getValueAt(Value *V, Instruction *CxtI);
 
bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
   }
 
   // If this is an instruction which supports range metadata, return the
   // implied range.  TODO: This should be an intersection, not a union.
   Res.mergeIn(getFromRangeMetadata(BBI), DL);
 
   // We can only analyze the definitions of certain classes of instructions
   // (integral binops and casts at the moment), so bail if this isn't one.
-  LVILatticeVal Result;
   if ((!isa<BinaryOperator>(BBI) && !isa<CastInst>(BBI)) ||
       !BBI->getType()->isIntegerTy()) {
+    // If we haven't found any facts about this value, we need to return
+    // something conservatively correct.  If we have found facts, we want to
+    // use them.
+    if (Res.isUndefined()) {
       DEBUG(dbgs() << " compute BB '" << BB->getName()
                    << "' - overdefined because inst def found.\n");
       Res.markOverdefined();
+    }
     insertResult(Val, BB, Res);
     return true;
   }
 
   // FIXME: We're currently limited to binops with a constant RHS.  This should
   // be improved.
   BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
   if (BO && !isa<ConstantInt>(BO->getOperand(1))) { 
if (ICmpInst *ICI = dyn_cast<ICmpInst>(C)) {
           BBLV = Result;
         else
           BBLV.mergeIn(Result, DL);
       }
     }
   }
 }
 
+
 bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
                                                       Instruction *BBI,
                                                       BasicBlock *BB) {
   // Figure out the range of the LHS.  If that fails, bail.
   if (!hasBlockValue(BBI->getOperand(0), BB)) {
     if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
       return false;
     BBLV.markOverdefined();

 }
 
 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());
-  pushBlockValue(std::make_pair(BB, V));
 
+  // Unless a block value for V is known in BB, solve for it.  Note that
+  // Constants will never take this path since they are always known.
+  if (!hasBlockValue(V, BB)) {
+    pushBlockValue(std::make_pair(BB, V));
     solve();
+  }
   LVILatticeVal Result = getBlockValue(V, BB);
   mergeAssumeBlockValueConstantRange(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");
+        << *CxtI << "'\n");
+
+  auto *BB = CxtI->getParent();
 
+  // Use the generic infrastructure to solve for the value in the required
+  // basic block if we can.
   LVILatticeVal Result;
+  if (BB->getTerminator() == CxtI)
+    Result = getValueInBlock(V, BB, CxtI);
+  else {
+    // If we couldn't use the generic infrastructure (since context is not the
+    // terminator and facts true at the end of the basic block might not
+    // apply), handle some easy cases.
+    // TODO: We could extent this to use LVI to compute the result on the start
+    // of a basic block, and then intersect.  
     if (auto *I = dyn_cast<Instruction>(V))
       Result = getFromRangeMetadata(I);
     mergeAssumeBlockValueConstantRange(V, Result, CxtI);
-
+  }
   DEBUG(dbgs() << "  Result = " << Result << "\n");
   return Result;
 }
 
 LVILatticeVal LazyValueInfoCache::
 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
                Instruction *CxtI) {
   DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
if (PImpl) {
     PImpl = nullptr;
   }
 }
 
 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
                                      Instruction *CxtI) {
   const DataLayout &DL = BB->getModule()->getDataLayout();
   LVILatticeVal Result =
-      getCache(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
 
   if (Result.isConstant())
     return Result.getConstant();
   if (Result.isConstantRange()) {
     ConstantRange CR = Result.getConstantRange();
     if (const APInt *SingleVal = CR.getSingleElement())
       return ConstantInt::get(V->getContext(), *SingleVal);
   }

test/Transforms/CorrelatedValuePropagation/basic.ll

 ; CHECK: br label %next
 
 out:
   ret void
 
 next:
   ret void
 }
+
+; The next two check for a subtle potential miscompile.  In these examples,
+; we can use assume facts to prove things about terminators, but can NOT use
+; those those same facts for uses proceding the assume since control flow may
+; never reach the assume.  This is essentially checking that getValueInBlock 
+; from LVI correctly separates block facts and context specific facts.
+
+declare void @may_throw(i1)
+declare void @llvm.assume(i1)
+
+define i1 @maythrow(i32 %p) {
+; CHECK-LABEL: @maythrow
+; CHECK: @may_throw(i1 %res)
+  %res = icmp eq i32 %p, 0
+  call void @may_throw(i1 %res)
+  call void @llvm.assume(i1 %res)
+  ret i1 %res
+}
+
+define i1 @maythrow2(i32 %p) {
+; CHECK-LABEL: @maythrow2
+; CHECK: @may_throw(i1 %res)
+  %res = icmp eq i32 %p, 0
+  call void @may_throw(i1 %res)
+  call void @llvm.assume(i1 %res)
+  br i1 %res, label %taken, label %untaken
+taken:
+  ret i1 %res
+untaken:
+  ret i1 %res
+}