#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Target/TargetLibraryInfo.h"
-
using namespace llvm;
using namespace PatternMatch;
APInt AP1 = CI1->getValue();
APInt AP2 = CI2->getValue();
- if (!AP1) {
- if (!AP2) {
- // Both Constants are 0.
- return getConstant(true);
- }
-
- if (cast<BinaryOperator>(Op)->isExact())
- return getConstant(false);
-
- if (AP2.isNegative()) {
- // MSB is set, so a lshr with a large enough 'A' would be undefined.
- return getConstant(false);
- }
+ // Don't bother doing any work for cases which InstSimplify handles.
+ if (AP2 == 0)
+ return nullptr;
+ bool IsAShr = isa<AShrOperator>(Op);
+ if (IsAShr) {
+ if (AP2.isAllOnesValue())
+ return nullptr;
+ if (AP2.isNegative() != AP1.isNegative())
+ return nullptr;
+ if (AP2.sgt(AP1))
+ return nullptr;
+ }
+ if (!AP1)
// 'A' must be large enough to shift out the highest set bit.
return getICmp(I.ICMP_UGT, A,
ConstantInt::get(A->getType(), AP2.logBase2()));
- }
-
- if (!AP2) {
- // Shifting 0 by any value gives 0.
- return getConstant(false);
- }
- bool IsAShr = isa<AShrOperator>(Op);
- if (AP1 == AP2) {
- if (AP1.isAllOnesValue() && IsAShr) {
- // Arithmatic shift of -1 is always -1.
- return getConstant(true);
- }
+ if (AP1 == AP2)
return getICmp(I.ICMP_EQ, A, ConstantInt::getNullValue(A->getType()));
- }
-
- bool IsNegative = false;
- if (IsAShr) {
- if (AP1.isNegative() != AP2.isNegative()) {
- // Arithmetic shift will never change the sign.
- return getConstant(false);
- }
- // Both the constants are negative, take their positive to calculate log.
- if (AP1.isNegative()) {
- if (AP1.slt(AP2))
- // Right-shifting won't increase the magnitude.
- return getConstant(false);
- IsNegative = true;
- }
- }
-
- if (!IsNegative && AP1.ugt(AP2))
- // Right-shifting will not increase the value.
- return getConstant(false);
// Get the distance between the highest bit that's set.
int Shift;
- if (IsNegative)
- Shift = (-AP2).logBase2() - (-AP1).logBase2();
+ // Both the constants are negative, take their positive to calculate log.
+ if (IsAShr && AP1.isNegative())
+ // Get the ones' complement of AP2 and AP1 when computing the distance.
+ Shift = (~AP2).logBase2() - (~AP1).logBase2();
else
Shift = AP2.logBase2() - AP1.logBase2();
- if (IsAShr ? AP1 == AP2.ashr(Shift) : AP1 == AP2.lshr(Shift))
+ if (Shift > 0) {
+ if (IsAShr ? AP1 == AP2.ashr(Shift) : AP1 == AP2.lshr(Shift))
+ return getICmp(I.ICMP_EQ, A, ConstantInt::get(A->getType(), Shift));
+ }
+ // Shifting const2 will never be equal to const1.
+ return getConstant(false);
+}
+
+/// FoldICmpCstShlCst - Handle "(icmp eq/ne (shl const2, A), const1)" ->
+/// (icmp eq/ne A, TrailingZeros(const1) - TrailingZeros(const2)).
+Instruction *InstCombiner::FoldICmpCstShlCst(ICmpInst &I, Value *Op, Value *A,
+ ConstantInt *CI1,
+ ConstantInt *CI2) {
+ assert(I.isEquality() && "Cannot fold icmp gt/lt");
+
+ auto getConstant = [&I, this](bool IsTrue) {
+ if (I.getPredicate() == I.ICMP_NE)
+ IsTrue = !IsTrue;
+ return ReplaceInstUsesWith(I, ConstantInt::get(I.getType(), IsTrue));
+ };
+
+ auto getICmp = [&I](CmpInst::Predicate Pred, Value *LHS, Value *RHS) {
+ if (I.getPredicate() == I.ICMP_NE)
+ Pred = CmpInst::getInversePredicate(Pred);
+ return new ICmpInst(Pred, LHS, RHS);
+ };
+
+ APInt AP1 = CI1->getValue();
+ APInt AP2 = CI2->getValue();
+
+ // Don't bother doing any work for cases which InstSimplify handles.
+ if (AP2 == 0)
+ return nullptr;
+
+ unsigned AP2TrailingZeros = AP2.countTrailingZeros();
+
+ if (!AP1 && AP2TrailingZeros != 0)
+ return getICmp(I.ICMP_UGE, A,
+ ConstantInt::get(A->getType(), AP2.getBitWidth() - AP2TrailingZeros));
+
+ if (AP1 == AP2)
+ return getICmp(I.ICMP_EQ, A, ConstantInt::getNullValue(A->getType()));
+
+ // Get the distance between the lowest bits that are set.
+ int Shift = AP1.countTrailingZeros() - AP2TrailingZeros;
+
+ if (Shift > 0 && AP2.shl(Shift) == AP1)
return getICmp(I.ICMP_EQ, A, ConstantInt::get(A->getType(), Shift));
// Shifting const2 will never be equal to const1.
return GlobalSwapBenefits > 0;
}
-/// \brief Check that one use is in the same block as the definition and all
-/// other uses are in blocks dominated by a given block
-///
-/// \param DI Definition
-/// \param UI Use
-/// \param DB Block that must dominate all uses of \p DI outside
-/// the parent block
-/// \return true when \p UI is the only use of \p DI in the parent block
-/// and all other uses of \p DI are in blocks dominated by \p DB.
-///
-bool InstCombiner::dominatesAllUses(const Instruction *DI,
- const Instruction *UI,
- const BasicBlock *DB) const {
- assert(DI && UI && "Instruction not defined\n");
- if (DI->getParent() != UI->getParent())
- return false;
- // DominatorTree available?
- if (!DT)
- return false;
- for (const User *U : DI->users()) {
- auto *Usr = cast<Instruction>(U);
- if (Usr != UI && !DT->dominates(DB, Usr->getParent()))
- return false;
- }
- return true;
-}
-
-///
-/// true when the instruction sequence within a block is select-cmp-br.
-///
-static bool isChainSelectCmpBranch(const SelectInst *SI) {
- const BasicBlock *BB = SI->getParent();
- if (!BB)
- return false;
- auto *BI = dyn_cast_or_null<BranchInst>(BB->getTerminator());
- if (!BI || BI->getNumSuccessors() != 2)
- return false;
- auto *IC = dyn_cast<ICmpInst>(BI->getCondition());
- if (!IC || (IC->getOperand(0) != SI && IC->getOperand(1) != SI))
- return false;
- return true;
-}
-
-///
-/// \brief True when a select result is replaced by one of its operands
-/// in select-icmp sequence. This will eventually result in the elimination
-/// of the select.
-///
-/// \param SI Select instruction
-/// \param Icmp Compare instruction
-/// \param CI1 'true' when first select operand is equal to RHSC of Icmp
-/// \param CI2 'true' when second select operand is equal to RHSC of Icmp
-///
-/// Notes:
-/// - The replacement is global and requires dominator information
-/// - The caller is responsible for the actual replacement
-///
-/// Example:
-///
-/// entry:
-/// %4 = select i1 %3, %C* %0, %C* null
-/// %5 = icmp eq %C* %4, null
-/// br i1 %5, label %9, label %7
-/// ...
-/// ; <label>:7 ; preds = %entry
-/// %8 = getelementptr inbounds %C* %4, i64 0, i32 0
-/// ...
-///
-/// can be transformed to
-///
-/// %5 = icmp eq %C* %0, null
-/// %6 = select i1 %3, i1 %5, i1 true
-/// br i1 %6, label %9, label %7
-/// ...
-/// ; <label>:7 ; preds = %entry
-/// %8 = getelementptr inbounds %C* %0, i64 0, i32 0 // replace by %0!
-///
-/// Similar when the first operand of the select is a constant or/and
-/// the compare is for not equal rather than equal.
-///
-/// FIXME: Currently the function considers equal compares only. It should be
-/// possbile to extend it to not equal compares also.
-///
-bool InstCombiner::replacedSelectWithOperand(SelectInst *SI,
- const ICmpInst *Icmp,
- const ConstantInt *CI1,
- const ConstantInt *CI2) {
- if (isChainSelectCmpBranch(SI) && Icmp->isEquality()) {
- // Code sequence is select - icmp.[eq|ne] - br
- unsigned ReplaceWithOpd = 0;
- if (CI1 && !CI1->isZero())
- // The first constant operand of the select and the RHS of
- // the compare match, so try to substitute
- // the select results with its second operand
- // Example:
- // %4 = select i1 %3, %C* null, %C* %0
- // %5 = icmp eq %C* %4, null
- // ==> could replace select with second operand
- ReplaceWithOpd = 2;
- else if (CI2 && !CI2->isZero())
- // Similar when the second operand of the select is a constant
- // Example:
- // %4 = select i1 %3, %C* %0, %C* null
- // %5 = icmp eq %C* %4, null
- // ==> could replace select with first operand
- ReplaceWithOpd = 1;
- if (ReplaceWithOpd) {
- // Replace select with operand on else path for EQ compares.
- // Replace select with operand on then path for NE compares.
- BasicBlock *Succ =
- Icmp->getPredicate() == ICmpInst::ICMP_EQ
- ? SI->getParent()->getTerminator()->getSuccessor(1)
- : SI->getParent()->getTerminator()->getSuccessor(0);
- if (InstCombiner::dominatesAllUses(SI, Icmp, Succ)) {
- SI->replaceAllUsesWith(SI->getOperand(ReplaceWithOpd));
- return true;
- }
- }
- }
- return false;
-}
-
Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
bool Changed = false;
Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
Builder->getInt(CI->getValue()-1));
}
- // (icmp eq/ne (ashr/lshr const2, A), const1)
if (I.isEquality()) {
ConstantInt *CI2;
if (match(Op0, m_AShr(m_ConstantInt(CI2), m_Value(A))) ||
match(Op0, m_LShr(m_ConstantInt(CI2), m_Value(A)))) {
- return FoldICmpCstShrCst(I, Op0, A, CI, CI2);
+ // (icmp eq/ne (ashr/lshr const2, A), const1)
+ if (Instruction *Inst = FoldICmpCstShrCst(I, Op0, A, CI, CI2))
+ return Inst;
+ }
+ if (match(Op0, m_Shl(m_ConstantInt(CI2), m_Value(A)))) {
+ // (icmp eq/ne (shl const2, A), const1)
+ if (Instruction *Inst = FoldICmpCstShlCst(I, Op0, A, CI, CI2))
+ return Inst;
}
}
// fold to a constant (in which case the icmp is replaced with a select
// which will usually simplify) or this is the only user of the
// select (in which case we are trading a select+icmp for a simpler
- // select+icmp) or all uses of the select can be replaced based on
- // dominance information ("Global cases").
- bool Transform = false;
- if (Op1 && Op2)
- Transform = true;
- else if (Op1 || Op2) {
- if (LHSI->hasOneUse())
- Transform = true;
- else
- // Global cases
- Transform = replacedSelectWithOperand(
- cast<SelectInst>(LHSI), &I, dyn_cast_or_null<ConstantInt>(Op1),
- dyn_cast_or_null<ConstantInt>(Op2));
- }
- if (Transform) {
+ // select+icmp).
+ if ((Op1 && Op2) || (LHSI->hasOneUse() && (Op1 || Op2))) {
if (!Op1)
Op1 = Builder->CreateICmp(I.getPredicate(), LHSI->getOperand(1),
RHSC, I.getName());
projects / oota-llvm.git / blobdiff