//
//===----------------------------------------------------------------------===//
-#include "InstCombine.h"
+#include "InstCombineInternal.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/IR/PatternMatch.h"
/// replaced with RepOp.
static Value *SimplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp,
const DataLayout *TD,
- const TargetLibraryInfo *TLI) {
+ const TargetLibraryInfo *TLI,
+ DominatorTree *DT, AssumptionCache *AC) {
// Trivial replacement.
if (V == Op)
return RepOp;
if (CmpInst *C = dyn_cast<CmpInst>(I)) {
if (C->getOperand(0) == Op)
return SimplifyCmpInst(C->getPredicate(), RepOp, C->getOperand(1), TD,
- TLI);
+ TLI, DT, AC);
if (C->getOperand(1) == Op)
return SimplifyCmpInst(C->getPredicate(), C->getOperand(0), RepOp, TD,
- TLI);
+ TLI, DT, AC);
}
// TODO: We could hand off more cases to instsimplify here.
/// 1. The icmp predicate is inverted
/// 2. The select operands are reversed
/// 3. The magnitude of C2 and C1 are flipped
-///
-/// This also tries to turn
-/// --- Single bit tests:
-/// if ((x & C) == 0) x |= C to x |= C
-/// if ((x & C) != 0) x ^= C to x &= ~C
-/// if ((x & C) == 0) x ^= C to x |= C
-/// if ((x & C) != 0) x &= ~C to x &= ~C
-/// if ((x & C) == 0) x &= ~C to nothing
-static Value *foldSelectICmpAndOr(SelectInst &SI, Value *TrueVal,
+static Value *foldSelectICmpAndOr(const SelectInst &SI, Value *TrueVal,
Value *FalseVal,
InstCombiner::BuilderTy *Builder) {
const ICmpInst *IC = dyn_cast<ICmpInst>(SI.getCondition());
return nullptr;
const APInt *C2;
- if (match(TrueVal, m_Specific(X))) {
- // if ((X & C) != 0) X ^= C becomes X &= ~C
- if (match(FalseVal, m_Xor(m_Specific(X), m_APInt(C2))) && C1 == C2)
- return Builder->CreateAnd(X, ~(*C1));
- // if ((X & C) != 0) X &= ~C becomes X &= ~C
- if (match(FalseVal, m_And(m_Specific(X), m_APInt(C2))) && *C1 == ~(*C2))
- return FalseVal;
- } else if (match(FalseVal, m_Specific(X))) {
- // if ((X & C) == 0) X ^= C becomes X |= C
- if (match(TrueVal, m_Xor(m_Specific(X), m_APInt(C2))) && C1 == C2)
- return Builder->CreateOr(X, *C1);
- // if ((X & C) == 0) X &= ~C becomes nothing
- if (match(TrueVal, m_And(m_Specific(X), m_APInt(C2))) && *C1 == ~(*C2))
- return X;
- // if ((X & C) == 0) X |= C becomes X |= C
- if (match(TrueVal, m_Or(m_Specific(X), m_APInt(C2))) && C1 == C2)
- return TrueVal;
- }
-
bool OrOnTrueVal = false;
bool OrOnFalseVal = match(FalseVal, m_Or(m_Specific(TrueVal), m_Power2(C2)));
if (!OrOnFalseVal)
return Builder->CreateOr(V, Y);
}
+/// Attempt to fold a cttz/ctlz followed by a icmp plus select into a single
+/// call to cttz/ctlz with flag 'is_zero_undef' cleared.
+///
+/// For example, we can fold the following code sequence:
+/// \code
+/// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
+/// %1 = icmp ne i32 %x, 0
+/// %2 = select i1 %1, i32 %0, i32 32
+/// \code
+///
+/// into:
+/// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 false)
+static Value *foldSelectCttzCtlz(ICmpInst *ICI, Value *TrueVal, Value *FalseVal,
+ InstCombiner::BuilderTy *Builder) {
+ ICmpInst::Predicate Pred = ICI->getPredicate();
+ Value *CmpLHS = ICI->getOperand(0);
+ Value *CmpRHS = ICI->getOperand(1);
+
+ // Check if the condition value compares a value for equality against zero.
+ if (!ICI->isEquality() || !match(CmpRHS, m_Zero()))
+ return nullptr;
+
+ Value *Count = FalseVal;
+ Value *ValueOnZero = TrueVal;
+ if (Pred == ICmpInst::ICMP_NE)
+ std::swap(Count, ValueOnZero);
+
+ // Skip zero extend/truncate.
+ Value *V = nullptr;
+ if (match(Count, m_ZExt(m_Value(V))) ||
+ match(Count, m_Trunc(m_Value(V))))
+ Count = V;
+
+ // Check if the value propagated on zero is a constant number equal to the
+ // sizeof in bits of 'Count'.
+ unsigned SizeOfInBits = Count->getType()->getScalarSizeInBits();
+ if (!match(ValueOnZero, m_SpecificInt(SizeOfInBits)))
+ return nullptr;
+
+ // Check that 'Count' is a call to intrinsic cttz/ctlz. Also check that the
+ // input to the cttz/ctlz is used as LHS for the compare instruction.
+ if (match(Count, m_Intrinsic<Intrinsic::cttz>(m_Specific(CmpLHS))) ||
+ match(Count, m_Intrinsic<Intrinsic::ctlz>(m_Specific(CmpLHS)))) {
+ IntrinsicInst *II = cast<IntrinsicInst>(Count);
+ IRBuilder<> Builder(II);
+ if (cast<ConstantInt>(II->getArgOperand(1))->isOne()) {
+ // Explicitly clear the 'undef_on_zero' flag.
+ IntrinsicInst *NewI = cast<IntrinsicInst>(II->clone());
+ Type *Ty = NewI->getArgOperand(1)->getType();
+ NewI->setArgOperand(1, Constant::getNullValue(Ty));
+ Builder.Insert(NewI);
+ Count = NewI;
+ }
+
+ return Builder.CreateZExtOrTrunc(Count, ValueOnZero->getType());
+ }
+
+ return nullptr;
+}
+
/// visitSelectInstWithICmp - Visit a SelectInst that has an
/// ICmpInst as its first operand.
///
// arms of the select. See if substituting this value into the arm and
// simplifying the result yields the same value as the other arm.
if (Pred == ICmpInst::ICMP_EQ) {
- if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, DL, TLI) == TrueVal ||
- SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, DL, TLI) == TrueVal)
+ if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, DL, TLI, DT, AC) ==
+ TrueVal ||
+ SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, DL, TLI, DT, AC) ==
+ TrueVal)
return ReplaceInstUsesWith(SI, FalseVal);
- if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, DL, TLI) == FalseVal ||
- SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, DL, TLI) == FalseVal)
+ if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, DL, TLI, DT, AC) ==
+ FalseVal ||
+ SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, DL, TLI, DT, AC) ==
+ FalseVal)
return ReplaceInstUsesWith(SI, FalseVal);
} else if (Pred == ICmpInst::ICMP_NE) {
- if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, DL, TLI) == FalseVal ||
- SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, DL, TLI) == FalseVal)
+ if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, DL, TLI, DT, AC) ==
+ FalseVal ||
+ SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, DL, TLI, DT, AC) ==
+ FalseVal)
return ReplaceInstUsesWith(SI, TrueVal);
- if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, DL, TLI) == TrueVal ||
- SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, DL, TLI) == TrueVal)
+ if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, DL, TLI, DT, AC) ==
+ TrueVal ||
+ SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, DL, TLI, DT, AC) ==
+ TrueVal)
return ReplaceInstUsesWith(SI, TrueVal);
}
}
}
+ if (unsigned BitWidth = TrueVal->getType()->getScalarSizeInBits()) {
+ APInt MinSignedValue = APInt::getSignBit(BitWidth);
+ Value *X;
+ const APInt *Y, *C;
+ bool TrueWhenUnset;
+ bool IsBitTest = false;
+ if (ICmpInst::isEquality(Pred) &&
+ match(CmpLHS, m_And(m_Value(X), m_Power2(Y))) &&
+ match(CmpRHS, m_Zero())) {
+ IsBitTest = true;
+ TrueWhenUnset = Pred == ICmpInst::ICMP_EQ;
+ } else if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, m_Zero())) {
+ X = CmpLHS;
+ Y = &MinSignedValue;
+ IsBitTest = true;
+ TrueWhenUnset = false;
+ } else if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes())) {
+ X = CmpLHS;
+ Y = &MinSignedValue;
+ IsBitTest = true;
+ TrueWhenUnset = true;
+ }
+ if (IsBitTest) {
+ Value *V = nullptr;
+ // (X & Y) == 0 ? X : X ^ Y --> X & ~Y
+ if (TrueWhenUnset && TrueVal == X &&
+ match(FalseVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
+ V = Builder->CreateAnd(X, ~(*Y));
+ // (X & Y) != 0 ? X ^ Y : X --> X & ~Y
+ else if (!TrueWhenUnset && FalseVal == X &&
+ match(TrueVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
+ V = Builder->CreateAnd(X, ~(*Y));
+ // (X & Y) == 0 ? X ^ Y : X --> X | Y
+ else if (TrueWhenUnset && FalseVal == X &&
+ match(TrueVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
+ V = Builder->CreateOr(X, *Y);
+ // (X & Y) != 0 ? X : X ^ Y --> X | Y
+ else if (!TrueWhenUnset && TrueVal == X &&
+ match(FalseVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
+ V = Builder->CreateOr(X, *Y);
+
+ if (V)
+ return ReplaceInstUsesWith(SI, V);
+ }
+ }
+
if (Value *V = foldSelectICmpAndOr(SI, TrueVal, FalseVal, Builder))
return ReplaceInstUsesWith(SI, V);
+ if (Value *V = foldSelectCttzCtlz(ICI, TrueVal, FalseVal, Builder))
+ return ReplaceInstUsesWith(SI, V);
+
return Changed ? &SI : nullptr;
}
return ReplaceInstUsesWith(Outer, Inner);
}
- // TODO: ABS(NABS(X)) -> ABS(X)
- // TODO: NABS(ABS(X)) -> NABS(X)
+ // ABS(NABS(X)) -> ABS(X)
+ // NABS(ABS(X)) -> NABS(X)
+ if ((SPF1 == SPF_ABS && SPF2 == SPF_NABS) ||
+ (SPF1 == SPF_NABS && SPF2 == SPF_ABS)) {
+ SelectInst *SI = cast<SelectInst>(Inner);
+ Value *NewSI = Builder->CreateSelect(
+ SI->getCondition(), SI->getFalseValue(), SI->getTrueValue());
+ return ReplaceInstUsesWith(Outer, NewSI);
+ }
return nullptr;
}
Value *TrueVal = SI.getTrueValue();
Value *FalseVal = SI.getFalseValue();
- if (Value *V = SimplifySelectInst(CondVal, TrueVal, FalseVal, DL))
+ if (Value *V =
+ SimplifySelectInst(CondVal, TrueVal, FalseVal, DL, TLI, DT, AC))
return ReplaceInstUsesWith(SI, V);
if (SI.getType()->isIntegerTy(1)) {
!CFPf->getValueAPF().isZero()))
return ReplaceInstUsesWith(SI, TrueVal);
}
- // NOTE: if we wanted to, this is where to detect MIN/MAX
+ // Canonicalize to use ordered comparisons by swapping the select
+ // operands.
+ //
+ // e.g.
+ // (X ugt Y) ? X : Y -> (X ole Y) ? Y : X
+ if (FCI->hasOneUse() && FCmpInst::isUnordered(FCI->getPredicate())) {
+ FCmpInst::Predicate InvPred = FCI->getInversePredicate();
+ Value *NewCond = Builder->CreateFCmp(InvPred, TrueVal, FalseVal,
+ FCI->getName() + ".inv");
+
+ return SelectInst::Create(NewCond, FalseVal, TrueVal,
+ SI.getName() + ".p");
+ }
+
+ // NOTE: if we wanted to, this is where to detect MIN/MAX
} else if (FCI->getOperand(0) == FalseVal && FCI->getOperand(1) == TrueVal){
// Transform (X == Y) ? Y : X -> X
if (FCI->getPredicate() == FCmpInst::FCMP_OEQ) {
!CFPf->getValueAPF().isZero()))
return ReplaceInstUsesWith(SI, TrueVal);
}
+
+ // Canonicalize to use ordered comparisons by swapping the select
+ // operands.
+ //
+ // e.g.
+ // (X ugt Y) ? X : Y -> (X ole Y) ? X : Y
+ if (FCI->hasOneUse() && FCmpInst::isUnordered(FCI->getPredicate())) {
+ FCmpInst::Predicate InvPred = FCI->getInversePredicate();
+ Value *NewCond = Builder->CreateFCmp(InvPred, FalseVal, TrueVal,
+ FCI->getName() + ".inv");
+
+ return SelectInst::Create(NewCond, FalseVal, TrueVal,
+ SI.getName() + ".p");
+ }
+
// NOTE: if we wanted to, this is where to detect MIN/MAX
}
// NOTE: if we wanted to, this is where to detect ABS
projects / oota-llvm.git / blobdiff