[NFC][LoopPredication] Extract guard parsing to GuardUtils

[aleksandr.popov]

Summary

Extract logic of parsing guards and widenable branches in order to reuse
it in the GuardWidening

[anna]

llvm/lib/Analysis/GuardUtils.cpp

121

Pls leave default value for SmallVector (i.e. SmallVector<Value *> Worklist = {Condition};). If we happen to have more than 4 conditions, we end up resizing.

123

You can delay adding Condition into Visited and make this entire loop as:

do {
    Value *Check = Worklist.pop_back_val();
     if (!Visited.insert(Check).second)
       continue;
    Value *LHS, *RHS;
    if (match(Check, m_And(m_Value(LHS), m_Value(RHS)))) {
        Worklist.push_back(LHS);
        Worklist.push_back(RHS);
      continue;
    }
    if (!Callback(Check))
      break;
  } while (!Worklist.empty());

145

This always returns true. Why do you need a templated function for parseCondition in this patch? I'd suggest the non-templated version and once you add support for parsing it in GuardWidening, we can see if we need a templated version or not.

llvm/lib/Transforms/Scalar/LoopPredication.cpp

778

Pls land this and the added debug statement in the test separately (can land without review), since it is unrelated to patch.

[aleksandr.popov]

llvm/lib/Analysis/GuardUtils.cpp

123

Do you mind if I do that refactoring in the next separate patch?
I've intended just to extract logic from LoopPredication::collectChecks and move it here straightforwardly.

145

