[LVI] Don't use dominator tree in isValidAssumeForContext()

[nikic]

Summary

LVI and its consumers currently have quite a bit of complexity related to dominator tree management. However, it doesn't look like it is actually needed...

The only use of the dominator tree is inside isValidAssumeForContext(). However, due to the way LVI queries work, I don't think this is needed. If we query a value for some block, we will first get the edge values from all predecessor blocks, which also includes an intersection with assumptions that apply to the terminator of the predecessor. As such, we will already have processed all assumptions from predecessor blocks (this is actually stronger than what isValidAssumeForContext does with a DT, because this is capable of combining non-dominating assumptions). The only additional assumptions we need to take into account are those in the block being queried. And we don't need a dominator tree for that.

This patch only removes the use of DT. If it lands, I will remove the whole disableDT/enableDT machinery in a followup, because it becomes unused.

[lebedev.ri]

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

[nikic]

Ping

[nikic]

Ping

[nikic]

Ping

[fhahn]

LGTM, thanks! The non-local assumption should be applied when processing the containing basic block, as mentioned in the description.

llvm/lib/Analysis/LazyValueInfo.cpp

 // If we can determine a constraint on the value given conditions assumed by
 // the program, intersect those constraints with BBLV
 void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
         Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) {
   BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
   if (!BBI)
     return;
 
+  BasicBlock *BB = BBI->getParent();
   for (auto &AssumeVH : AC->assumptionsFor(Val)) {
     if (!AssumeVH)
       continue;
+
+    // Only check assumes in the block of the context instruction. Other
+    // assumes will have already been taken into account when the value was
+    // propagated from predecessor blocks.
     auto *I = cast<CallInst>(AssumeVH);
-    if (!isValidAssumeForContext(I, BBI, DT))
+    if (I->getParent() != BB || !isValidAssumeForContext(I, BBI))
       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;
 
-  if (BBI->getIterator() == BBI->getParent()->begin())
+  if (BBI->getIterator() == BB->begin())
     return;
   for (Instruction &I : make_range(std::next(BBI->getIterator().getReverse()),
-                                   BBI->getParent()->rend())) {
+                                   BB->rend())) {
     Value *Cond = nullptr;
     if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
       BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
   }
 }
 
 Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueSelect(
     SelectInst *SI, BasicBlock *BB) {