Index: llvm/include/llvm/Analysis/GuardUtils.h =================================================================== --- llvm/include/llvm/Analysis/GuardUtils.h +++ 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 Index: llvm/lib/Analysis/GuardUtils.cpp =================================================================== --- llvm/lib/Analysis/GuardUtils.cpp +++ 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,36 @@ } 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; + } + if (!Callback(Check)) + break; + } 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) -> bool { + if (!isWidenableCondition(Check)) + Checks.push_back(Check); + return true; + }); +} Index: llvm/lib/Transforms/Scalar/LoopPredication.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LoopPredication.cpp +++ 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,69 +754,37 @@ } } -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; } -bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard, - SCEVExpander &Expander) { +static SmallVector extractChecksFromGuard(Instruction *Guard) { LLVM_DEBUG(dbgs() << "Processing guard:\n"); LLVM_DEBUG(Guard->dump()); - TotalConsidered++; SmallVector Checks; - unsigned NumWidened = collectChecks(Checks, Guard->getOperand(0), Expander, - Guard); + parseWidenableGuard(Guard, Checks); + LLVM_DEBUG(dbgs() << "Found checks:\n"); + std::for_each(Checks.begin(), Checks.end(), [](const Value *Check) { + LLVM_DEBUG(dbgs() << *Check << "\n"); + }); + return Checks; +} + +bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard, + SCEVExpander &Expander) { + TotalConsidered++; + auto Checks = extractChecksFromGuard(Guard); + unsigned NumWidened = widenChecks(Checks, Expander, Guard); if (NumWidened == 0) return false; @@ -840,9 +808,6 @@ bool LoopPredication::widenWidenableBranchGuardConditions( BranchInst *BI, SCEVExpander &Expander) { assert(isGuardAsWidenableBranch(BI) && "Must be!"); - LLVM_DEBUG(dbgs() << "Processing guard:\n"); - LLVM_DEBUG(BI->dump()); - Value *Cond, *WC; BasicBlock *IfTrueBB, *IfFalseBB; bool Parsed = parseWidenableBranch(BI, Cond, WC, IfTrueBB, IfFalseBB); @@ -850,9 +815,11 @@ (void)Parsed; TotalConsidered++; - SmallVector Checks; - unsigned NumWidened = collectChecks(Checks, BI->getCondition(), - Expander, BI); + auto Checks = extractChecksFromGuard(BI); + // 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; Index: llvm/test/Transforms/LoopPredication/visited.ll =================================================================== --- llvm/test/Transforms/LoopPredication/visited.ll +++ llvm/test/Transforms/LoopPredication/visited.ll @@ -1,10 +1,15 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -S -passes=loop-predication < %s 2>&1 | FileCheck %s -; RUN: opt -S -passes='require,loop-mssa(loop-predication)' -verify-memoryssa < %s 2>&1 | FileCheck %s +; RUN: opt -S -passes=loop-predication -debug-only=loop-predication < %s 2>&1 | FileCheck %s +; RUN: opt -S -passes='require,loop-mssa(loop-predication)' -verify-memoryssa -debug-only=loop-predication < %s 2>&1 | FileCheck %s +; REQUIRES: asserts declare void @llvm.experimental.guard(i1, ...) define i32 @test_visited(ptr %array, i32 %length, i32 %n, i32 %x) { +; CHECK: Found checks: +; CHECK-NEXT: %unrelated.cond = icmp eq i32 %x, %i +; CHECK-NEXT: %within.bounds = icmp ult i32 %i, %length +; ; CHECK-LABEL: @test_visited( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[TMP5:%.*]] = icmp eq i32 [[N:%.*]], 0