[RFC] [LLVM] [LazyValueInfo] Introduce getRecurringEdgeValue to handle simple recurrence

[etherzhhb]

Summary

Teach LazyValueInfo to handle simple patterns on the PHINodes, including:

1. Induction variable of natural loop that increased by 1
2. select (phi (init, select)) generated from linear search

This is accomplished by computing the value of PHINode recurring edge based on mathematical fixed-point. We will fallback to getEdgeValue if we cannot handle the recurring edge.

PS: How should I add unittest for this? since it is "lazy". maybe I should come back with a LazyValueInfo printer

[regehr]

Could you please quantify the effect that this has on compile time? Time for an optimized -j1 compile of LLVM itself is reasonable. Also it would be nice to know what effect this has on generated code.

[etherzhhb]

In D35858#820816, @regehr wrote:

Could you please quantify the effect that this has on compile time? Time for an optimized -j1 compile of LLVM itself is reasonable. Also it would be nice to know what effect this has on generated code.

Sure, will do that.

[reames]

Pending update per last comment, just getting this off review queue.

lib/Analysis/LazyValueInfo.cpp

namespace {
   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,
                                               Instruction *BBI);
+  bool getRecurringEdgeValue(Value *RecurVal, BasicBlock *F, BasicBlock *T,
+                             LVILatticeVal &EdgeResult,
+                             const LVILatticeVal &ResultSoFar, PHINode *PN);
 
   void solve();
 
   ValueCacheEntryTy &lookup(Value *V) {
     return ValueCache[LVIValueHandle(V, this)];
   }
 
     bool isOverdefined(Value *V, BasicBlock *BB) const {
bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV,
   assert(!Result.isOverdefined());
   BBLV = Result;
   return true;
 }
 
 bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
                                                 PHINode *PN, BasicBlock *BB) {
   LVILatticeVal Result;  // Start Undefined.
+  auto *PNParent = PN->getParent();
+
+  SmallVector<BasicBlock *, 4> Blocks(PN->blocks());
+  if (DT) {
+    // Sort the blocks such that we visit the backedge last
+    std::partition(Blocks.begin(), Blocks.end(),
+                   [this, PNParent](BasicBlock *IncomingBB) {
+                     return !DT->dominates(PNParent, IncomingBB);
+                   });
+  }
 
   // Loop over all of our predecessors, merging what we know from them into
   // result.
   bool EdgesMissing = false;
-  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
-    BasicBlock *PhiBB = PN->getIncomingBlock(i);
-    Value *PhiVal = PN->getIncomingValue(i);
+  for (auto *PhiBB : Blocks) {
+    Value *PhiVal = PN->getIncomingValueForBlock(PhiBB);
     LVILatticeVal EdgeResult;
     // 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.
+    if (DT && DT->dominates(PNParent, PhiBB))
+      // Try to calculate a more precise LVILatticeVal on the recurring edge
+      // based on mathematical fix-point. This function will fallback to
+      // getEdgeValue if we cannot handle the edge.
+      // Currently getRecurringEdgeValue only handle a few patterns
+      EdgesMissing |=
+          !getRecurringEdgeValue(PhiVal, PhiBB, BB, EdgeResult, Result, PN);
+    else
       EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN);
     if (EdgesMissing)
       continue;
 
     Result.mergeIn(EdgeResult, DL);
 
     // If we hit overdefined, exit early.  The BlockVals entry is already set
     // to overdefined.
     if (Result.isOverdefined()) {
for (SwitchInst::CaseIt i : SI->cases()) {
         EdgesVals = EdgesVals.unionWith(EdgeVal);
     }
     Result = LVILatticeVal::getRange(std::move(EdgesVals));
     return true;
   }
   return false;
 }
 
