[LVI] Cleanup/unify cache access

[nikic]

Summary

This patch combines the "has" and "get" parts of the cache access. getCachedValueInfo() now both sets the BBLV return argument, and returns whether the value was found.

Additionally, the management of the work stack is now integrated into getBlockValue(). If the value is not cached yet, we try to push to the stack (and return false, indicating that we need to solve first), or return overdefined in case of a cycle.

These changes a) avoid a duplicate cache lookup for has & get and b) ensure that the logic is uniform everywhere. For this reason this change is also not quite NFC, because previously overdefined values from the cache, and overdefined values from a cycle received slightly different treatment in some places.

[nikic]

Ping

[fhahn]

lib/Analysis/LazyValueInfo.cpp

212

Would it make sense to return Optional<ValuelLatticeElement> instead? IMO that would make things a bit more explicit (and personally I think it's easier to follow than using 'out' parameters)

[nikic]

lib/Analysis/LazyValueInfo.cpp

212

I'm a bit fan of Option(al) ... in Rust. Unfortunately, the ergonomics of Optional in C++ really leave something to be desired :(

LVI is mostly based around the out parameter + bool return pattern, with only one part using Optional returns: https://github.com/llvm/llvm-project/blob/9e1455dc236252a60066c312c6d2e8a7ed66f609/llvm/lib/Analysis/LazyValueInfo.cpp#L1047-L1051

This kind of code is (imho) rather ugly and inefficient (in this example, it will result in an entirely unnecessary copy of the range).

Possibly I'm just missing some kind of standard pattern for this? I wasn't able to find anything on this, not even in C++17.

Another possibility would be to add another state to ValueLatticeElement like unresolved for this purpose. I tried using unknown for this initially, because I thought it would not occur inside the LVI cache, but it does occur for values coming from unreachable blocks.

[fhahn]

lib/Analysis/LazyValueInfo.cpp

212

I'm a bit fan of Option(al) ... in Rust. Unfortunately, the ergonomics of Optional in C++ really leave something to be desired :(

Unfortunately there's no direct equivalent for Rust's if let Some(m) = &MaybeFoo {} which lets you unpack the value from the optional, if it has one as far as I am aware. Probably the next best thing would be to use if (Optional<ConstantRange> CR = getOptionalCR()) { and use *CR/CR.getValue() in the if body. Using auto in the if that's just one character more :)

This kind of code is (imho) rather ugly and inefficient (in this example, it will result in an entirely unnecessary copy of the range).

Are you referring to the the explicit copy ConstantRange LHSRange = LHSRes.getValue();? That's not necessary, getValue returns a reference. There's the copy/move of the optional result from callee to caller of course, but ideally the compiler should be able to remove them I guess, as long as it can inline things. In some cases, it might even save some work, as you do not have to unconditionally construct a ValueLatticeElement in the caller.

Possibly I'm just missing some kind of standard pattern for this? I wasn't able to find anything on this, not even in C++17.

I don't think there is much potential for improvement here, as it is just a regular type and the if (auto X = ..) syntax relies on the bool operator of the result :(

LVI is mostly based around the out parameter + bool return pattern, with only one part using Optional returns: https://github.com/llvm/llvm-project/blob/9e1455dc236252a60066c312c6d2e8a7ed66f609/llvm/lib/Analysis/LazyValueInfo.cpp#L1047-L1051

Right. Conceptually it seems Optional would be a good fit here, but if the existing code uses the other pattern the incentive for change is not that big I guess.

[lebedev.ri]

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

[nikic]

lib/Analysis/LazyValueInfo.cpp

212

I just gave the Optional conversion a try, and it looks a lot nicer than I expected: https://gist.github.com/nikic/f437fc7f667e433f462232aeb5272bc1

I'd like to apply this as a NFC cleanup after this patch though, as has to touch a lot more code.

[fhahn]

lib/Analysis/LazyValueInfo.cpp

212

SGTM, thanks!

1000

It looks like the original code checks for the block value again after pushing it. I think the new code skips the check. Not sure if it actually matters though?

1523

This case seems to be gone in the new code? Not sure if it matters much in practice?

[nikic]

lib/Analysis/LazyValueInfo.cpp

1000

pushBlockValue() does not change the result of hasBlockValue() (it pushes to the work stack, but does not modify the cache). The duplicate hasBlockValue() call here was to handle the case where pushBlockValue() returned false (and thus did not early exit above).

There is indeed a change in behavior here, this is one of the "not quite NFC" parts mentioned in the summary: Previously the case where the value is assumed overdefined due to a cycle would always result in a full range here, while now it will be treated like other overdefined values by trying to perform the assume intersect first.

1523

Right, this is the second "not quite NFC" part. If we assume an overdefined block value due to a cycle, this previously did not perform the assume intersections below, while now it does.

In both cases, this may improve analysis results in some edge cases, though I doubt it happens in practice. It could also make analysis more expensive, but at least I did not see any compile-time regressions.

[fhahn]

LGTM, thanks for clarifying the not quite NFC bits. Sounds reasonable and safe. I also checked test-suite & SPEC, there are now binary changes with this patch on -O3 & LTO. But it would be good to wait a day or so with committing, in case there are additional thoughts.

lib/Analysis/LazyValueInfo.cpp

bool isOverdefined(Value *V, BasicBlock *BB) const {
       auto ODI = OverDefinedCache.find(BB);
 
       if (ODI == OverDefinedCache.end())
         return false;
 
       return ODI->second.count(V);
     }
 
-    bool hasCachedValueInfo(Value *V, BasicBlock *BB) const {
-      if (isOverdefined(V, BB))
+    bool getCachedValueInfo(ValueLatticeElement &BBLV, Value *V,
+                            BasicBlock *BB) const {
+      if (isOverdefined(V, BB)) {
+        BBLV = ValueLatticeElement::getOverdefined();
         return true;
-
-      auto I = ValueCache.find_as(V);
-      if (I == ValueCache.end())
-        return false;
-
-      return I->second->BlockVals.count(BB);
       }
 
-    ValueLatticeElement getCachedValueInfo(Value *V, BasicBlock *BB) const {
-      if (isOverdefined(V, BB))
-        return ValueLatticeElement::getOverdefined();
-
       auto I = ValueCache.find_as(V);
       if (I == ValueCache.end())
-        return ValueLatticeElement();
+        return false;
       auto BBI = I->second->BlockVals.find(BB);
       if (BBI == I->second->BlockVals.end())
-        return ValueLatticeElement();
-      return BBI->second;
+        return false;
+      BBLV = BBI->second;
+      return true;
     }
 
     /// clear - Empty the cache.
     void clear() {
       SeenBlocks.clear();
       ValueCache.clear();
       OverDefinedCache.clear();
     }
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
     DominatorTree *DT;    ///< An optional DT pointer.
     DominatorTree *DisabledDT; ///< Stores DT if it's disabled.
 
-  ValueLatticeElement getBlockValue(Value *Val, BasicBlock *BB);
+  bool getBlockValue(ValueLatticeElement &Result, Value *Val, BasicBlock *BB);
   bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
                     ValueLatticeElement &Result, Instruction *CxtI = nullptr);
-  bool hasBlockValue(Value *Val, BasicBlock *BB);
 
   // 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);
   bool solveBlockValueImpl(ValueLatticeElement &Res, Value *Val,
                            BasicBlock *BB);
   bool solveBlockValueNonLocal(ValueLatticeElement &BBLV, Value *Val,
if (processedCount > MaxProcessedPerValue) {
       return;
     }
     std::pair<BasicBlock *, Value *> e = BlockValueStack.back();
     assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
 
     if (solveBlockValue(e.second, e.first)) {
       // The work item was completely processed.
       assert(BlockValueStack.back() == e && "Nothing should have been pushed!");
-      assert(TheCache.hasCachedValueInfo(e.second, e.first) &&
+#ifndef NDEBUG
+      ValueLatticeElement BBLV;
+      assert(TheCache.getCachedValueInfo(BBLV, e.second, e.first) &&
              "Result should be in cache!");
-
       LLVM_DEBUG(
           dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = "
-                 << TheCache.getCachedValueInfo(e.second, e.first) << "\n");
+                 << BBLV << "\n");
+#endif
 
       BlockValueStack.pop_back();
       BlockValueSet.erase(e);
     } else {
       // More work needs to be done before revisiting.
       assert(BlockValueStack.back() != e && "Stack should have been pushed!");
     }
   }
 }
 
-bool LazyValueInfoImpl::hasBlockValue(Value *Val, BasicBlock *BB) {
+bool LazyValueInfoImpl::getBlockValue(ValueLatticeElement &BBLV,
+                                      Value *Val, BasicBlock *BB) {
   // If already a constant, there is nothing to compute.
-  if (isa<Constant>(Val))
+  if (Constant *VC = dyn_cast<Constant>(Val)) {
+    BBLV = ValueLatticeElement::get(VC);
     return true;
-
-  return TheCache.hasCachedValueInfo(Val, BB);
   }
 
-ValueLatticeElement LazyValueInfoImpl::getBlockValue(Value *Val,
-                                                     BasicBlock *BB) {
-  // If already a constant, there is nothing to compute.
-  if (Constant *VC = dyn_cast<Constant>(Val))
-    return ValueLatticeElement::get(VC);
+  if (TheCache.getCachedValueInfo(BBLV, Val, BB))
+    return true;
 
-  return TheCache.getCachedValueInfo(Val, BB);
+  // We have hit a cycle, assume overdefined.
+  if (!pushBlockValue({ BB, Val })) {
+    BBLV = ValueLatticeElement::getOverdefined();
+    return true;
+  }
+
+  // Yet to be resolved.
+  return false;
 }
 
 static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) {
   switch (BBI->getOpcode()) {
   default: break;
   case Instruction::Load:
   case Instruction::Call:
   case Instruction::Invoke:
     if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
       if (isa<IntegerType>(BBI->getType())) {
         return ValueLatticeElement::getRange(
             getConstantRangeFromMetadata(*Ranges));
       }
     break;
   };
   // Nothing known - will be intersected with other facts
   return ValueLatticeElement::getOverdefined();
 }
 
 bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
+#ifndef NDEBUG
+  ValueLatticeElement BBLV;
   assert(!isa<Constant>(Val) && "Value should not be constant");
-  assert(!TheCache.hasCachedValueInfo(Val, BB) &&
+  assert(!TheCache.getCachedValueInfo(BBLV, Val, BB) &&
          "Value should not be in cache");
+#endif
 
   // Hold off inserting this value into the Cache in case we have to return
   // false and come back later.
   ValueLatticeElement Res;
   if (!solveBlockValueImpl(Res, Val, BB))
     // Work pushed, will revisit
     return false;
 
if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
       BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
   }
 }
 
 bool LazyValueInfoImpl::solveBlockValueSelect(ValueLatticeElement &BBLV,
                                               SelectInst *SI, BasicBlock *BB) {
 
   // Recurse on our inputs if needed
-  if (!hasBlockValue(SI->getTrueValue(), BB)) {
-    if (pushBlockValue(std::make_pair(BB, SI->getTrueValue())))
-      return false;
-    BBLV = ValueLatticeElement::getOverdefined();
-    return true;
-  }
-  ValueLatticeElement TrueVal = getBlockValue(SI->getTrueValue(), BB);
+  ValueLatticeElement TrueVal;
+  if (!getBlockValue(TrueVal, SI->getTrueValue(), BB))
+
   // If we hit overdefined, don't ask more queries.  We want to avoid poisoning
   // extra slots in the table if we can.
   if (TrueVal.isOverdefined()) {
     BBLV = ValueLatticeElement::getOverdefined();
     return true;
   }
 
-  if (!hasBlockValue(SI->getFalseValue(), BB)) {
-    if (pushBlockValue(std::make_pair(BB, SI->getFalseValue())))
-      return false;
-    BBLV = ValueLatticeElement::getOverdefined();
-    return true;
-  }
-  ValueLatticeElement FalseVal = getBlockValue(SI->getFalseValue(), BB);
+  ValueLatticeElement FalseVal;
+  if (!getBlockValue(FalseVal, SI->getFalseValue(), BB))
+
   // If we hit overdefined, don't ask more queries.  We want to avoid poisoning
   // extra slots in the table if we can.
   if (FalseVal.isOverdefined()) {
     BBLV = ValueLatticeElement::getOverdefined();
     return true;
   }
 
   if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) {
bool LazyValueInfoImpl::solveBlockValueSelect(ValueLatticeElement &BBLV,
   Result.mergeIn(FalseVal, DL);
   BBLV = Result;
   return true;
 }
 
 Optional<ConstantRange> LazyValueInfoImpl::getRangeForOperand(unsigned Op,
                                                               Instruction *I,
                                                               BasicBlock *BB) {
-  if (!hasBlockValue(I->getOperand(Op), BB))
-    if (pushBlockValue(std::make_pair(BB, I->getOperand(Op))))
-      return None;
+  ValueLatticeElement Val;
+  if (!getBlockValue(Val, I->getOperand(Op), BB))
 
-  const unsigned OperandBitWidth =
-    DL.getTypeSizeInBits(I->getOperand(Op)->getType());
-  ConstantRange Range = ConstantRange::getFull(OperandBitWidth);
-  if (hasBlockValue(I->getOperand(Op), BB)) {
-    ValueLatticeElement Val = getBlockValue(I->getOperand(Op), BB);
-    intersectAssumeOrGuardBlockValueConstantRange(I->getOperand(Op), Val, I);
-    if (Val.isConstantRange())
-      Range = Val.getConstantRange();
-  }
-  return Range;
+    return Val.getConstantRange();
+
+  const unsigned OperandBitWidth =
+    DL.getTypeSizeInBits(I->getOperand(Op)->getType());
+  return ConstantRange::getFull(OperandBitWidth);
 }
 
 bool LazyValueInfoImpl::solveBlockValueCast(ValueLatticeElement &BBLV,
                                             CastInst *CI,
                                             BasicBlock *BB) {
   if (!CI->getOperand(0)->getType()->isSized()) {
     // Without knowing how wide the input is, we can't analyze it in any useful
     // way.
bool LazyValueInfoImpl::solveBlockValueExtractValue(
   if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
     if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0)
       return solveBlockValueOverflowIntrinsic(BBLV, WO, BB);
 
   // Handle extractvalue of insertvalue to allow further simplification
   // based on replaced with.overflow intrinsics.
   if (Value *V = SimplifyExtractValueInst(
           EVI->getAggregateOperand(), EVI->getIndices(),
-          EVI->getModule()->getDataLayout())) {
-    if (!hasBlockValue(V, BB)) {
-      if (pushBlockValue({ BB, V }))
-        return false;
-      BBLV = ValueLatticeElement::getOverdefined();
-      return true;
-    }
-    BBLV = getBlockValue(V, BB);
-    return true;
-  }
+          EVI->getModule()->getDataLayout()))
+    return getBlockValue(BBLV, V, BB);
 
   LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
                     << "' - overdefined (unknown extractvalue).\n");
   BBLV = ValueLatticeElement::getOverdefined();
   return true;
 }
 
 static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
     LocalResult = ValueLatticeElement::getOverdefined();
 
   if (hasSingleValue(LocalResult)) {
     // Can't get any more precise here
     Result = LocalResult;
     return true;
   }
 
-  if (!hasBlockValue(Val, BBFrom)) {
-    if (pushBlockValue(std::make_pair(BBFrom, Val)))
-      return false;
-    // No new information.
-    Result = LocalResult;
-    return true;
-  }
+  ValueLatticeElement InBlock;
+  if (!getBlockValue(InBlock, Val, BBFrom))
 
   // Try to intersect ranges of the BB and the constraint on the edge.
-  ValueLatticeElement InBlock = getBlockValue(Val, BBFrom);
   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);
 
   Result = intersect(LocalResult, InBlock);
   return true;
 }
 
 ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
                                                        Instruction *CxtI) {
   LLVM_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));
+  ValueLatticeElement Result;
+  if (!getBlockValue(Result, V, BB)) {
     solve();
+    bool ValueAvailable = getBlockValue(Result, V, BB);
+    (void) ValueAvailable;
+    assert(ValueAvailable && "Value not available after solving");
   }
-  ValueLatticeElement Result = getBlockValue(V, BB);
   intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
 
   LLVM_DEBUG(dbgs() << "  Result = " << Result << "\n");
   return Result;
 }
 
 ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
   LLVM_DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName()