diff options
Diffstat (limited to 'llvm/lib/Transforms/InstCombine')
8 files changed, 126 insertions, 67 deletions
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp index 06c9bf650f37..dc55b5a31596 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -1727,16 +1727,18 @@ static Instruction *foldComplexAndOrPatterns(BinaryOperator &I, (Opcode == Instruction::And) ? Instruction::Or : Instruction::And; Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); - Value *A, *B, *C; + Value *A, *B, *C, *X, *Y; // (~(A | B) & C) | ... --> ... // (~(A & B) | C) & ... --> ... // TODO: One use checks are conservative. We just need to check that a total // number of multiple used values does not exceed reduction // in operations. - if (match(Op0, m_c_BinOp(FlippedOpcode, - m_Not(m_BinOp(Opcode, m_Value(A), m_Value(B))), - m_Value(C)))) { + if (match(Op0, + m_c_BinOp(FlippedOpcode, + m_CombineAnd(m_Value(X), m_Not(m_BinOp(Opcode, m_Value(A), + m_Value(B)))), + m_Value(C)))) { // (~(A | B) & C) | (~(A | C) & B) --> (B ^ C) & ~A // (~(A & B) | C) & (~(A & C) | B) --> ~((B ^ C) & A) if (match(Op1, @@ -1776,6 +1778,21 @@ static Instruction *foldComplexAndOrPatterns(BinaryOperator &I, m_c_BinOp(Opcode, m_Specific(B), m_Specific(C))))))) return BinaryOperator::CreateNot(Builder.CreateBinOp( Opcode, Builder.CreateBinOp(FlippedOpcode, A, C), B)); + + // (~(A | B) & C) | ~(C | (A ^ B)) --> ~((A | B) & (C | (A ^ B))) + // Note, the pattern with swapped and/or is not handled because the + // result is more undefined than a source: + // (~(A & B) | C) & ~(C & (A ^ B)) --> (A ^ B ^ C) | ~(A | C) is invalid. + if (Opcode == Instruction::Or && Op0->hasOneUse() && + match(Op1, m_OneUse(m_Not(m_CombineAnd( + m_Value(Y), + m_c_BinOp(Opcode, m_Specific(C), + m_c_Xor(m_Specific(A), m_Specific(B)))))))) { + // X = ~(A | B) + // Y = (C | (A ^ B) + Value *Or = cast<BinaryOperator>(X)->getOperand(0); + return BinaryOperator::CreateNot(Builder.CreateAnd(Or, Y)); + } } return nullptr; @@ -2061,7 +2078,14 @@ Instruction *InstCombinerImpl::visitAnd(BinaryOperator &I) { if (Instruction *CastedAnd = foldCastedBitwiseLogic(I)) return CastedAnd; + if (Instruction *Sel = foldBinopOfSextBoolToSelect(I)) + return Sel; + // and(sext(A), B) / and(B, sext(A)) --> A ? B : 0, where A is i1 or <N x i1>. + // TODO: Move this into foldBinopOfSextBoolToSelect as a more generalized fold + // with binop identity constant. But creating a select with non-constant + // arm may not be reversible due to poison semantics. Is that a good + // canonicalization? Value *A; if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) && A->getType()->isIntOrIntVectorTy(1)) @@ -2322,11 +2346,20 @@ Value *InstCombinerImpl::getSelectCondition(Value *A, Value *B) { Value *Cond; Value *NotB; if (match(A, m_SExt(m_Value(Cond))) && - Cond->getType()->isIntOrIntVectorTy(1) && - match(B, m_OneUse(m_Not(m_Value(NotB))))) { - NotB = peekThroughBitcast(NotB, true); - if (match(NotB, m_SExt(m_Specific(Cond)))) + Cond->getType()->isIntOrIntVectorTy(1)) { + // A = sext i1 Cond; B = sext (not (i1 Cond)) + if (match(B, m_SExt(m_Not(m_Specific(Cond))))) return Cond; + + // A = sext i1 Cond; B = not ({bitcast} (sext (i1 Cond))) + // TODO: The one-use checks are unnecessary or misplaced. If the caller + // checked for uses on logic ops/casts, that should be enough to + // make this transform worthwhile. + if (match(B, m_OneUse(m_Not(m_Value(NotB))))) { + NotB = peekThroughBitcast(NotB, true); + if (match(NotB, m_SExt(m_Specific(Cond)))) + return Cond; + } } // All scalar (and most vector) possibilities should be handled now. @@ -2569,7 +2602,8 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) { return replaceInstUsesWith(I, V); Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); - if (I.getType()->isIntOrIntVectorTy(1)) { + Type *Ty = I.getType(); + if (Ty->isIntOrIntVectorTy(1)) { if (auto *SI0 = dyn_cast<SelectInst>(Op0)) { if (auto *I = foldAndOrOfSelectUsingImpliedCond(Op1, *SI0, /* IsAnd */ false)) @@ -2602,7 +2636,16 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) { // (X ^ C) | Y -> (X | Y) ^ C iff Y & C == 0 // The check for a 'not' op is for efficiency (if Y is known zero --> ~X). Value *Or = Builder.CreateOr(X, Y); - return BinaryOperator::CreateXor(Or, ConstantInt::get(I.getType(), *CV)); + return BinaryOperator::CreateXor(Or, ConstantInt::get(Ty, *CV)); + } + + // If the operands have no common bits set: + // or (mul X, Y), X --> add (mul X, Y), X --> mul X, (Y + 1) + if (match(&I, + m_c_Or(m_OneUse(m_Mul(m_Value(X), m_Value(Y))), m_Deferred(X))) && + haveNoCommonBitsSet(Op0, Op1, DL)) { + Value *IncrementY = Builder.CreateAdd(Y, ConstantInt::get(Ty, 1)); + return BinaryOperator::CreateMul(X, IncrementY); } // (A & C) | (B & D) @@ -2635,14 +2678,14 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) { // iff (C0 & C1) == 0 and (X & ~C0) == 0 if (match(A, m_c_Or(m_Value(X), m_Specific(B))) && MaskedValueIsZero(X, ~*C0, 0, &I)) { - Constant *C01 = ConstantInt::get(I.getType(), *C0 | *C1); + Constant *C01 = ConstantInt::get(Ty, *C0 | *C1); return BinaryOperator::CreateAnd(A, C01); } // (A & C0) | ((X | A) & C1) --> (X | A) & (C0 | C1) // iff (C0 & C1) == 0 and (X & ~C1) == 0 if (match(B, m_c_Or(m_Value(X), m_Specific(A))) && MaskedValueIsZero(X, ~*C1, 0, &I)) { - Constant *C01 = ConstantInt::get(I.getType(), *C0 | *C1); + Constant *C01 = ConstantInt::get(Ty, *C0 | *C1); return BinaryOperator::CreateAnd(B, C01); } // ((X | C2) & C0) | ((X | C3) & C1) --> (X | C2 | C3) & (C0 | C1) @@ -2652,7 +2695,7 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) { match(B, m_Or(m_Specific(X), m_APInt(C3))) && (*C2 & ~*C0).isZero() && (*C3 & ~*C1).isZero()) { Value *Or = Builder.CreateOr(X, *C2 | *C3, "bitfield"); - Constant *C01 = ConstantInt::get(I.getType(), *C0 | *C1); + Constant *C01 = ConstantInt::get(Ty, *C0 | *C1); return BinaryOperator::CreateAnd(Or, C01); } } @@ -2788,13 +2831,20 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) { if (Instruction *CastedOr = foldCastedBitwiseLogic(I)) return CastedOr; + if (Instruction *Sel = foldBinopOfSextBoolToSelect(I)) + return Sel; + // or(sext(A), B) / or(B, sext(A)) --> A ? -1 : B, where A is i1 or <N x i1>. + // TODO: Move this into foldBinopOfSextBoolToSelect as a more generalized fold + // with binop identity constant. But creating a select with non-constant + // arm may not be reversible due to poison semantics. Is that a good + // canonicalization? if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) && A->getType()->isIntOrIntVectorTy(1)) - return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op1); + return SelectInst::Create(A, ConstantInt::getAllOnesValue(Ty), Op1); if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) && A->getType()->isIntOrIntVectorTy(1)) - return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op0); + return SelectInst::Create(A, ConstantInt::getAllOnesValue(Ty), Op0); // Note: If we've gotten to the point of visiting the outer OR, then the // inner one couldn't be simplified. If it was a constant, then it won't @@ -2826,7 +2876,6 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) { // or(ashr(subNSW(Y, X), ScalarSizeInBits(Y) - 1), X) --> X s> Y ? -1 : X. { Value *X, *Y; - Type *Ty = I.getType(); if (match(&I, m_c_Or(m_OneUse(m_AShr( m_NSWSub(m_Value(Y), m_Value(X)), m_SpecificInt(Ty->getScalarSizeInBits() - 1))), @@ -2876,7 +2925,6 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) { if (match(&I, m_c_Or(m_Add(m_Shl(m_One(), m_Value(X)), m_AllOnes()), m_Shl(m_One(), m_Deferred(X)))) && match(&I, m_c_Or(m_OneUse(m_Value()), m_Value()))) { - Type *Ty = X->getType(); Value *Sub = Builder.CreateSub( ConstantInt::get(Ty, Ty->getScalarSizeInBits() - 1), X); return BinaryOperator::CreateLShr(Constant::getAllOnesValue(Ty), Sub); @@ -3601,6 +3649,14 @@ Instruction *InstCombinerImpl::visitXor(BinaryOperator &I) { if (match(&I, m_c_Xor(m_c_And(m_Not(m_Value(A)), m_Value(B)), m_Deferred(A)))) return BinaryOperator::CreateOr(A, B); + // (~A | B) ^ A --> ~(A & B) + if (match(Op0, m_OneUse(m_c_Or(m_Not(m_Specific(Op1)), m_Value(B))))) + return BinaryOperator::CreateNot(Builder.CreateAnd(Op1, B)); + + // A ^ (~A | B) --> ~(A & B) + if (match(Op1, m_OneUse(m_c_Or(m_Not(m_Specific(Op0)), m_Value(B))))) + return BinaryOperator::CreateNot(Builder.CreateAnd(Op0, B)); + // (A | B) ^ (A | C) --> (B ^ C) & ~A -- There are 4 commuted variants. // TODO: Loosen one-use restriction if common operand is a constant. Value *D; diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp index bfa7bfa2290a..7da2669e1d13 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp @@ -2641,7 +2641,7 @@ Instruction *InstCombinerImpl::visitCallBase(CallBase &Call) { ArgNo++; } - assert(ArgNo == Call.arg_size() && "sanity check"); + assert(ArgNo == Call.arg_size() && "Call arguments not processed correctly."); if (!ArgNos.empty()) { AttributeList AS = Call.getAttributes(); diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp index ca87477c5d81..33f217659c01 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp @@ -2771,7 +2771,7 @@ Instruction *InstCombinerImpl::visitBitCast(BitCastInst &CI) { if (match(Src, m_OneUse(m_InsertElt(m_OneUse(m_BitCast(m_Value(X))), m_Value(Y), m_ConstantInt(IndexC)))) && DestTy->isIntegerTy() && X->getType() == DestTy && - isDesirableIntType(BitWidth)) { + Y->getType()->isIntegerTy() && isDesirableIntType(BitWidth)) { // Adjust for big endian - the LSBs are at the high index. if (DL.isBigEndian()) IndexC = SrcVTy->getNumElements() - 1 - IndexC; diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp index 7a9e177f19da..ed53b88aed61 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -14,6 +14,7 @@ #include "llvm/ADT/APSInt.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/CmpInstAnalysis.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/TargetLibraryInfo.h" @@ -1894,23 +1895,6 @@ Instruction *InstCombinerImpl::foldICmpAndConstant(ICmpInst &Cmp, return new ICmpInst(NewPred, X, SubOne(cast<Constant>(Cmp.getOperand(1)))); } - // (X & C2) == 0 -> (trunc X) >= 0 - // (X & C2) != 0 -> (trunc X) < 0 - // iff C2 is a power of 2 and it masks the sign bit of a legal integer type. - const APInt *C2; - if (And->hasOneUse() && C.isZero() && match(Y, m_APInt(C2))) { - int32_t ExactLogBase2 = C2->exactLogBase2(); - if (ExactLogBase2 != -1 && DL.isLegalInteger(ExactLogBase2 + 1)) { - Type *NTy = IntegerType::get(Cmp.getContext(), ExactLogBase2 + 1); - if (auto *AndVTy = dyn_cast<VectorType>(And->getType())) - NTy = VectorType::get(NTy, AndVTy->getElementCount()); - Value *Trunc = Builder.CreateTrunc(X, NTy); - auto NewPred = - Pred == CmpInst::ICMP_EQ ? CmpInst::ICMP_SGE : CmpInst::ICMP_SLT; - return new ICmpInst(NewPred, Trunc, Constant::getNullValue(NTy)); - } - } - return nullptr; } @@ -2803,7 +2787,8 @@ bool InstCombinerImpl::matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, PredB, cast<Constant>(RHS2)); if (!FlippedStrictness) return false; - assert(FlippedStrictness->first == ICmpInst::ICMP_SGE && "Sanity check"); + assert(FlippedStrictness->first == ICmpInst::ICMP_SGE && + "basic correctness failure"); RHS2 = FlippedStrictness->second; // And kind-of perform the result swap. std::swap(Less, Greater); @@ -4614,7 +4599,7 @@ Instruction *InstCombinerImpl::foldICmpEquality(ICmpInst &I) { static Instruction *foldICmpWithTrunc(ICmpInst &ICmp, InstCombiner::BuilderTy &Builder) { - const ICmpInst::Predicate Pred = ICmp.getPredicate(); + ICmpInst::Predicate Pred = ICmp.getPredicate(); Value *Op0 = ICmp.getOperand(0), *Op1 = ICmp.getOperand(1); // Try to canonicalize trunc + compare-to-constant into a mask + cmp. @@ -4624,41 +4609,31 @@ static Instruction *foldICmpWithTrunc(ICmpInst &ICmp, if (!match(Op0, m_OneUse(m_Trunc(m_Value(X)))) || !match(Op1, m_APInt(C))) return nullptr; + // This matches patterns corresponding to tests of the signbit as well as: + // (trunc X) u< C --> (X & -C) == 0 (are all masked-high-bits clear?) + // (trunc X) u> C --> (X & ~C) != 0 (are any masked-high-bits set?) + APInt Mask; + if (decomposeBitTestICmp(Op0, Op1, Pred, X, Mask, true /* WithTrunc */)) { + Value *And = Builder.CreateAnd(X, Mask); + Constant *Zero = ConstantInt::getNullValue(X->getType()); + return new ICmpInst(Pred, And, Zero); + } + unsigned SrcBits = X->getType()->getScalarSizeInBits(); - if (Pred == ICmpInst::ICMP_ULT) { - if (C->isPowerOf2()) { - // If C is a power-of-2 (one set bit): - // (trunc X) u< C --> (X & -C) == 0 (are all masked-high-bits clear?) - Constant *MaskC = ConstantInt::get(X->getType(), (-*C).zext(SrcBits)); - Value *And = Builder.CreateAnd(X, MaskC); - Constant *Zero = ConstantInt::getNullValue(X->getType()); - return new ICmpInst(ICmpInst::ICMP_EQ, And, Zero); - } + if (Pred == ICmpInst::ICMP_ULT && C->isNegatedPowerOf2()) { // If C is a negative power-of-2 (high-bit mask): // (trunc X) u< C --> (X & C) != C (are any masked-high-bits clear?) - if (C->isNegatedPowerOf2()) { - Constant *MaskC = ConstantInt::get(X->getType(), C->zext(SrcBits)); - Value *And = Builder.CreateAnd(X, MaskC); - return new ICmpInst(ICmpInst::ICMP_NE, And, MaskC); - } + Constant *MaskC = ConstantInt::get(X->getType(), C->zext(SrcBits)); + Value *And = Builder.CreateAnd(X, MaskC); + return new ICmpInst(ICmpInst::ICMP_NE, And, MaskC); } - if (Pred == ICmpInst::ICMP_UGT) { - // If C is a low-bit-mask (C+1 is a power-of-2): - // (trunc X) u> C --> (X & ~C) != 0 (are any masked-high-bits set?) - if (C->isMask()) { - Constant *MaskC = ConstantInt::get(X->getType(), (~*C).zext(SrcBits)); - Value *And = Builder.CreateAnd(X, MaskC); - Constant *Zero = ConstantInt::getNullValue(X->getType()); - return new ICmpInst(ICmpInst::ICMP_NE, And, Zero); - } + if (Pred == ICmpInst::ICMP_UGT && (~*C).isPowerOf2()) { // If C is not-of-power-of-2 (one clear bit): // (trunc X) u> C --> (X & (C+1)) == C+1 (are all masked-high-bits set?) - if ((~*C).isPowerOf2()) { - Constant *MaskC = ConstantInt::get(X->getType(), (*C + 1).zext(SrcBits)); - Value *And = Builder.CreateAnd(X, MaskC); - return new ICmpInst(ICmpInst::ICMP_EQ, And, MaskC); - } + Constant *MaskC = ConstantInt::get(X->getType(), (*C + 1).zext(SrcBits)); + Value *And = Builder.CreateAnd(X, MaskC); + return new ICmpInst(ICmpInst::ICMP_EQ, And, MaskC); } return nullptr; diff --git a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h index 72e1b21e8d49..20c75188ec9f 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h +++ b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h @@ -319,6 +319,7 @@ private: Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN); Instruction *foldBitcastExtElt(ExtractElementInst &ExtElt); Instruction *foldCastedBitwiseLogic(BinaryOperator &I); + Instruction *foldBinopOfSextBoolToSelect(BinaryOperator &I); Instruction *narrowBinOp(TruncInst &Trunc); Instruction *narrowMaskedBinOp(BinaryOperator &And); Instruction *narrowMathIfNoOverflow(BinaryOperator &I); diff --git a/llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp b/llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp index 7dc516c6fdc3..42ba4a34a5a9 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp @@ -403,7 +403,7 @@ LLVM_NODISCARD Value *Negator::visitImpl(Value *V, unsigned Depth) { NonNegatedOps.emplace_back(Op); // Just record which operand that was. } assert((NegatedOps.size() + NonNegatedOps.size()) == 2 && - "Internal consistency sanity check."); + "Internal consistency check failed."); // Did we manage to sink negation into both of the operands? if (NegatedOps.size() == 2) // Then we get to keep the `add`! return Builder.CreateAdd(NegatedOps[0], NegatedOps[1], diff --git a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp index 4a1e82ae9c1d..518d3952dce5 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp @@ -246,12 +246,16 @@ static Value *foldSelectICmpAnd(SelectInst &Sel, ICmpInst *Cmp, static unsigned getSelectFoldableOperands(BinaryOperator *I) { switch (I->getOpcode()) { case Instruction::Add: + case Instruction::FAdd: case Instruction::Mul: + case Instruction::FMul: case Instruction::And: case Instruction::Or: case Instruction::Xor: return 3; // Can fold through either operand. case Instruction::Sub: // Can only fold on the amount subtracted. + case Instruction::FSub: + case Instruction::FDiv: // Can only fold on the divisor amount. case Instruction::Shl: // Can only fold on the shift amount. case Instruction::LShr: case Instruction::AShr: diff --git a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp index 47b6dcb67a78..1f81624f79e7 100644 --- a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -967,6 +967,29 @@ Value *InstCombinerImpl::dyn_castNegVal(Value *V) const { return nullptr; } +/// A binop with a constant operand and a sign-extended boolean operand may be +/// converted into a select of constants by applying the binary operation to +/// the constant with the two possible values of the extended boolean (0 or -1). +Instruction *InstCombinerImpl::foldBinopOfSextBoolToSelect(BinaryOperator &BO) { + // TODO: Handle non-commutative binop (constant is operand 0). + // TODO: Handle zext. + // TODO: Peek through 'not' of cast. + Value *BO0 = BO.getOperand(0); + Value *BO1 = BO.getOperand(1); + Value *X; + Constant *C; + if (!match(BO0, m_SExt(m_Value(X))) || !match(BO1, m_ImmConstant(C)) || + !X->getType()->isIntOrIntVectorTy(1)) + return nullptr; + + // bo (sext i1 X), C --> select X, (bo -1, C), (bo 0, C) + Constant *Ones = ConstantInt::getAllOnesValue(BO.getType()); + Constant *Zero = ConstantInt::getNullValue(BO.getType()); + Constant *TVal = ConstantExpr::get(BO.getOpcode(), Ones, C); + Constant *FVal = ConstantExpr::get(BO.getOpcode(), Zero, C); + return SelectInst::Create(X, TVal, FVal); +} + static Value *foldOperationIntoSelectOperand(Instruction &I, Value *SO, InstCombiner::BuilderTy &Builder) { if (auto *Cast = dyn_cast<CastInst>(&I)) |