Yep, returning true was change in advance. I'll turn callback's type into void.
The reason why I need templated function for parseCondition - is an intent to separate condition parsing and checks collecting.
So in the parseCondition I just want to parse the condition while in the parseWidenableGuard I want to make a decision whether to add check in the resulting list or not (in case if it's widenable-condition)

llvm/lib/Transforms/Scalar/LoopPredication.cpp

778

Ok, will do it in the separate patch, thanks!

[aleksandr.popov]

llvm/lib/Analysis/GuardUtils.cpp

123

https://reviews.llvm.org/D157490

llvm/lib/Transforms/Scalar/LoopPredication.cpp

778

https://reviews.llvm.org/D157490

[anna]

llvm/lib/Analysis/GuardUtils.cpp

145

had a chat with Aleksandr offline. The need for the template arises because a later patch will use the same logic but with a different Callback function (which will be modified to return a bool).

llvm/include/llvm/Analysis/GuardUtils.h

 #define LLVM_ANALYSIS_GUARDUTILS_H
 
 namespace llvm {
 
 class BasicBlock;
 class Use;
 class User;
 class Value;
+template <typename T> class SmallVectorImpl;
 
 /// Returns true iff \p U has semantics of a guard expressed in a form of call
 /// of llvm.experimental.guard intrinsic.
 bool isGuard(const User *U);
 
+/// Returns true iff \p V has semantics of llvm.experimental.widenable.condition
+/// call
+bool isWidenableCondition(const Value *V);
+
 /// Returns true iff \p U is a widenable branch (that is, parseWidenableBranch
 /// returns true).
 bool isWidenableBranch(const User *U);
 
 /// Returns true iff \p U has semantics of a guard expressed in a form of a
 /// widenable conditional branch to deopt block.
 bool isGuardAsWidenableBranch(const User *U);
 

 bool parseWidenableBranch(const User *U, Value *&Condition,
                           Value *&WidenableCondition, BasicBlock *&IfTrueBB,
                           BasicBlock *&IfFalseBB);
 
 /// Analgous to the above, but return the Uses so that that they can be
 /// modified. Unlike previous version, Condition is optional and may be null.
 bool parseWidenableBranch(User *U, Use *&Cond, Use *&WC, BasicBlock *&IfTrueBB,
                           BasicBlock *&IfFalseBB);
-  
+// The guard condition is expected to be in form of:
+//   cond1 && cond2 && cond3 ...
+// or in case of widenable branch:
+//   cond1 && cond2 && cond3 && widenable_contidion ...
+// Method collects the list of checks, but skips widenable_condition.
+void parseWidenableGuard(const User *U, llvm::SmallVectorImpl<Value *> &Checks);
 } // llvm
 
 #endif // LLVM_ANALYSIS_GUARDUTILS_H

llvm/lib/Analysis/GuardUtils.cpp

 
 using namespace llvm;
 using namespace llvm::PatternMatch;
 
 bool llvm::isGuard(const User *U) {
   return match(U, m_Intrinsic<Intrinsic::experimental_guard>());
 }
 
+bool llvm::isWidenableCondition(const Value *V) {
+  return match(V, m_Intrinsic<Intrinsic::experimental_widenable_condition>());
+}
+
 bool llvm::isWidenableBranch(const User *U) {
   Value *Condition, *WidenableCondition;
   BasicBlock *GuardedBB, *DeoptBB;
   return parseWidenableBranch(U, Condition, WidenableCondition, GuardedBB,
                               DeoptBB);
 }
 
 bool llvm::isGuardAsWidenableBranch(const User *U) {
bool llvm::parseWidenableBranch(User *U, Use *&C,Use *&WC,
   if (match(B, m_Intrinsic<Intrinsic::experimental_widenable_condition>()) &&
       B->hasOneUse()) {
     WC = &And->getOperandUse(1);
     C = &And->getOperandUse(0);
     return true;
   }
   return false;
 }
+
+template <typename CallbackType>
+static void parseCondition(Value *Condition, CallbackType Callback) {
+  SmallVector<Value *, 4> Worklist(1, Condition);
+  SmallPtrSet<Value *, 4> Visited;
+  Visited.insert(Condition);
+  do {
+    Value *Check = Worklist.pop_back_val();
+    Value *LHS, *RHS;
+    if (match(Check, m_And(m_Value(LHS), m_Value(RHS)))) {
+      if (Visited.insert(LHS).second)
+        Worklist.push_back(LHS);
+      if (Visited.insert(RHS).second)
+        Worklist.push_back(RHS);
+      continue;
+    }
+    Callback(Check);
+  } while (!Worklist.empty());
+}
+
+void llvm::parseWidenableGuard(const User *U,
+                               llvm::SmallVectorImpl<Value *> &Checks) {
+  assert((isGuard(U) || isWidenableBranch(U)) && "Should be");
+  Value *Condition = isGuard(U) ? cast<IntrinsicInst>(U)->getArgOperand(0)
+                                : cast<BranchInst>(U)->getCondition();
+
+  parseCondition(Condition, [&](Value *Check) {
+    if (!isWidenableCondition(Check))
+      Checks.push_back(Check);
+  });
+}

llvm/lib/Transforms/Scalar/LoopPredication.cpp

class LoopPredication {
   std::optional<Value *>
   widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck, LoopICmp RangeCheck,
                                       SCEVExpander &Expander,
                                       Instruction *Guard);
   std::optional<Value *>
   widenICmpRangeCheckDecrementingLoop(LoopICmp LatchCheck, LoopICmp RangeCheck,
                                       SCEVExpander &Expander,
                                       Instruction *Guard);
-  unsigned collectChecks(SmallVectorImpl<Value *> &Checks, Value *Condition,
-                         SCEVExpander &Expander, Instruction *Guard);
+  unsigned widenChecks(SmallVectorImpl<Value *> &Checks, SCEVExpander &Expander,
+                       Instruction *Guard);
   bool widenGuardConditions(IntrinsicInst *II, SCEVExpander &Expander);
   bool widenWidenableBranchGuardConditions(BranchInst *Guard, SCEVExpander &Expander);
   // If the loop always exits through another block in the loop, we should not
   // predicate based on the latch check. For example, the latch check can be a
   // very coarse grained check and there can be more fine grained exit checks
   // within the loop.
   bool isLoopProfitableToPredicate();
 
return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck,
                                                Expander, Guard);
   else {
     assert(Step->isAllOnesValue() && "Step should be -1!");
     return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck,
                                                Expander, Guard);
   }
 }
 
