[NFC][GuardUtils] Add util to extract widenable conditions

[aleksandr.popov]

Summary

This is the next preparation patch to support widenable conditions
widening instead of branches widening.

We've added parseWidenableGuard util which parses guard condition and
collects all checks existing in the expression tree: D157276

Here we are adding util which walks similar way through the expression
tree but looks up for widenable condition without collecting the checks.
Therefore llvm::extractWidenableCondition could parse widenable branches
with arbitrary position of widenable condition in the expression tree.

llvm::parseWidenableBranch which is we are going to get rid of is being
replaced by llvm::extractWidenableCondition where it's possible.

[anna]

llvm/lib/Analysis/GuardUtils.cpp

133

Can you pls rename Callback to recordCheckOrWidenableCond ?

162

Why do you need the oneUse check here? the extractWidenableCondition API and following patches only talk about extracting widenable condition. Pls move this additional check to the patch where this context applies.

[anna]

LGTM w/ comments.

llvm/lib/Analysis/GuardUtils.cpp

163

llvm/lib/Transforms/Scalar/LoopPredication.cpp

1124 ↗

(On Diff #549299)

[aleksandr.popov]

Rebased

llvm/include/llvm/Analysis/GuardUtils.h

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);
+
+// Returns widenable_condition if it exists in the expression tree rooting from
+// \p U and has only one use.
+Value *extractWidenableCondition(const User *U);
 } // llvm
 
 #endif // LLVM_ANALYSIS_GUARDUTILS_H

llvm/lib/Analysis/GuardUtils.cpp

do {
     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;
     }
-    Callback(Check);
+    if (!Callback(Check))
+      break;
   } 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);
+    return true;
+  });
+}
+
+Value *llvm::extractWidenableCondition(const User *U) {
+  auto *BI = dyn_cast<BranchInst>(U);
+  if (!BI || !BI->isConditional())
+    return nullptr;
+
+  auto Condition = BI->getCondition();
+  if (!Condition->hasOneUse())
+    return nullptr;
+
+  Value *WidenableCondition = nullptr;
+  parseCondition(Condition, [&](Value *Check) {
+    if (isWidenableCondition(Check) && Check->hasOneUse()) {
+      WidenableCondition = Check;
+      return false;
+    }
+    return true;
   });
+  return WidenableCondition;
 }