From aaea24802bf5de0420f1ef5f3660a9765e23dea8 Mon Sep 17 00:00:00 2001 From: Philip Reames Date: Thu, 21 Nov 2019 10:44:13 -0800 Subject: Broaden the definition of a "widenable branch" As a reminder, a "widenable branch" is the pattern "br i1 (and i1 X, WC()), label %taken, label %untaken" where "WC" is the widenable condition intrinsics. The semantics of such a branch (derived from the semantics of WC) is that a new condition can be added into the condition arbitrarily without violating legality. Broaden the definition in two ways: Allow swapped operands to the br (and X, WC()) form Allow widenable branch w/trivial condition (i.e. true) which takes form of br i1 WC() The former is just general robustness (e.g. for X = non-instruction this is what instcombine produces). The later is specifically important as partial unswitching of a widenable range check produces exactly this form above the loop. Differential Revision: https://reviews.llvm.org/D70502 --- llvm/lib/Analysis/GuardUtils.cpp | 34 +++++++++++++------ llvm/lib/Transforms/Scalar/GuardWidening.cpp | 11 +++--- llvm/lib/Transforms/Utils/GuardUtils.cpp | 50 ++++++++++++++++++++++------ 3 files changed, 69 insertions(+), 26 deletions(-) (limited to 'llvm/lib') diff --git a/llvm/lib/Analysis/GuardUtils.cpp b/llvm/lib/Analysis/GuardUtils.cpp index 6dc2b740ac9..d4a86e18997 100644 --- a/llvm/lib/Analysis/GuardUtils.cpp +++ b/llvm/lib/Analysis/GuardUtils.cpp @@ -13,9 +13,9 @@ #include "llvm/IR/PatternMatch.h" using namespace llvm; +using namespace llvm::PatternMatch; bool llvm::isGuard(const User *U) { - using namespace llvm::PatternMatch; return match(U, m_Intrinsic()); } @@ -32,7 +32,6 @@ bool llvm::isGuardAsWidenableBranch(const User *U) { if (!parseWidenableBranch(U, Condition, WidenableCondition, GuardedBB, DeoptBB)) return false; - using namespace llvm::PatternMatch; for (auto &Insn : *DeoptBB) { if (match(&Insn, m_Intrinsic())) return true; @@ -45,17 +44,32 @@ bool llvm::isGuardAsWidenableBranch(const User *U) { bool llvm::parseWidenableBranch(const User *U, Value *&Condition, Value *&WidenableCondition, BasicBlock *&IfTrueBB, BasicBlock *&IfFalseBB) { - using namespace llvm::PatternMatch; + if (match(U, m_Br(m_Intrinsic(), + IfTrueBB, IfFalseBB)) && + cast(U)->getCondition()->hasOneUse()) { + WidenableCondition = cast(U)->getCondition(); + Condition = ConstantInt::getTrue(IfTrueBB->getContext()); + return true; + } + + // Check for two cases: + // 1) br (i1 (and A, WC())), label %IfTrue, label %IfFalse + // 2) br (i1 (and WC(), B)), label %IfTrue, label %IfFalse + // We do not check for more generalized and trees as we should canonicalize + // to the form above in instcombine. (TODO) if (!match(U, m_Br(m_And(m_Value(Condition), m_Value(WidenableCondition)), IfTrueBB, IfFalseBB))) return false; + if (!match(WidenableCondition, + m_Intrinsic())) { + if (!match(Condition, + m_Intrinsic())) + return false; + std::swap(Condition, WidenableCondition); + } + // For the branch to be (easily) widenable, it must not correlate with other // branches. Thus, the widenable condition must have a single use. - if (!WidenableCondition->hasOneUse() || - !cast(U)->getCondition()->hasOneUse()) - return false; - // TODO: At the moment, we only recognize the branch if the WC call in this - // specific position. We should generalize! - return match(WidenableCondition, - m_Intrinsic()); + return (WidenableCondition->hasOneUse() && + cast(U)->getCondition()->hasOneUse()); } diff --git a/llvm/lib/Transforms/Scalar/GuardWidening.cpp b/llvm/lib/Transforms/Scalar/GuardWidening.cpp index 69d9507b356..a3eba27a4d9 100644 --- a/llvm/lib/Transforms/Scalar/GuardWidening.cpp +++ b/llvm/lib/Transforms/Scalar/GuardWidening.cpp @@ -84,15 +84,16 @@ static Value *getCondition(Instruction *I) { "Bad guard intrinsic?"); return GI->getArgOperand(0); } - if (isGuardAsWidenableBranch(I)) { - auto *Cond = cast(I)->getCondition(); - return cast(Cond)->getOperand(0); - } + Value *Cond, *WC; + BasicBlock *IfTrueBB, *IfFalseBB; + if (parseWidenableBranch(I, Cond, WC, IfTrueBB, IfFalseBB)) + return Cond; + return cast(I)->getCondition(); } // Set the condition for \p I to \p NewCond. \p I can either be a guard or a -// conditional branch. +// conditional branch. static void setCondition(Instruction *I, Value *NewCond) { if (IntrinsicInst *GI = dyn_cast(I)) { assert(GI->getIntrinsicID() == Intrinsic::experimental_guard && diff --git a/llvm/lib/Transforms/Utils/GuardUtils.cpp b/llvm/lib/Transforms/Utils/GuardUtils.cpp index b8c4c764e74..241bfbf80bd 100644 --- a/llvm/lib/Transforms/Utils/GuardUtils.cpp +++ b/llvm/lib/Transforms/Utils/GuardUtils.cpp @@ -15,10 +15,12 @@ #include "llvm/IR/IRBuilder.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/MDBuilder.h" +#include "llvm/IR/PatternMatch.h" #include "llvm/Support/CommandLine.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" using namespace llvm; +using namespace llvm::PatternMatch; static cl::opt PredicatePassBranchWeight( "guards-predicate-pass-branch-weight", cl::Hidden, cl::init(1 << 20), @@ -80,23 +82,49 @@ void llvm::makeGuardControlFlowExplicit(Function *DeoptIntrinsic, void llvm::widenWidenableBranch(BranchInst *WidenableBR, Value *NewCond) { assert(isWidenableBranch(WidenableBR) && "precondition"); - Instruction *WCAnd = cast(WidenableBR->getCondition()); - // Condition is only guaranteed to dominate branch - WCAnd->moveBefore(WidenableBR); - Value *OldCond = WCAnd->getOperand(0); - IRBuilder<> B(WCAnd); - WCAnd->setOperand(0, B.CreateAnd(NewCond, OldCond)); + // The tempting trivially option is to produce something like this: + // br (and oldcond, newcond) where oldcond is assumed to contain a widenable + // condition, but that doesn't match the pattern parseWidenableBranch expects + // so we have to be more sophisticated. + if (match(WidenableBR->getCondition(), + m_Intrinsic())) { + IRBuilder<> B(WidenableBR); + WidenableBR->setCondition(B.CreateAnd(NewCond, + WidenableBR->getCondition())); + } else { + Instruction *WCAnd = cast(WidenableBR->getCondition()); + // Condition is only guaranteed to dominate branch + WCAnd->moveBefore(WidenableBR); + IRBuilder<> B(WCAnd); + const bool Op0IsWC = + match(WCAnd->getOperand(0), + m_Intrinsic()); + const unsigned CondOpIdx = Op0IsWC ? 1 : 0; + Value *OldCond = WCAnd->getOperand(CondOpIdx); + NewCond = B.CreateAnd(NewCond, OldCond); + WCAnd->setOperand(CondOpIdx, NewCond); + } assert(isWidenableBranch(WidenableBR) && "preserve widenabiliy"); } void llvm::setWidenableBranchCond(BranchInst *WidenableBR, Value *NewCond) { assert(isWidenableBranch(WidenableBR) && "precondition"); - Instruction *WCAnd = cast(WidenableBR->getCondition()); - // Condition is only guaranteed to dominate branch - WCAnd->moveBefore(WidenableBR); - WCAnd->setOperand(0, NewCond); - + if (match(WidenableBR->getCondition(), + m_Intrinsic())) { + IRBuilder<> B(WidenableBR); + WidenableBR->setCondition(B.CreateAnd(NewCond, + WidenableBR->getCondition())); + } else { + Instruction *WCAnd = cast(WidenableBR->getCondition()); + // Condition is only guaranteed to dominate branch + WCAnd->moveBefore(WidenableBR); + const bool Op0IsWC = + match(WCAnd->getOperand(0), + m_Intrinsic()); + const unsigned CondOpIdx = Op0IsWC ? 1 : 0; + WCAnd->setOperand(CondOpIdx, NewCond); + } assert(isWidenableBranch(WidenableBR) && "preserve widenabiliy"); } -- cgit v1.2.3