-unsigned LoopPredication::collectChecks(SmallVectorImpl<Value *> &Checks,
-                                        Value *Condition,
-                                        SCEVExpander &Expander,
-                                        Instruction *Guard) {
+unsigned LoopPredication::widenChecks(SmallVectorImpl<Value *> &Checks,
   unsigned NumWidened = 0;
-  // The guard condition is expected to be in form of:
-  //   cond1 && cond2 && cond3 ...
-  // Iterate over subconditions looking for icmp conditions which can be
-  // widened across loop iterations. Widening these conditions remember the
-  // resulting list of subconditions in Checks vector.
-  SmallVector<Value *, 4> Worklist(1, Condition);
-  SmallPtrSet<Value *, 4> Visited;
-  Visited.insert(Condition);
-  Value *WideableCond = nullptr;
-  do {
-    Value *Condition = Worklist.pop_back_val();
-    Value *LHS, *RHS;
-    using namespace llvm::PatternMatch;
-    if (match(Condition, m_And(m_Value(LHS), m_Value(RHS)))) {
-      if (Visited.insert(LHS).second)
-        Worklist.push_back(LHS);
-      if (Visited.insert(RHS).second)
-        Worklist.push_back(RHS);
-      continue;
-    }
-
-    if (match(Condition,
-              m_Intrinsic<Intrinsic::experimental_widenable_condition>())) {
-      // Pick any, we don't care which
-      WideableCond = Condition;
-      continue;
-    }
-
-    if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
-      if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander,
-                                                   Guard)) {
-        Checks.push_back(*NewRangeCheck);
+  for (auto &Check : Checks)
+    if (ICmpInst *ICI = dyn_cast<ICmpInst>(Check))
+      if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander, Guard)) {
         NumWidened++;
-        continue;
-      }
+        Check = *NewRangeCheck;
       }
-
-    // Save the condition as is if we can't widen it
-    Checks.push_back(Condition);
-  } while (!Worklist.empty());
-  // At the moment, our matching logic for wideable conditions implicitly
-  // assumes we preserve the form: (br (and Cond, WC())).  FIXME
-  // Note that if there were multiple calls to wideable condition in the
-  // traversal, we only need to keep one, and which one is arbitrary.
-  if (WideableCond)
-    Checks.push_back(WideableCond);
   return NumWidened;
 }
 
 bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard,
                                            SCEVExpander &Expander) {
   LLVM_DEBUG(dbgs() << "Processing guard:\n");
   LLVM_DEBUG(Guard->dump());
 
   TotalConsidered++;
   SmallVector<Value *, 4> Checks;
-  unsigned NumWidened = collectChecks(Checks, Guard->getOperand(0), Expander,
-                                      Guard);
+  parseWidenableGuard(Guard, Checks);
+  unsigned NumWidened = widenChecks(Checks, Expander, Guard);
   if (NumWidened == 0)
     return false;
 
   TotalWidened += NumWidened;
 
   // Emit the new guard condition
   IRBuilder<> Builder(findInsertPt(Guard, Checks));
   Value *AllChecks = Builder.CreateAnd(Checks);
bool LoopPredication::widenWidenableBranchGuardConditions(
   Value *Cond, *WC;
   BasicBlock *IfTrueBB, *IfFalseBB;
   bool Parsed = parseWidenableBranch(BI, Cond, WC, IfTrueBB, IfFalseBB);
   assert(Parsed && "Must be able to parse widenable branch");
   (void)Parsed;
 
   TotalConsidered++;
   SmallVector<Value *, 4> Checks;
-  unsigned NumWidened = collectChecks(Checks, BI->getCondition(),
-                                      Expander, BI);
+  parseWidenableGuard(BI, Checks);
+  // At the moment, our matching logic for wideable conditions implicitly
+  // assumes we preserve the form: (br (and Cond, WC())).  FIXME
+  Checks.push_back(WC);
+  unsigned NumWidened = widenChecks(Checks, Expander, BI);
   if (NumWidened == 0)
     return false;
 
   TotalWidened += NumWidened;
 
   // Emit the new guard condition
   IRBuilder<> Builder(findInsertPt(BI, Checks));
   Value *AllChecks = Builder.CreateAnd(Checks);