diff --git a/llvm/include/llvm/Analysis/GuardUtils.h b/llvm/include/llvm/Analysis/GuardUtils.h --- a/llvm/include/llvm/Analysis/GuardUtils.h +++ b/llvm/include/llvm/Analysis/GuardUtils.h @@ -18,11 +18,16 @@ class Use; class User; class Value; +template 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); @@ -48,7 +53,13 @@ /// 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 &Checks); } // llvm #endif // LLVM_ANALYSIS_GUARDUTILS_H diff --git a/llvm/lib/Analysis/GuardUtils.cpp b/llvm/lib/Analysis/GuardUtils.cpp --- a/llvm/lib/Analysis/GuardUtils.cpp +++ b/llvm/lib/Analysis/GuardUtils.cpp @@ -19,6 +19,10 @@ return match(U, m_Intrinsic()); } +bool llvm::isWidenableCondition(const Value *V) { + return match(V, m_Intrinsic()); +} + bool llvm::isWidenableBranch(const User *U) { Value *Condition, *WidenableCondition; BasicBlock *GuardedBB, *DeoptBB; @@ -111,3 +115,34 @@ } return false; } + +template +static void parseCondition(Value *Condition, CallbackType Callback) { + SmallVector Worklist(1, Condition); + SmallPtrSet 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 &Checks) { + assert((isGuard(U) || isWidenableBranch(U)) && "Should be"); + Value *Condition = isGuard(U) ? cast(U)->getArgOperand(0) + : cast(U)->getCondition(); + + parseCondition(Condition, [&](Value *Check) { + if (!isWidenableCondition(Check)) + Checks.push_back(Check); + }); +} diff --git a/llvm/lib/Transforms/Scalar/LoopPredication.cpp b/llvm/lib/Transforms/Scalar/LoopPredication.cpp --- a/llvm/lib/Transforms/Scalar/LoopPredication.cpp +++ b/llvm/lib/Transforms/Scalar/LoopPredication.cpp @@ -307,8 +307,8 @@ widenICmpRangeCheckDecrementingLoop(LoopICmp LatchCheck, LoopICmp RangeCheck, SCEVExpander &Expander, Instruction *Guard); - unsigned collectChecks(SmallVectorImpl &Checks, Value *Condition, - SCEVExpander &Expander, Instruction *Guard); + unsigned widenChecks(SmallVectorImpl &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 @@ -754,57 +754,16 @@ } } -unsigned LoopPredication::collectChecks(SmallVectorImpl &Checks, - Value *Condition, - SCEVExpander &Expander, - Instruction *Guard) { +unsigned LoopPredication::widenChecks(SmallVectorImpl &Checks, + SCEVExpander &Expander, + Instruction *Guard) { 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 Worklist(1, Condition); - SmallPtrSet 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())) { - // Pick any, we don't care which - WideableCond = Condition; - continue; - } - - if (ICmpInst *ICI = dyn_cast(Condition)) { - if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander, - Guard)) { - Checks.push_back(*NewRangeCheck); + for (auto &Check : Checks) + if (ICmpInst *ICI = dyn_cast(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; } @@ -815,8 +774,8 @@ TotalConsidered++; SmallVector Checks; - unsigned NumWidened = collectChecks(Checks, Guard->getOperand(0), Expander, - Guard); + parseWidenableGuard(Guard, Checks); + unsigned NumWidened = widenChecks(Checks, Expander, Guard); if (NumWidened == 0) return false; @@ -851,8 +810,11 @@ TotalConsidered++; SmallVector 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;