diff options
author | Dimitry Andric <dim@FreeBSD.org> | 2023-02-11 12:38:04 +0000 |
---|---|---|
committer | Dimitry Andric <dim@FreeBSD.org> | 2023-02-11 12:38:11 +0000 |
commit | e3b557809604d036af6e00c60f012c2025b59a5e (patch) | |
tree | 8a11ba2269a3b669601e2fd41145b174008f4da8 /llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | |
parent | 08e8dd7b9db7bb4a9de26d44c1cbfd24e869c014 (diff) | |
download | src-e3b557809604d036af6e00c60f012c2025b59a5e.tar.gz src-e3b557809604d036af6e00c60f012c2025b59a5e.zip |
Vendor import of llvm-project main llvmorg-16-init-18548-gb0daacf58f41,vendor/llvm-project/llvmorg-16-init-18548-gb0daacf58f41
the last commit before the upstream release/17.x branch was created.
Diffstat (limited to 'llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp')
-rw-r--r-- | llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | 699 |
1 files changed, 577 insertions, 122 deletions
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp index 8253c575bc37..97a001b2ed32 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -233,17 +233,13 @@ static bool decomposeBitTestICmp(Value *LHS, Value *RHS, CmpInst::Predicate &Pre /// the right hand side as a pair. /// LHS and RHS are the left hand side and the right hand side ICmps and PredL /// and PredR are their predicates, respectively. -static -Optional<std::pair<unsigned, unsigned>> -getMaskedTypeForICmpPair(Value *&A, Value *&B, Value *&C, - Value *&D, Value *&E, ICmpInst *LHS, - ICmpInst *RHS, - ICmpInst::Predicate &PredL, - ICmpInst::Predicate &PredR) { +static std::optional<std::pair<unsigned, unsigned>> getMaskedTypeForICmpPair( + Value *&A, Value *&B, Value *&C, Value *&D, Value *&E, ICmpInst *LHS, + ICmpInst *RHS, ICmpInst::Predicate &PredL, ICmpInst::Predicate &PredR) { // Don't allow pointers. Splat vectors are fine. if (!LHS->getOperand(0)->getType()->isIntOrIntVectorTy() || !RHS->getOperand(0)->getType()->isIntOrIntVectorTy()) - return None; + return std::nullopt; // Here comes the tricky part: // LHS might be of the form L11 & L12 == X, X == L21 & L22, @@ -274,7 +270,7 @@ getMaskedTypeForICmpPair(Value *&A, Value *&B, Value *&C, // Bail if LHS was a icmp that can't be decomposed into an equality. if (!ICmpInst::isEquality(PredL)) - return None; + return std::nullopt; Value *R1 = RHS->getOperand(0); Value *R2 = RHS->getOperand(1); @@ -288,7 +284,7 @@ getMaskedTypeForICmpPair(Value *&A, Value *&B, Value *&C, A = R12; D = R11; } else { - return None; + return std::nullopt; } E = R2; R1 = nullptr; @@ -316,7 +312,7 @@ getMaskedTypeForICmpPair(Value *&A, Value *&B, Value *&C, // Bail if RHS was a icmp that can't be decomposed into an equality. if (!ICmpInst::isEquality(PredR)) - return None; + return std::nullopt; // Look for ANDs on the right side of the RHS icmp. if (!Ok) { @@ -336,7 +332,7 @@ getMaskedTypeForICmpPair(Value *&A, Value *&B, Value *&C, E = R1; Ok = true; } else { - return None; + return std::nullopt; } assert(Ok && "Failed to find AND on the right side of the RHS icmp."); @@ -358,7 +354,8 @@ getMaskedTypeForICmpPair(Value *&A, Value *&B, Value *&C, unsigned LeftType = getMaskedICmpType(A, B, C, PredL); unsigned RightType = getMaskedICmpType(A, D, E, PredR); - return Optional<std::pair<unsigned, unsigned>>(std::make_pair(LeftType, RightType)); + return std::optional<std::pair<unsigned, unsigned>>( + std::make_pair(LeftType, RightType)); } /// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) into a single @@ -526,7 +523,7 @@ static Value *foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, InstCombiner::BuilderTy &Builder) { Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr, *E = nullptr; ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate(); - Optional<std::pair<unsigned, unsigned>> MaskPair = + std::optional<std::pair<unsigned, unsigned>> MaskPair = getMaskedTypeForICmpPair(A, B, C, D, E, LHS, RHS, PredL, PredR); if (!MaskPair) return nullptr; @@ -1016,10 +1013,10 @@ struct IntPart { }; /// Match an extraction of bits from an integer. -static Optional<IntPart> matchIntPart(Value *V) { +static std::optional<IntPart> matchIntPart(Value *V) { Value *X; if (!match(V, m_OneUse(m_Trunc(m_Value(X))))) - return None; + return std::nullopt; unsigned NumOriginalBits = X->getType()->getScalarSizeInBits(); unsigned NumExtractedBits = V->getType()->getScalarSizeInBits(); @@ -1056,10 +1053,10 @@ Value *InstCombinerImpl::foldEqOfParts(ICmpInst *Cmp0, ICmpInst *Cmp1, if (Cmp0->getPredicate() != Pred || Cmp1->getPredicate() != Pred) return nullptr; - Optional<IntPart> L0 = matchIntPart(Cmp0->getOperand(0)); - Optional<IntPart> R0 = matchIntPart(Cmp0->getOperand(1)); - Optional<IntPart> L1 = matchIntPart(Cmp1->getOperand(0)); - Optional<IntPart> R1 = matchIntPart(Cmp1->getOperand(1)); + std::optional<IntPart> L0 = matchIntPart(Cmp0->getOperand(0)); + std::optional<IntPart> R0 = matchIntPart(Cmp0->getOperand(1)); + std::optional<IntPart> L1 = matchIntPart(Cmp1->getOperand(0)); + std::optional<IntPart> R1 = matchIntPart(Cmp1->getOperand(1)); if (!L0 || !R0 || !L1 || !R1) return nullptr; @@ -1094,7 +1091,7 @@ Value *InstCombinerImpl::foldEqOfParts(ICmpInst *Cmp0, ICmpInst *Cmp1, /// common operand with the constant. Callers are expected to call this with /// Cmp0/Cmp1 switched to handle logic op commutativity. static Value *foldAndOrOfICmpsWithConstEq(ICmpInst *Cmp0, ICmpInst *Cmp1, - bool IsAnd, + bool IsAnd, bool IsLogical, InstCombiner::BuilderTy &Builder, const SimplifyQuery &Q) { // Match an equality compare with a non-poison constant as Cmp0. @@ -1130,6 +1127,9 @@ static Value *foldAndOrOfICmpsWithConstEq(ICmpInst *Cmp0, ICmpInst *Cmp1, return nullptr; SubstituteCmp = Builder.CreateICmp(Pred1, Y, C); } + if (IsLogical) + return IsAnd ? Builder.CreateLogicalAnd(Cmp0, SubstituteCmp) + : Builder.CreateLogicalOr(Cmp0, SubstituteCmp); return Builder.CreateBinOp(IsAnd ? Instruction::And : Instruction::Or, Cmp0, SubstituteCmp); } @@ -1174,7 +1174,7 @@ Value *InstCombinerImpl::foldAndOrOfICmpsUsingRanges(ICmpInst *ICmp1, Type *Ty = V1->getType(); Value *NewV = V1; - Optional<ConstantRange> CR = CR1.exactUnionWith(CR2); + std::optional<ConstantRange> CR = CR1.exactUnionWith(CR2); if (!CR) { if (!(ICmp1->hasOneUse() && ICmp2->hasOneUse()) || CR1.isWrappedSet() || CR2.isWrappedSet()) @@ -1205,6 +1205,47 @@ Value *InstCombinerImpl::foldAndOrOfICmpsUsingRanges(ICmpInst *ICmp1, return Builder.CreateICmp(NewPred, NewV, ConstantInt::get(Ty, NewC)); } +/// Ignore all operations which only change the sign of a value, returning the +/// underlying magnitude value. +static Value *stripSignOnlyFPOps(Value *Val) { + match(Val, m_FNeg(m_Value(Val))); + match(Val, m_FAbs(m_Value(Val))); + match(Val, m_CopySign(m_Value(Val), m_Value())); + return Val; +} + +/// Matches canonical form of isnan, fcmp ord x, 0 +static bool matchIsNotNaN(FCmpInst::Predicate P, Value *LHS, Value *RHS) { + return P == FCmpInst::FCMP_ORD && match(RHS, m_AnyZeroFP()); +} + +/// Matches fcmp u__ x, +/-inf +static bool matchUnorderedInfCompare(FCmpInst::Predicate P, Value *LHS, + Value *RHS) { + return FCmpInst::isUnordered(P) && match(RHS, m_Inf()); +} + +/// and (fcmp ord x, 0), (fcmp u* x, inf) -> fcmp o* x, inf +/// +/// Clang emits this pattern for doing an isfinite check in __builtin_isnormal. +static Value *matchIsFiniteTest(InstCombiner::BuilderTy &Builder, FCmpInst *LHS, + FCmpInst *RHS) { + Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1); + Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1); + FCmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate(); + + if (!matchIsNotNaN(PredL, LHS0, LHS1) || + !matchUnorderedInfCompare(PredR, RHS0, RHS1)) + return nullptr; + + IRBuilder<>::FastMathFlagGuard FMFG(Builder); + FastMathFlags FMF = LHS->getFastMathFlags(); + FMF &= RHS->getFastMathFlags(); + Builder.setFastMathFlags(FMF); + + return Builder.CreateFCmp(FCmpInst::getOrderedPredicate(PredR), RHS0, RHS1); +} + Value *InstCombinerImpl::foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd, bool IsLogicalSelect) { Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1); @@ -1263,9 +1304,79 @@ Value *InstCombinerImpl::foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, return Builder.CreateFCmp(PredL, LHS0, RHS0); } + if (IsAnd && stripSignOnlyFPOps(LHS0) == stripSignOnlyFPOps(RHS0)) { + // and (fcmp ord x, 0), (fcmp u* x, inf) -> fcmp o* x, inf + // and (fcmp ord x, 0), (fcmp u* fabs(x), inf) -> fcmp o* x, inf + if (Value *Left = matchIsFiniteTest(Builder, LHS, RHS)) + return Left; + if (Value *Right = matchIsFiniteTest(Builder, RHS, LHS)) + return Right; + } + return nullptr; } +/// or (is_fpclass x, mask0), (is_fpclass x, mask1) +/// -> is_fpclass x, (mask0 | mask1) +/// and (is_fpclass x, mask0), (is_fpclass x, mask1) +/// -> is_fpclass x, (mask0 & mask1) +/// xor (is_fpclass x, mask0), (is_fpclass x, mask1) +/// -> is_fpclass x, (mask0 ^ mask1) +Instruction *InstCombinerImpl::foldLogicOfIsFPClass(BinaryOperator &BO, + Value *Op0, Value *Op1) { + Value *ClassVal; + uint64_t ClassMask0, ClassMask1; + + if (match(Op0, m_OneUse(m_Intrinsic<Intrinsic::is_fpclass>( + m_Value(ClassVal), m_ConstantInt(ClassMask0)))) && + match(Op1, m_OneUse(m_Intrinsic<Intrinsic::is_fpclass>( + m_Specific(ClassVal), m_ConstantInt(ClassMask1))))) { + unsigned NewClassMask; + switch (BO.getOpcode()) { + case Instruction::And: + NewClassMask = ClassMask0 & ClassMask1; + break; + case Instruction::Or: + NewClassMask = ClassMask0 | ClassMask1; + break; + case Instruction::Xor: + NewClassMask = ClassMask0 ^ ClassMask1; + break; + default: + llvm_unreachable("not a binary logic operator"); + } + + // TODO: Also check for special fcmps + auto *II = cast<IntrinsicInst>(Op0); + II->setArgOperand( + 1, ConstantInt::get(II->getArgOperand(1)->getType(), NewClassMask)); + return replaceInstUsesWith(BO, II); + } + + return nullptr; +} + +/// Look for the pattern that conditionally negates a value via math operations: +/// cond.splat = sext i1 cond +/// sub = add cond.splat, x +/// xor = xor sub, cond.splat +/// and rewrite it to do the same, but via logical operations: +/// value.neg = sub 0, value +/// cond = select i1 neg, value.neg, value +Instruction *InstCombinerImpl::canonicalizeConditionalNegationViaMathToSelect( + BinaryOperator &I) { + assert(I.getOpcode() == BinaryOperator::Xor && "Only for xor!"); + Value *Cond, *X; + // As per complexity ordering, `xor` is not commutative here. + if (!match(&I, m_c_BinOp(m_OneUse(m_Value()), m_Value())) || + !match(I.getOperand(1), m_SExt(m_Value(Cond))) || + !Cond->getType()->isIntOrIntVectorTy(1) || + !match(I.getOperand(0), m_c_Add(m_SExt(m_Deferred(Cond)), m_Value(X)))) + return nullptr; + return SelectInst::Create(Cond, Builder.CreateNeg(X, X->getName() + ".neg"), + X); +} + /// This a limited reassociation for a special case (see above) where we are /// checking if two values are either both NAN (unordered) or not-NAN (ordered). /// This could be handled more generally in '-reassociation', but it seems like @@ -1430,11 +1541,33 @@ Instruction *InstCombinerImpl::foldCastedBitwiseLogic(BinaryOperator &I) { if (!Cast1) return nullptr; - // Both operands of the logic operation are casts. The casts must be of the - // same type for reduction. - auto CastOpcode = Cast0->getOpcode(); - if (CastOpcode != Cast1->getOpcode() || SrcTy != Cast1->getSrcTy()) + // Both operands of the logic operation are casts. The casts must be the + // same kind for reduction. + Instruction::CastOps CastOpcode = Cast0->getOpcode(); + if (CastOpcode != Cast1->getOpcode()) + return nullptr; + + // If the source types do not match, but the casts are matching extends, we + // can still narrow the logic op. + if (SrcTy != Cast1->getSrcTy()) { + Value *X, *Y; + if (match(Cast0, m_OneUse(m_ZExtOrSExt(m_Value(X)))) && + match(Cast1, m_OneUse(m_ZExtOrSExt(m_Value(Y))))) { + // Cast the narrower source to the wider source type. + unsigned XNumBits = X->getType()->getScalarSizeInBits(); + unsigned YNumBits = Y->getType()->getScalarSizeInBits(); + if (XNumBits < YNumBits) + X = Builder.CreateCast(CastOpcode, X, Y->getType()); + else + Y = Builder.CreateCast(CastOpcode, Y, X->getType()); + // Do the logic op in the intermediate width, then widen more. + Value *NarrowLogic = Builder.CreateBinOp(LogicOpc, X, Y); + return CastInst::Create(CastOpcode, NarrowLogic, DestTy); + } + + // Give up for other cast opcodes. return nullptr; + } Value *Cast0Src = Cast0->getOperand(0); Value *Cast1Src = Cast1->getOperand(0); @@ -1722,6 +1855,77 @@ static Instruction *foldComplexAndOrPatterns(BinaryOperator &I, return nullptr; } +/// Try to reassociate a pair of binops so that values with one use only are +/// part of the same instruction. This may enable folds that are limited with +/// multi-use restrictions and makes it more likely to match other patterns that +/// are looking for a common operand. +static Instruction *reassociateForUses(BinaryOperator &BO, + InstCombinerImpl::BuilderTy &Builder) { + Instruction::BinaryOps Opcode = BO.getOpcode(); + Value *X, *Y, *Z; + if (match(&BO, + m_c_BinOp(Opcode, m_OneUse(m_BinOp(Opcode, m_Value(X), m_Value(Y))), + m_OneUse(m_Value(Z))))) { + if (!isa<Constant>(X) && !isa<Constant>(Y) && !isa<Constant>(Z)) { + // (X op Y) op Z --> (Y op Z) op X + if (!X->hasOneUse()) { + Value *YZ = Builder.CreateBinOp(Opcode, Y, Z); + return BinaryOperator::Create(Opcode, YZ, X); + } + // (X op Y) op Z --> (X op Z) op Y + if (!Y->hasOneUse()) { + Value *XZ = Builder.CreateBinOp(Opcode, X, Z); + return BinaryOperator::Create(Opcode, XZ, Y); + } + } + } + + return nullptr; +} + +// Match +// (X + C2) | C +// (X + C2) ^ C +// (X + C2) & C +// and convert to do the bitwise logic first: +// (X | C) + C2 +// (X ^ C) + C2 +// (X & C) + C2 +// iff bits affected by logic op are lower than last bit affected by math op +static Instruction *canonicalizeLogicFirst(BinaryOperator &I, + InstCombiner::BuilderTy &Builder) { + Type *Ty = I.getType(); + Instruction::BinaryOps OpC = I.getOpcode(); + Value *Op0 = I.getOperand(0); + Value *Op1 = I.getOperand(1); + Value *X; + const APInt *C, *C2; + + if (!(match(Op0, m_OneUse(m_Add(m_Value(X), m_APInt(C2)))) && + match(Op1, m_APInt(C)))) + return nullptr; + + unsigned Width = Ty->getScalarSizeInBits(); + unsigned LastOneMath = Width - C2->countTrailingZeros(); + + switch (OpC) { + case Instruction::And: + if (C->countLeadingOnes() < LastOneMath) + return nullptr; + break; + case Instruction::Xor: + case Instruction::Or: + if (C->countLeadingZeros() < LastOneMath) + return nullptr; + break; + default: + llvm_unreachable("Unexpected BinaryOp!"); + } + + Value *NewBinOp = Builder.CreateBinOp(OpC, X, ConstantInt::get(Ty, *C)); + return BinaryOperator::CreateAdd(NewBinOp, ConstantInt::get(Ty, *C2)); +} + // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches // here. We should standardize that construct where it is needed or choose some // other way to ensure that commutated variants of patterns are not missed. @@ -1754,7 +1958,7 @@ Instruction *InstCombinerImpl::visitAnd(BinaryOperator &I) { return X; // (A|B)&(A|C) -> A|(B&C) etc - if (Value *V = SimplifyUsingDistributiveLaws(I)) + if (Value *V = foldUsingDistributiveLaws(I)) return replaceInstUsesWith(I, V); if (Value *V = SimplifyBSwap(I, Builder)) @@ -2156,24 +2360,36 @@ Instruction *InstCombinerImpl::visitAnd(BinaryOperator &I) { A->getType()->isIntOrIntVectorTy(1)) return SelectInst::Create(A, Op0, Constant::getNullValue(Ty)); - // (iN X s>> (N-1)) & Y --> (X s< 0) ? Y : 0 - unsigned FullShift = Ty->getScalarSizeInBits() - 1; - if (match(&I, m_c_And(m_OneUse(m_AShr(m_Value(X), m_SpecificInt(FullShift))), - m_Value(Y)))) { + // Similarly, a 'not' of the bool translates to a swap of the select arms: + // ~sext(A) & Op1 --> A ? 0 : Op1 + // Op0 & ~sext(A) --> A ? 0 : Op0 + if (match(Op0, m_Not(m_SExt(m_Value(A)))) && + A->getType()->isIntOrIntVectorTy(1)) + return SelectInst::Create(A, Constant::getNullValue(Ty), Op1); + if (match(Op1, m_Not(m_SExt(m_Value(A)))) && + A->getType()->isIntOrIntVectorTy(1)) + return SelectInst::Create(A, Constant::getNullValue(Ty), Op0); + + // (iN X s>> (N-1)) & Y --> (X s< 0) ? Y : 0 -- with optional sext + if (match(&I, m_c_And(m_OneUse(m_SExtOrSelf( + m_AShr(m_Value(X), m_APIntAllowUndef(C)))), + m_Value(Y))) && + *C == X->getType()->getScalarSizeInBits() - 1) { Value *IsNeg = Builder.CreateIsNeg(X, "isneg"); return SelectInst::Create(IsNeg, Y, ConstantInt::getNullValue(Ty)); } // If there's a 'not' of the shifted value, swap the select operands: - // ~(iN X s>> (N-1)) & Y --> (X s< 0) ? 0 : Y - if (match(&I, m_c_And(m_OneUse(m_Not( - m_AShr(m_Value(X), m_SpecificInt(FullShift)))), - m_Value(Y)))) { + // ~(iN X s>> (N-1)) & Y --> (X s< 0) ? 0 : Y -- with optional sext + if (match(&I, m_c_And(m_OneUse(m_SExtOrSelf( + m_Not(m_AShr(m_Value(X), m_APIntAllowUndef(C))))), + m_Value(Y))) && + *C == X->getType()->getScalarSizeInBits() - 1) { Value *IsNeg = Builder.CreateIsNeg(X, "isneg"); return SelectInst::Create(IsNeg, ConstantInt::getNullValue(Ty), Y); } // (~x) & y --> ~(x | (~y)) iff that gets rid of inversions - if (sinkNotIntoOtherHandOfAndOrOr(I)) + if (sinkNotIntoOtherHandOfLogicalOp(I)) return &I; // An and recurrence w/loop invariant step is equivelent to (and start, step) @@ -2182,6 +2398,15 @@ Instruction *InstCombinerImpl::visitAnd(BinaryOperator &I) { if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN)) return replaceInstUsesWith(I, Builder.CreateAnd(Start, Step)); + if (Instruction *R = reassociateForUses(I, Builder)) + return R; + + if (Instruction *Canonicalized = canonicalizeLogicFirst(I, Builder)) + return Canonicalized; + + if (Instruction *Folded = foldLogicOfIsFPClass(I, Op0, Op1)) + return Folded; + return nullptr; } @@ -2375,7 +2600,9 @@ static bool areInverseVectorBitmasks(Constant *C1, Constant *C2) { /// We have an expression of the form (A & C) | (B & D). If A is a scalar or /// vector composed of all-zeros or all-ones values and is the bitwise 'not' of /// B, it can be used as the condition operand of a select instruction. -Value *InstCombinerImpl::getSelectCondition(Value *A, Value *B) { +/// We will detect (A & C) | ~(B | D) when the flag ABIsTheSame enabled. +Value *InstCombinerImpl::getSelectCondition(Value *A, Value *B, + bool ABIsTheSame) { // We may have peeked through bitcasts in the caller. // Exit immediately if we don't have (vector) integer types. Type *Ty = A->getType(); @@ -2383,7 +2610,7 @@ Value *InstCombinerImpl::getSelectCondition(Value *A, Value *B) { return nullptr; // If A is the 'not' operand of B and has enough signbits, we have our answer. - if (match(B, m_Not(m_Specific(A)))) { + if (ABIsTheSame ? (A == B) : match(B, m_Not(m_Specific(A)))) { // If these are scalars or vectors of i1, A can be used directly. if (Ty->isIntOrIntVectorTy(1)) return A; @@ -2403,6 +2630,10 @@ Value *InstCombinerImpl::getSelectCondition(Value *A, Value *B) { return nullptr; } + // TODO: add support for sext and constant case + if (ABIsTheSame) + return nullptr; + // If both operands are constants, see if the constants are inverse bitmasks. Constant *AConst, *BConst; if (match(A, m_Constant(AConst)) && match(B, m_Constant(BConst))) @@ -2451,14 +2682,17 @@ Value *InstCombinerImpl::getSelectCondition(Value *A, Value *B) { /// We have an expression of the form (A & C) | (B & D). Try to simplify this /// to "A' ? C : D", where A' is a boolean or vector of booleans. +/// When InvertFalseVal is set to true, we try to match the pattern +/// where we have peeked through a 'not' op and A and B are the same: +/// (A & C) | ~(A | D) --> (A & C) | (~A & ~D) --> A' ? C : ~D Value *InstCombinerImpl::matchSelectFromAndOr(Value *A, Value *C, Value *B, - Value *D) { + Value *D, bool InvertFalseVal) { // The potential condition of the select may be bitcasted. In that case, look // through its bitcast and the corresponding bitcast of the 'not' condition. Type *OrigType = A->getType(); A = peekThroughBitcast(A, true); B = peekThroughBitcast(B, true); - if (Value *Cond = getSelectCondition(A, B)) { + if (Value *Cond = getSelectCondition(A, B, InvertFalseVal)) { // ((bc Cond) & C) | ((bc ~Cond) & D) --> bc (select Cond, (bc C), (bc D)) // If this is a vector, we may need to cast to match the condition's length. // The bitcasts will either all exist or all not exist. The builder will @@ -2469,11 +2703,13 @@ Value *InstCombinerImpl::matchSelectFromAndOr(Value *A, Value *C, Value *B, unsigned Elts = VecTy->getElementCount().getKnownMinValue(); // For a fixed or scalable vector, get the size in bits of N x iM; for a // scalar this is just M. - unsigned SelEltSize = SelTy->getPrimitiveSizeInBits().getKnownMinSize(); + unsigned SelEltSize = SelTy->getPrimitiveSizeInBits().getKnownMinValue(); Type *EltTy = Builder.getIntNTy(SelEltSize / Elts); SelTy = VectorType::get(EltTy, VecTy->getElementCount()); } Value *BitcastC = Builder.CreateBitCast(C, SelTy); + if (InvertFalseVal) + D = Builder.CreateNot(D); Value *BitcastD = Builder.CreateBitCast(D, SelTy); Value *Select = Builder.CreateSelect(Cond, BitcastC, BitcastD); return Builder.CreateBitCast(Select, OrigType); @@ -2484,8 +2720,9 @@ Value *InstCombinerImpl::matchSelectFromAndOr(Value *A, Value *C, Value *B, // (icmp eq X, 0) | (icmp ult Other, X) -> (icmp ule Other, X-1) // (icmp ne X, 0) & (icmp uge Other, X) -> (icmp ugt Other, X-1) -Value *foldAndOrOfICmpEqZeroAndICmp(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, - IRBuilderBase &Builder) { +static Value *foldAndOrOfICmpEqZeroAndICmp(ICmpInst *LHS, ICmpInst *RHS, + bool IsAnd, bool IsLogical, + IRBuilderBase &Builder) { ICmpInst::Predicate LPred = IsAnd ? LHS->getInversePredicate() : LHS->getPredicate(); ICmpInst::Predicate RPred = @@ -2504,6 +2741,8 @@ Value *foldAndOrOfICmpEqZeroAndICmp(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, else return nullptr; + if (IsLogical) + Other = Builder.CreateFreeze(Other); return Builder.CreateICmp( IsAnd ? ICmpInst::ICMP_ULT : ICmpInst::ICMP_UGE, Builder.CreateAdd(LHS0, Constant::getAllOnesValue(LHS0->getType())), @@ -2552,22 +2791,23 @@ Value *InstCombinerImpl::foldAndOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, IsAnd, IsLogical, Builder)) return V; - // TODO: One of these directions is fine with logical and/or, the other could - // be supported by inserting freeze. - if (!IsLogical) { - if (Value *V = foldAndOrOfICmpEqZeroAndICmp(LHS, RHS, IsAnd, Builder)) - return V; - if (Value *V = foldAndOrOfICmpEqZeroAndICmp(RHS, LHS, IsAnd, Builder)) - return V; - } + if (Value *V = + foldAndOrOfICmpEqZeroAndICmp(LHS, RHS, IsAnd, IsLogical, Builder)) + return V; + // We can treat logical like bitwise here, because both operands are used on + // the LHS, and as such poison from both will propagate. + if (Value *V = foldAndOrOfICmpEqZeroAndICmp(RHS, LHS, IsAnd, + /*IsLogical*/ false, Builder)) + return V; - // TODO: Verify whether this is safe for logical and/or. - if (!IsLogical) { - if (Value *V = foldAndOrOfICmpsWithConstEq(LHS, RHS, IsAnd, Builder, Q)) - return V; - if (Value *V = foldAndOrOfICmpsWithConstEq(RHS, LHS, IsAnd, Builder, Q)) - return V; - } + if (Value *V = + foldAndOrOfICmpsWithConstEq(LHS, RHS, IsAnd, IsLogical, Builder, Q)) + return V; + // We can convert this case to bitwise and, because both operands are used + // on the LHS, and as such poison from both will propagate. + if (Value *V = foldAndOrOfICmpsWithConstEq(RHS, LHS, IsAnd, + /*IsLogical*/ false, Builder, Q)) + return V; if (Value *V = foldIsPowerOf2OrZero(LHS, RHS, IsAnd, Builder)) return V; @@ -2724,7 +2964,7 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) { return X; // (A&B)|(A&C) -> A&(B|C) etc - if (Value *V = SimplifyUsingDistributiveLaws(I)) + if (Value *V = foldUsingDistributiveLaws(I)) return replaceInstUsesWith(I, V); if (Value *V = SimplifyBSwap(I, Builder)) @@ -2777,6 +3017,10 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) { return BinaryOperator::CreateMul(X, IncrementY); } + // X | (X ^ Y) --> X | Y (4 commuted patterns) + if (match(&I, m_c_Or(m_Value(X), m_c_Xor(m_Deferred(X), m_Value(Y))))) + return BinaryOperator::CreateOr(X, Y); + // (A & C) | (B & D) Value *A, *B, *C, *D; if (match(Op0, m_And(m_Value(A), m_Value(C))) && @@ -2854,6 +3098,20 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) { } } + if (match(Op0, m_And(m_Value(A), m_Value(C))) && + match(Op1, m_Not(m_Or(m_Value(B), m_Value(D)))) && + (Op0->hasOneUse() || Op1->hasOneUse())) { + // (Cond & C) | ~(Cond | D) -> Cond ? C : ~D + if (Value *V = matchSelectFromAndOr(A, C, B, D, true)) + return replaceInstUsesWith(I, V); + if (Value *V = matchSelectFromAndOr(A, C, D, B, true)) + return replaceInstUsesWith(I, V); + if (Value *V = matchSelectFromAndOr(C, A, B, D, true)) + return replaceInstUsesWith(I, V); + if (Value *V = matchSelectFromAndOr(C, A, D, B, true)) + return replaceInstUsesWith(I, V); + } + // (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C if (match(Op0, m_Xor(m_Value(A), m_Value(B)))) if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A)))) @@ -2886,30 +3144,58 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) { SwappedForXor = true; } - // A | ( A ^ B) -> A | B - // A | (~A ^ B) -> A | ~B - // (A & B) | (A ^ B) - // ~A | (A ^ B) -> ~(A & B) - // The swap above should always make Op0 the 'not' for the last case. if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) { - if (Op0 == A || Op0 == B) - return BinaryOperator::CreateOr(A, B); - + // (A | ?) | (A ^ B) --> (A | ?) | B + // (B | ?) | (A ^ B) --> (B | ?) | A + if (match(Op0, m_c_Or(m_Specific(A), m_Value()))) + return BinaryOperator::CreateOr(Op0, B); + if (match(Op0, m_c_Or(m_Specific(B), m_Value()))) + return BinaryOperator::CreateOr(Op0, A); + + // (A & B) | (A ^ B) --> A | B + // (B & A) | (A ^ B) --> A | B if (match(Op0, m_And(m_Specific(A), m_Specific(B))) || match(Op0, m_And(m_Specific(B), m_Specific(A)))) return BinaryOperator::CreateOr(A, B); + // ~A | (A ^ B) --> ~(A & B) + // ~B | (A ^ B) --> ~(A & B) + // The swap above should always make Op0 the 'not'. if ((Op0->hasOneUse() || Op1->hasOneUse()) && (match(Op0, m_Not(m_Specific(A))) || match(Op0, m_Not(m_Specific(B))))) return BinaryOperator::CreateNot(Builder.CreateAnd(A, B)); + // Same as above, but peek through an 'and' to the common operand: + // ~(A & ?) | (A ^ B) --> ~((A & ?) & B) + // ~(B & ?) | (A ^ B) --> ~((B & ?) & A) + Instruction *And; + if ((Op0->hasOneUse() || Op1->hasOneUse()) && + match(Op0, m_Not(m_CombineAnd(m_Instruction(And), + m_c_And(m_Specific(A), m_Value()))))) + return BinaryOperator::CreateNot(Builder.CreateAnd(And, B)); + if ((Op0->hasOneUse() || Op1->hasOneUse()) && + match(Op0, m_Not(m_CombineAnd(m_Instruction(And), + m_c_And(m_Specific(B), m_Value()))))) + return BinaryOperator::CreateNot(Builder.CreateAnd(And, A)); + + // (~A | C) | (A ^ B) --> ~(A & B) | C + // (~B | C) | (A ^ B) --> ~(A & B) | C + if (Op0->hasOneUse() && Op1->hasOneUse() && + (match(Op0, m_c_Or(m_Not(m_Specific(A)), m_Value(C))) || + match(Op0, m_c_Or(m_Not(m_Specific(B)), m_Value(C))))) { + Value *Nand = Builder.CreateNot(Builder.CreateAnd(A, B), "nand"); + return BinaryOperator::CreateOr(Nand, C); + } + + // A | (~A ^ B) --> ~B | A + // B | (A ^ ~B) --> ~A | B if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) { - Value *Not = Builder.CreateNot(B, B->getName() + ".not"); - return BinaryOperator::CreateOr(Not, Op0); + Value *NotB = Builder.CreateNot(B, B->getName() + ".not"); + return BinaryOperator::CreateOr(NotB, Op0); } if (Op1->hasOneUse() && match(B, m_Not(m_Specific(Op0)))) { - Value *Not = Builder.CreateNot(A, A->getName() + ".not"); - return BinaryOperator::CreateOr(Not, Op0); + Value *NotA = Builder.CreateNot(A, A->getName() + ".not"); + return BinaryOperator::CreateOr(NotA, Op0); } } @@ -3072,7 +3358,7 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) { } // (~x) | y --> ~(x & (~y)) iff that gets rid of inversions - if (sinkNotIntoOtherHandOfAndOrOr(I)) + if (sinkNotIntoOtherHandOfLogicalOp(I)) return &I; // Improve "get low bit mask up to and including bit X" pattern: @@ -3121,6 +3407,15 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) { Builder.CreateOr(C, Builder.CreateAnd(A, B)), D); } + if (Instruction *R = reassociateForUses(I, Builder)) + return R; + + if (Instruction *Canonicalized = canonicalizeLogicFirst(I, Builder)) + return Canonicalized; + + if (Instruction *Folded = foldLogicOfIsFPClass(I, Op0, Op1)) + return Folded; + return nullptr; } @@ -3338,14 +3633,8 @@ static Instruction *visitMaskedMerge(BinaryOperator &I, // (~x) ^ y // or into // x ^ (~y) -static Instruction *sinkNotIntoXor(BinaryOperator &I, +static Instruction *sinkNotIntoXor(BinaryOperator &I, Value *X, Value *Y, InstCombiner::BuilderTy &Builder) { - Value *X, *Y; - // FIXME: one-use check is not needed in general, but currently we are unable - // to fold 'not' into 'icmp', if that 'icmp' has multiple uses. (D35182) - if (!match(&I, m_Not(m_OneUse(m_Xor(m_Value(X), m_Value(Y)))))) - return nullptr; - // We only want to do the transform if it is free to do. if (InstCombiner::isFreeToInvert(X, X->hasOneUse())) { // Ok, good. @@ -3358,6 +3647,41 @@ static Instruction *sinkNotIntoXor(BinaryOperator &I, return BinaryOperator::CreateXor(NotX, Y, I.getName() + ".demorgan"); } +static Instruction *foldNotXor(BinaryOperator &I, + InstCombiner::BuilderTy &Builder) { + Value *X, *Y; + // FIXME: one-use check is not needed in general, but currently we are unable + // to fold 'not' into 'icmp', if that 'icmp' has multiple uses. (D35182) + if (!match(&I, m_Not(m_OneUse(m_Xor(m_Value(X), m_Value(Y)))))) + return nullptr; + + if (Instruction *NewXor = sinkNotIntoXor(I, X, Y, Builder)) + return NewXor; + + auto hasCommonOperand = [](Value *A, Value *B, Value *C, Value *D) { + return A == C || A == D || B == C || B == D; + }; + + Value *A, *B, *C, *D; + // Canonicalize ~((A & B) ^ (A | ?)) -> (A & B) | ~(A | ?) + // 4 commuted variants + if (match(X, m_And(m_Value(A), m_Value(B))) && + match(Y, m_Or(m_Value(C), m_Value(D))) && hasCommonOperand(A, B, C, D)) { + Value *NotY = Builder.CreateNot(Y); + return BinaryOperator::CreateOr(X, NotY); + }; + + // Canonicalize ~((A | ?) ^ (A & B)) -> (A & B) | ~(A | ?) + // 4 commuted variants + if (match(Y, m_And(m_Value(A), m_Value(B))) && + match(X, m_Or(m_Value(C), m_Value(D))) && hasCommonOperand(A, B, C, D)) { + Value *NotX = Builder.CreateNot(X); + return BinaryOperator::CreateOr(Y, NotX); + }; + + return nullptr; +} + /// Canonicalize a shifty way to code absolute value to the more common pattern /// that uses negation and select. static Instruction *canonicalizeAbs(BinaryOperator &Xor, @@ -3392,39 +3716,127 @@ static Instruction *canonicalizeAbs(BinaryOperator &Xor, } // Transform -// z = (~x) &/| y +// z = ~(x &/| y) // into: -// z = ~(x |/& (~y)) -// iff y is free to invert and all uses of z can be freely updated. -bool InstCombinerImpl::sinkNotIntoOtherHandOfAndOrOr(BinaryOperator &I) { - Instruction::BinaryOps NewOpc; - switch (I.getOpcode()) { - case Instruction::And: - NewOpc = Instruction::Or; - break; - case Instruction::Or: - NewOpc = Instruction::And; - break; - default: +// z = ((~x) |/& (~y)) +// iff both x and y are free to invert and all uses of z can be freely updated. +bool InstCombinerImpl::sinkNotIntoLogicalOp(Instruction &I) { + Value *Op0, *Op1; + if (!match(&I, m_LogicalOp(m_Value(Op0), m_Value(Op1)))) return false; - }; - Value *X, *Y; - if (!match(&I, m_c_BinOp(m_Not(m_Value(X)), m_Value(Y)))) + // If this logic op has not been simplified yet, just bail out and let that + // happen first. Otherwise, the code below may wrongly invert. + if (Op0 == Op1) return false; - // Will we be able to fold the `not` into Y eventually? - if (!InstCombiner::isFreeToInvert(Y, Y->hasOneUse())) + Instruction::BinaryOps NewOpc = + match(&I, m_LogicalAnd()) ? Instruction::Or : Instruction::And; + bool IsBinaryOp = isa<BinaryOperator>(I); + + // Can our users be adapted? + if (!InstCombiner::canFreelyInvertAllUsersOf(&I, /*IgnoredUser=*/nullptr)) + return false; + + // And can the operands be adapted? + for (Value *Op : {Op0, Op1}) + if (!(InstCombiner::isFreeToInvert(Op, /*WillInvertAllUses=*/true) && + (match(Op, m_ImmConstant()) || + (isa<Instruction>(Op) && + InstCombiner::canFreelyInvertAllUsersOf(cast<Instruction>(Op), + /*IgnoredUser=*/&I))))) + return false; + + for (Value **Op : {&Op0, &Op1}) { + Value *NotOp; + if (auto *C = dyn_cast<Constant>(*Op)) { + NotOp = ConstantExpr::getNot(C); + } else { + Builder.SetInsertPoint( + &*cast<Instruction>(*Op)->getInsertionPointAfterDef()); + NotOp = Builder.CreateNot(*Op, (*Op)->getName() + ".not"); + (*Op)->replaceUsesWithIf( + NotOp, [NotOp](Use &U) { return U.getUser() != NotOp; }); + freelyInvertAllUsersOf(NotOp, /*IgnoredUser=*/&I); + } + *Op = NotOp; + } + + Builder.SetInsertPoint(I.getInsertionPointAfterDef()); + Value *NewLogicOp; + if (IsBinaryOp) + NewLogicOp = Builder.CreateBinOp(NewOpc, Op0, Op1, I.getName() + ".not"); + else + NewLogicOp = + Builder.CreateLogicalOp(NewOpc, Op0, Op1, I.getName() + ".not"); + + replaceInstUsesWith(I, NewLogicOp); + // We can not just create an outer `not`, it will most likely be immediately + // folded back, reconstructing our initial pattern, and causing an + // infinite combine loop, so immediately manually fold it away. + freelyInvertAllUsersOf(NewLogicOp); + return true; +} + +// Transform +// z = (~x) &/| y +// into: +// z = ~(x |/& (~y)) +// iff y is free to invert and all uses of z can be freely updated. +bool InstCombinerImpl::sinkNotIntoOtherHandOfLogicalOp(Instruction &I) { + Value *Op0, *Op1; + if (!match(&I, m_LogicalOp(m_Value(Op0), m_Value(Op1)))) + return false; + Instruction::BinaryOps NewOpc = + match(&I, m_LogicalAnd()) ? Instruction::Or : Instruction::And; + bool IsBinaryOp = isa<BinaryOperator>(I); + + Value *NotOp0 = nullptr; + Value *NotOp1 = nullptr; + Value **OpToInvert = nullptr; + if (match(Op0, m_Not(m_Value(NotOp0))) && + InstCombiner::isFreeToInvert(Op1, /*WillInvertAllUses=*/true) && + (match(Op1, m_ImmConstant()) || + (isa<Instruction>(Op1) && + InstCombiner::canFreelyInvertAllUsersOf(cast<Instruction>(Op1), + /*IgnoredUser=*/&I)))) { + Op0 = NotOp0; + OpToInvert = &Op1; + } else if (match(Op1, m_Not(m_Value(NotOp1))) && + InstCombiner::isFreeToInvert(Op0, /*WillInvertAllUses=*/true) && + (match(Op0, m_ImmConstant()) || + (isa<Instruction>(Op0) && + InstCombiner::canFreelyInvertAllUsersOf(cast<Instruction>(Op0), + /*IgnoredUser=*/&I)))) { + Op1 = NotOp1; + OpToInvert = &Op0; + } else return false; // And can our users be adapted? if (!InstCombiner::canFreelyInvertAllUsersOf(&I, /*IgnoredUser=*/nullptr)) return false; - Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not"); - Value *NewBinOp = - BinaryOperator::Create(NewOpc, X, NotY, I.getName() + ".not"); - Builder.Insert(NewBinOp); + if (auto *C = dyn_cast<Constant>(*OpToInvert)) { + *OpToInvert = ConstantExpr::getNot(C); + } else { + Builder.SetInsertPoint( + &*cast<Instruction>(*OpToInvert)->getInsertionPointAfterDef()); + Value *NotOpToInvert = + Builder.CreateNot(*OpToInvert, (*OpToInvert)->getName() + ".not"); + (*OpToInvert)->replaceUsesWithIf(NotOpToInvert, [NotOpToInvert](Use &U) { + return U.getUser() != NotOpToInvert; + }); + freelyInvertAllUsersOf(NotOpToInvert, /*IgnoredUser=*/&I); + *OpToInvert = NotOpToInvert; + } + + Builder.SetInsertPoint(&*I.getInsertionPointAfterDef()); + Value *NewBinOp; + if (IsBinaryOp) + NewBinOp = Builder.CreateBinOp(NewOpc, Op0, Op1, I.getName() + ".not"); + else + NewBinOp = Builder.CreateLogicalOp(NewOpc, Op0, Op1, I.getName() + ".not"); replaceInstUsesWith(I, NewBinOp); // We can not just create an outer `not`, it will most likely be immediately // folded back, reconstructing our initial pattern, and causing an @@ -3472,23 +3884,6 @@ Instruction *InstCombinerImpl::foldNot(BinaryOperator &I) { // Is this a 'not' (~) fed by a binary operator? BinaryOperator *NotVal; if (match(NotOp, m_BinOp(NotVal))) { - if (NotVal->getOpcode() == Instruction::And || - NotVal->getOpcode() == Instruction::Or) { - // Apply DeMorgan's Law when inverts are free: - // ~(X & Y) --> (~X | ~Y) - // ~(X | Y) --> (~X & ~Y) - if (isFreeToInvert(NotVal->getOperand(0), - NotVal->getOperand(0)->hasOneUse()) && - isFreeToInvert(NotVal->getOperand(1), - NotVal->getOperand(1)->hasOneUse())) { - Value *NotX = Builder.CreateNot(NotVal->getOperand(0), "notlhs"); - Value *NotY = Builder.CreateNot(NotVal->getOperand(1), "notrhs"); - if (NotVal->getOpcode() == Instruction::And) - return BinaryOperator::CreateOr(NotX, NotY); - return BinaryOperator::CreateAnd(NotX, NotY); - } - } - // ~((-X) | Y) --> (X - 1) & (~Y) if (match(NotVal, m_OneUse(m_c_Or(m_OneUse(m_Neg(m_Value(X))), m_Value(Y))))) { @@ -3501,6 +3896,14 @@ Instruction *InstCombinerImpl::foldNot(BinaryOperator &I) { if (match(NotVal, m_AShr(m_Not(m_Value(X)), m_Value(Y)))) return BinaryOperator::CreateAShr(X, Y); + // Bit-hack form of a signbit test: + // iN ~X >>s (N-1) --> sext i1 (X > -1) to iN + unsigned FullShift = Ty->getScalarSizeInBits() - 1; + if (match(NotVal, m_OneUse(m_AShr(m_Value(X), m_SpecificInt(FullShift))))) { + Value *IsNotNeg = Builder.CreateIsNotNeg(X, "isnotneg"); + return new SExtInst(IsNotNeg, Ty); + } + // If we are inverting a right-shifted constant, we may be able to eliminate // the 'not' by inverting the constant and using the opposite shift type. // Canonicalization rules ensure that only a negative constant uses 'ashr', @@ -3545,11 +3948,28 @@ Instruction *InstCombinerImpl::foldNot(BinaryOperator &I) { // not (cmp A, B) = !cmp A, B CmpInst::Predicate Pred; - if (match(NotOp, m_OneUse(m_Cmp(Pred, m_Value(), m_Value())))) { + if (match(NotOp, m_Cmp(Pred, m_Value(), m_Value())) && + (NotOp->hasOneUse() || + InstCombiner::canFreelyInvertAllUsersOf(cast<Instruction>(NotOp), + /*IgnoredUser=*/nullptr))) { cast<CmpInst>(NotOp)->setPredicate(CmpInst::getInversePredicate(Pred)); - return replaceInstUsesWith(I, NotOp); + freelyInvertAllUsersOf(NotOp); + return &I; + } + + // Move a 'not' ahead of casts of a bool to enable logic reduction: + // not (bitcast (sext i1 X)) --> bitcast (sext (not i1 X)) + if (match(NotOp, m_OneUse(m_BitCast(m_OneUse(m_SExt(m_Value(X)))))) && X->getType()->isIntOrIntVectorTy(1)) { + Type *SextTy = cast<BitCastOperator>(NotOp)->getSrcTy(); + Value *NotX = Builder.CreateNot(X); + Value *Sext = Builder.CreateSExt(NotX, SextTy); + return CastInst::CreateBitOrPointerCast(Sext, Ty); } + if (auto *NotOpI = dyn_cast<Instruction>(NotOp)) + if (sinkNotIntoLogicalOp(*NotOpI)) + return &I; + // Eliminate a bitwise 'not' op of 'not' min/max by inverting the min/max: // ~min(~X, ~Y) --> max(X, Y) // ~max(~X, Y) --> min(X, ~Y) @@ -3570,6 +3990,14 @@ Instruction *InstCombinerImpl::foldNot(BinaryOperator &I) { Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, X, NotY); return replaceInstUsesWith(I, InvMaxMin); } + + if (II->getIntrinsicID() == Intrinsic::is_fpclass) { + ConstantInt *ClassMask = cast<ConstantInt>(II->getArgOperand(1)); + II->setArgOperand( + 1, ConstantInt::get(ClassMask->getType(), + ~ClassMask->getZExtValue() & fcAllFlags)); + return replaceInstUsesWith(I, II); + } } if (NotOp->hasOneUse()) { @@ -3602,7 +4030,7 @@ Instruction *InstCombinerImpl::foldNot(BinaryOperator &I) { } } - if (Instruction *NewXor = sinkNotIntoXor(I, Builder)) + if (Instruction *NewXor = foldNotXor(I, Builder)) return NewXor; return nullptr; @@ -3629,7 +4057,7 @@ Instruction *InstCombinerImpl::visitXor(BinaryOperator &I) { return NewXor; // (A&B)^(A&C) -> A&(B^C) etc - if (Value *V = SimplifyUsingDistributiveLaws(I)) + if (Value *V = foldUsingDistributiveLaws(I)) return replaceInstUsesWith(I, V); // See if we can simplify any instructions used by the instruction whose sole @@ -3718,6 +4146,21 @@ Instruction *InstCombinerImpl::visitXor(BinaryOperator &I) { MaskedValueIsZero(X, *C, 0, &I)) return BinaryOperator::CreateXor(X, ConstantInt::get(Ty, *C ^ *RHSC)); + // When X is a power-of-two or zero and zero input is poison: + // ctlz(i32 X) ^ 31 --> cttz(X) + // cttz(i32 X) ^ 31 --> ctlz(X) + auto *II = dyn_cast<IntrinsicInst>(Op0); + if (II && II->hasOneUse() && *RHSC == Ty->getScalarSizeInBits() - 1) { + Intrinsic::ID IID = II->getIntrinsicID(); + if ((IID == Intrinsic::ctlz || IID == Intrinsic::cttz) && + match(II->getArgOperand(1), m_One()) && + isKnownToBeAPowerOfTwo(II->getArgOperand(0), /*OrZero */ true)) { + IID = (IID == Intrinsic::ctlz) ? Intrinsic::cttz : Intrinsic::ctlz; + Function *F = Intrinsic::getDeclaration(II->getModule(), IID, Ty); + return CallInst::Create(F, {II->getArgOperand(0), Builder.getTrue()}); + } + } + // If RHSC is inverting the remaining bits of shifted X, // canonicalize to a 'not' before the shift to help SCEV and codegen: // (X << C) ^ RHSC --> ~X << C @@ -3858,5 +4301,17 @@ Instruction *InstCombinerImpl::visitXor(BinaryOperator &I) { m_Value(Y)))) return BinaryOperator::CreateXor(Builder.CreateXor(X, Y), C1); + if (Instruction *R = reassociateForUses(I, Builder)) + return R; + + if (Instruction *Canonicalized = canonicalizeLogicFirst(I, Builder)) + return Canonicalized; + + if (Instruction *Folded = foldLogicOfIsFPClass(I, Op0, Op1)) + return Folded; + + if (Instruction *Folded = canonicalizeConditionalNegationViaMathToSelect(I)) + return Folded; + return nullptr; } |