+static bool MatchIncreasedByOne(PHINode *PN, Instruction *Update) {
+  return match(Update, m_CombineOr(m_Add(m_One(), m_Specific(PN)),
+                                   m_Add(m_Specific(PN), m_One())));
+}
+
+static bool MatchSelectRecurrence(PHINode *PN, SelectInst *Sel,
+                                  Value *&Incoming) {
+  if (isa<Constant>(Sel->getCondition()))
+    return false;
+
+  if (Sel->getTrueValue() == PN) {
+    Incoming = Sel->getFalseValue();
+    return true;
+  }
+
+  if (Sel->getFalseValue() == PN) {
+    Incoming = Sel->getTrueValue();
+    return true;
+  }
+
+  return false;
+}
+
+/// \brief Compute the value of PHINode recurring edge based on mathematical
+/// fixed-point. Fall back to getEdgeValue if we cannot handle the edge
+/// return false if the edge is missing
+bool LazyValueInfoCache::getRecurringEdgeValue(
+    Value *RecurVal, BasicBlock *BBFrom, BasicBlock *BBTo,
+    LVILatticeVal &EdgeResult, const LVILatticeVal &ResultSoFar, PHINode *PN) {
+  // If already a constant, there is nothing to compute.
+  if (Constant *VC = dyn_cast<Constant>(RecurVal)) {
+    EdgeResult = LVILatticeVal::get(VC);
+    return true;
+  }
+
+  // Only simple PHINode with 1 recurring edge and 1 entry
+  if (PN->getNumIncomingValues() != 2)
+    return getEdgeValue(RecurVal, BBFrom, BBTo, EdgeResult, PN);
+
+  auto *RecurInst = dyn_cast<Instruction>(RecurVal);
+  if (!RecurInst)
+    return getEdgeValue(RecurVal, BBFrom, BBTo, EdgeResult, PN);
+
+  // Skip if the range for initalization is not knwon
+  if (!ResultSoFar.isConstantRange())
+    return getEdgeValue(RecurVal, BBFrom, BBTo, EdgeResult, PN);
+
+  switch (RecurInst->getOpcode()) {
+  default:
+    return getEdgeValue(RecurVal, BBFrom, BBTo, EdgeResult, PN);
+  case Instruction::Add: {
+    // Calculate the local result without poluting the cache, we want to get a
+    // upper bound based on the the branch condition
+    LVILatticeVal LocalResult;
+    if (!getEdgeValueLocal(RecurInst, BBFrom, BBTo, LocalResult))
+      return getEdgeValue(RecurVal, BBFrom, BBTo, EdgeResult, PN);
+
+    if (!LocalResult.isConstantRange() || !MatchIncreasedByOne(PN, RecurInst))
+      return getEdgeValue(RecurVal, BBFrom, BBTo, EdgeResult, PN);
+
+    auto EdgeRange = LocalResult.getConstantRange();
+    auto InitRange = ResultSoFar.getConstantRange();
+    if (!EdgeRange.contains(InitRange))
+      return getEdgeValue(RecurVal, BBFrom, BBTo, EdgeResult, PN);
+
+    // This is correct even if the set wrap around
+    EdgeResult = LVILatticeVal::getRange(
+        ConstantRange(InitRange.getLower(), EdgeRange.getUpper()));
+
+    return true;
+  }
+  case Instruction::Select: {
+    // Handle recurrence with select for linear search pattern:
+    // %tmp86 = phi i32[1, %bb73], [%tmp95, %bb85]
+    // %tmp87 = phi i32[0, %bb73], [%tmp94, %bb85]
+    // %tmp94 = select i1 %tmp91, i32 %tmp86, i32 %tmp87
+    // %tmp95 = add nsw i32 %tmp86, 1
+    // % tmp96 = icmp slt i32 %tmp95, 20
+    // br i1 %tmp96, label %bb85, label %bb97
+    //
+    // In this case, R(%tmp94) = R(%tmp86) U R(%tmp87)
+    // =>  R(%tmp94) = R(%tmp86) U R(%tmp94) U R(0)
+    // =>  R(%tmp94) = R(%tmp86) U R(%tmp86) U R(%tmp87) U R(0)
+    // =>  R(%tmp94) = R(%tmp86) U R(%tmp86) U ... U R(0)
+    //
+
+    Value *Incoming;
+    if (!MatchSelectRecurrence(PN, cast<SelectInst>(RecurInst), Incoming))
+      return getEdgeValue(RecurVal, BBFrom, BBTo, EdgeResult, PN);
+
+    if (!getEdgeValue(Incoming, BBFrom, BBTo, EdgeResult, PN))
+      return false;
+
+    EdgeResult.mergeIn(ResultSoFar, DL);
+    return true;
+  }
+  }
+}
+
 /// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at
 /// the basic block if the edge does not constrain Val.
 bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
                                       BasicBlock *BBTo, LVILatticeVal &Result,
                                       Instruction *CxtI) {
   // If already a constant, there is nothing to compute.
   if (Constant *VC = dyn_cast<Constant>(Val)) {
     Result = LVILatticeVal::get(VC);
bool LazyValueInfoWrapperPass::runOnFunction(Function &F) {
   // Fully lazy.
   return false;
 }
 
 void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequired<AssumptionCacheTracker>();
   AU.addRequired<TargetLibraryInfoWrapperPass>();
+  AU.addUsedIfAvailable<DominatorTreeWrapperPass>();
 }
 
 LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; }
 
 LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
 
 void LazyValueInfo::releaseMemory() {
   // If the cache was allocated, free it.