[LVI] Move assume intersection from getEdgeValue() to getValueOnEdge()

[nikic]

Summary

We currently perform an assume intersection with the context instruction directly in the internal getEdgeValue() API. This patch moves it into getValueOnEdge(), similar to what we do in getValueInBlock() and getValueAt().

There are three users of getEdgeValue():

1. getValueOnEdge(): As this is where the intersection is moved, no change in behavior there.
2. solveBlockValueNonLocal(): This call is done without the context instruction.
3. solveBlockValuePHINode(): This call is done with the phi node as context, i.e. the start of the basic block. We already intersect with the terminators of the predecessors, so this doesn't add anything.

Moving the intersection in this way avoids unnecessary work, makes the LVI APIs more symmetric, and makes the caching more obviously correct (as the lengthy comments that are being removed here indicate.)

[lebedev.ri]

No idea who is comfortable/qualified doing LVI reviews, but that isn't me.

[nikic]

Rebase

[nikic]

Ping

[nikic]

Ping

[nikic]

Ping

lib/Analysis/LazyValueInfo.cpp

bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
       return true;
     }
 
     AssumptionCache *AC;  ///< A pointer to the cache of @llvm.assume calls.
     const DataLayout &DL; ///< A mandatory DataLayout
 
   Optional<ValueLatticeElement> getBlockValue(Value *Val, BasicBlock *BB);
   Optional<ValueLatticeElement> getEdgeValue(Value *V, BasicBlock *F,
-                                BasicBlock *T, Instruction *CxtI = nullptr);
+                                             BasicBlock *T);
 
   // These methods process one work item and may add more. A false value
   // returned means that the work item was not completely processed and must
   // be revisited after going through the new items.
   bool solveBlockValue(Value *Val, BasicBlock *BB);
   Optional<ValueLatticeElement> solveBlockValueImpl(Value *Val, BasicBlock *BB);
   Optional<ValueLatticeElement> solveBlockValueNonLocal(Value *Val,
                                                         BasicBlock *BB);
Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValuePHINode(
   ValueLatticeElement Result;  // Start Undefined.
 
   // Loop over all of our predecessors, merging what we know from them into
   // result.  See the comment about the chosen traversal order in
   // solveBlockValueNonLocal; the same reasoning applies here.
   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
     BasicBlock *PhiBB = PN->getIncomingBlock(i);
     Value *PhiVal = PN->getIncomingValue(i);
-    // Note that we can provide PN as the context value to getEdgeValue, even
-    // though the results will be cached, because PN is the value being used as
-    // the cache key in the caller.
-    Optional<ValueLatticeElement> EdgeResult =
-        getEdgeValue(PhiVal, PhiBB, BB, PN);
+    Optional<ValueLatticeElement> EdgeResult = getEdgeValue(PhiVal, PhiBB, BB);
     if (!EdgeResult)
       // Explore that input, then return here
       return None;
 
     Result.mergeIn(*EdgeResult);
 
     // If we hit overdefined, exit early.  The BlockVals entry is already set
     // to overdefined.
if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
     return ValueLatticeElement::getRange(std::move(EdgesVals));
   }
   return None;
 }
 
 /// Compute the value of Val on the edge BBFrom -> BBTo or the value at
 /// the basic block if the edge does not constrain Val.
 Optional<ValueLatticeElement> LazyValueInfoImpl::getEdgeValue(
-    Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo, Instruction *CxtI) {
+    Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo) {
   // If already a constant, there is nothing to compute.
   if (Constant *VC = dyn_cast<Constant>(Val))
     return ValueLatticeElement::get(VC);
 
   ValueLatticeElement LocalResult = getEdgeValueLocal(Val, BBFrom, BBTo)
       .getValueOr(ValueLatticeElement::getOverdefined());
   if (hasSingleValue(LocalResult))
     // Can't get any more precise here
     return LocalResult;
 
   Optional<ValueLatticeElement> OptInBlock = getBlockValue(Val, BBFrom);
   if (!OptInBlock)
     return None;
   ValueLatticeElement &InBlock = *OptInBlock;
 
   // Try to intersect ranges of the BB and the constraint on the edge.
   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
-  // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
-  // but then the result is not cached.
-  intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
 
   return intersect(LocalResult, InBlock);
 }
 
 ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
                                                        Instruction *CxtI) {
   LLVM_DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
                     << BB->getName() << "'\n");

 
 ValueLatticeElement LazyValueInfoImpl::
 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
                Instruction *CxtI) {
   LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
                     << FromBB->getName() << "' to '" << ToBB->getName()
                     << "'\n");
 
-  Optional<ValueLatticeElement> Result = getEdgeValue(V, FromBB, ToBB, CxtI);
+  Optional<ValueLatticeElement> Result = getEdgeValue(V, FromBB, ToBB);
   if (!Result) {
     solve();
-    Result = getEdgeValue(V, FromBB, ToBB, CxtI);
+    Result = getEdgeValue(V, FromBB, ToBB);
     assert(Result && "More work to do after problem solved?");
   }
+  intersectAssumeOrGuardBlockValueConstantRange(V, *Result, CxtI);
 
   LLVM_DEBUG(dbgs() << "  Result = " << *Result << "\n");
   return *Result;
 }
 
 void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
                                    BasicBlock *NewSucc) {
   TheCache.threadEdgeImpl(OldSucc, NewSucc);