diff options
Diffstat (limited to 'contrib/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp')
| -rw-r--r-- | contrib/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp | 193 |
1 files changed, 162 insertions, 31 deletions
diff --git a/contrib/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp b/contrib/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp index 6e196bfdbd25..ba15b023f2a3 100644 --- a/contrib/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp +++ b/contrib/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp @@ -1,9 +1,8 @@ //===- InstCombineAddSub.cpp ------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // @@ -823,6 +822,47 @@ static Value *checkForNegativeOperand(BinaryOperator &I, return nullptr; } +/// Wrapping flags may allow combining constants separated by an extend. +static Instruction *foldNoWrapAdd(BinaryOperator &Add, + InstCombiner::BuilderTy &Builder) { + Value *Op0 = Add.getOperand(0), *Op1 = Add.getOperand(1); + Type *Ty = Add.getType(); + Constant *Op1C; + if (!match(Op1, m_Constant(Op1C))) + return nullptr; + + // Try this match first because it results in an add in the narrow type. + // (zext (X +nuw C2)) + C1 --> zext (X + (C2 + trunc(C1))) + Value *X; + const APInt *C1, *C2; + if (match(Op1, m_APInt(C1)) && + match(Op0, m_OneUse(m_ZExt(m_NUWAdd(m_Value(X), m_APInt(C2))))) && + C1->isNegative() && C1->sge(-C2->sext(C1->getBitWidth()))) { + Constant *NewC = + ConstantInt::get(X->getType(), *C2 + C1->trunc(C2->getBitWidth())); + return new ZExtInst(Builder.CreateNUWAdd(X, NewC), Ty); + } + + // More general combining of constants in the wide type. + // (sext (X +nsw NarrowC)) + C --> (sext X) + (sext(NarrowC) + C) + Constant *NarrowC; + if (match(Op0, m_OneUse(m_SExt(m_NSWAdd(m_Value(X), m_Constant(NarrowC)))))) { + Constant *WideC = ConstantExpr::getSExt(NarrowC, Ty); + Constant *NewC = ConstantExpr::getAdd(WideC, Op1C); + Value *WideX = Builder.CreateSExt(X, Ty); + return BinaryOperator::CreateAdd(WideX, NewC); + } + // (zext (X +nuw NarrowC)) + C --> (zext X) + (zext(NarrowC) + C) + if (match(Op0, m_OneUse(m_ZExt(m_NUWAdd(m_Value(X), m_Constant(NarrowC)))))) { + Constant *WideC = ConstantExpr::getZExt(NarrowC, Ty); + Constant *NewC = ConstantExpr::getAdd(WideC, Op1C); + Value *WideX = Builder.CreateZExt(X, Ty); + return BinaryOperator::CreateAdd(WideX, NewC); + } + + return nullptr; +} + Instruction *InstCombiner::foldAddWithConstant(BinaryOperator &Add) { Value *Op0 = Add.getOperand(0), *Op1 = Add.getOperand(1); Constant *Op1C; @@ -832,7 +872,14 @@ Instruction *InstCombiner::foldAddWithConstant(BinaryOperator &Add) { if (Instruction *NV = foldBinOpIntoSelectOrPhi(Add)) return NV; - Value *X, *Y; + Value *X; + Constant *Op00C; + + // add (sub C1, X), C2 --> sub (add C1, C2), X + if (match(Op0, m_Sub(m_Constant(Op00C), m_Value(X)))) + return BinaryOperator::CreateSub(ConstantExpr::getAdd(Op00C, Op1C), X); + + Value *Y; // add (sub X, Y), -1 --> add (not Y), X if (match(Op0, m_OneUse(m_Sub(m_Value(X), m_Value(Y)))) && @@ -852,6 +899,11 @@ Instruction *InstCombiner::foldAddWithConstant(BinaryOperator &Add) { if (!match(Op1, m_APInt(C))) return nullptr; + // (X | C2) + C --> (X | C2) ^ C2 iff (C2 == -C) + const APInt *C2; + if (match(Op0, m_Or(m_Value(), m_APInt(C2))) && *C2 == -*C) + return BinaryOperator::CreateXor(Op0, ConstantInt::get(Add.getType(), *C2)); + if (C->isSignMask()) { // If wrapping is not allowed, then the addition must set the sign bit: // X + (signmask) --> X | signmask @@ -866,19 +918,10 @@ Instruction *InstCombiner::foldAddWithConstant(BinaryOperator &Add) { // Is this add the last step in a convoluted sext? // add(zext(xor i16 X, -32768), -32768) --> sext X Type *Ty = Add.getType(); - const APInt *C2; if (match(Op0, m_ZExt(m_Xor(m_Value(X), m_APInt(C2)))) && C2->isMinSignedValue() && C2->sext(Ty->getScalarSizeInBits()) == *C) return CastInst::Create(Instruction::SExt, X, Ty); - // (add (zext (add nuw X, C2)), C) --> (zext (add nuw X, C2 + C)) - if (match(Op0, m_OneUse(m_ZExt(m_NUWAdd(m_Value(X), m_APInt(C2))))) && - C->isNegative() && C->sge(-C2->sext(C->getBitWidth()))) { - Constant *NewC = - ConstantInt::get(X->getType(), *C2 + C->trunc(C2->getBitWidth())); - return new ZExtInst(Builder.CreateNUWAdd(X, NewC), Ty); - } - if (C->isOneValue() && Op0->hasOneUse()) { // add (sext i1 X), 1 --> zext (not X) // TODO: The smallest IR representation is (select X, 0, 1), and that would @@ -1032,6 +1075,28 @@ static Instruction *canonicalizeLowbitMask(BinaryOperator &I, return BinaryOperator::CreateNot(NotMask, I.getName()); } +static Instruction *foldToUnsignedSaturatedAdd(BinaryOperator &I) { + assert(I.getOpcode() == Instruction::Add && "Expecting add instruction"); + Type *Ty = I.getType(); + auto getUAddSat = [&]() { + return Intrinsic::getDeclaration(I.getModule(), Intrinsic::uadd_sat, Ty); + }; + + // add (umin X, ~Y), Y --> uaddsat X, Y + Value *X, *Y; + if (match(&I, m_c_Add(m_c_UMin(m_Value(X), m_Not(m_Value(Y))), + m_Deferred(Y)))) + return CallInst::Create(getUAddSat(), { X, Y }); + + // add (umin X, ~C), C --> uaddsat X, C + const APInt *C, *NotC; + if (match(&I, m_Add(m_UMin(m_Value(X), m_APInt(NotC)), m_APInt(C))) && + *C == ~*NotC) + return CallInst::Create(getUAddSat(), { X, ConstantInt::get(Ty, *C) }); + + return nullptr; +} + Instruction *InstCombiner::visitAdd(BinaryOperator &I) { if (Value *V = SimplifyAddInst(I.getOperand(0), I.getOperand(1), I.hasNoSignedWrap(), I.hasNoUnsignedWrap(), @@ -1051,6 +1116,9 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) { if (Instruction *X = foldAddWithConstant(I)) return X; + if (Instruction *X = foldNoWrapAdd(I, Builder)) + return X; + // FIXME: This should be moved into the above helper function to allow these // transforms for general constant or constant splat vectors. Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); @@ -1119,6 +1187,12 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) { return BinaryOperator::CreateSub(RHS, A); } + // Canonicalize sext to zext for better value tracking potential. + // add A, sext(B) --> sub A, zext(B) + if (match(&I, m_c_Add(m_Value(A), m_OneUse(m_SExt(m_Value(B))))) && + B->getType()->isIntOrIntVectorTy(1)) + return BinaryOperator::CreateSub(A, Builder.CreateZExt(B, Ty)); + // A + -B --> A - B if (match(RHS, m_Neg(m_Value(B)))) return BinaryOperator::CreateSub(LHS, B); @@ -1128,7 +1202,10 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) { // (A + 1) + ~B --> A - B // ~B + (A + 1) --> A - B - if (match(&I, m_c_BinOp(m_Add(m_Value(A), m_One()), m_Not(m_Value(B))))) + // (~B + A) + 1 --> A - B + // (A + ~B) + 1 --> A - B + if (match(&I, m_c_BinOp(m_Add(m_Value(A), m_One()), m_Not(m_Value(B)))) || + match(&I, m_BinOp(m_c_Add(m_Not(m_Value(B)), m_Value(A)), m_One()))) return BinaryOperator::CreateSub(A, B); // X % C0 + (( X / C0 ) % C1) * C0 => X % (C0 * C1) @@ -1225,6 +1302,9 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) { if (Instruction *V = canonicalizeLowbitMask(I, Builder)) return V; + if (Instruction *SatAdd = foldToUnsignedSaturatedAdd(I)) + return SatAdd; + return Changed ? &I : nullptr; } @@ -1500,6 +1580,12 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) { if (match(Op1, m_OneUse(m_Add(m_Value(X), m_One())))) return BinaryOperator::CreateAdd(Builder.CreateNot(X), Op0); + // Y - ~X --> (X + 1) + Y + if (match(Op1, m_OneUse(m_Not(m_Value(X))))) { + return BinaryOperator::CreateAdd( + Builder.CreateAdd(Op0, ConstantInt::get(I.getType(), 1)), X); + } + if (Constant *C = dyn_cast<Constant>(Op0)) { bool IsNegate = match(C, m_ZeroInt()); Value *X; @@ -1532,8 +1618,13 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) { if (Instruction *R = foldOpIntoPhi(I, PN)) return R; - // C-(X+C2) --> (C-C2)-X Constant *C2; + + // C-(C2-X) --> X+(C-C2) + if (match(Op1, m_Sub(m_Constant(C2), m_Value(X)))) + return BinaryOperator::CreateAdd(X, ConstantExpr::getSub(C, C2)); + + // C-(X+C2) --> (C-C2)-X if (match(Op1, m_Add(m_Value(X), m_Constant(C2)))) return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X); } @@ -1626,9 +1717,15 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) { Builder.CreateNot(Y, Y->getName() + ".not")); // 0 - (X sdiv C) -> (X sdiv -C) provided the negation doesn't overflow. - if (match(Op1, m_SDiv(m_Value(X), m_Constant(C))) && match(Op0, m_Zero()) && - C->isNotMinSignedValue() && !C->isOneValue()) - return BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(C)); + // TODO: This could be extended to match arbitrary vector constants. + const APInt *DivC; + if (match(Op0, m_Zero()) && match(Op1, m_SDiv(m_Value(X), m_APInt(DivC))) && + !DivC->isMinSignedValue() && *DivC != 1) { + Constant *NegDivC = ConstantInt::get(I.getType(), -(*DivC)); + Instruction *BO = BinaryOperator::CreateSDiv(X, NegDivC); + BO->setIsExact(cast<BinaryOperator>(Op1)->isExact()); + return BO; + } // 0 - (X << Y) -> (-X << Y) when X is freely negatable. if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero())) @@ -1745,6 +1842,49 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) { return Changed ? &I : nullptr; } +/// This eliminates floating-point negation in either 'fneg(X)' or +/// 'fsub(-0.0, X)' form by combining into a constant operand. +static Instruction *foldFNegIntoConstant(Instruction &I) { + Value *X; + Constant *C; + + // Fold negation into constant operand. This is limited with one-use because + // fneg is assumed better for analysis and cheaper in codegen than fmul/fdiv. + // -(X * C) --> X * (-C) + // FIXME: It's arguable whether these should be m_OneUse or not. The current + // belief is that the FNeg allows for better reassociation opportunities. + if (match(&I, m_FNeg(m_OneUse(m_FMul(m_Value(X), m_Constant(C)))))) + return BinaryOperator::CreateFMulFMF(X, ConstantExpr::getFNeg(C), &I); + // -(X / C) --> X / (-C) + if (match(&I, m_FNeg(m_OneUse(m_FDiv(m_Value(X), m_Constant(C)))))) + return BinaryOperator::CreateFDivFMF(X, ConstantExpr::getFNeg(C), &I); + // -(C / X) --> (-C) / X + if (match(&I, m_FNeg(m_OneUse(m_FDiv(m_Constant(C), m_Value(X)))))) + return BinaryOperator::CreateFDivFMF(ConstantExpr::getFNeg(C), X, &I); + + return nullptr; +} + +Instruction *InstCombiner::visitFNeg(UnaryOperator &I) { + Value *Op = I.getOperand(0); + + if (Value *V = SimplifyFNegInst(Op, I.getFastMathFlags(), + SQ.getWithInstruction(&I))) + return replaceInstUsesWith(I, V); + + if (Instruction *X = foldFNegIntoConstant(I)) + return X; + + Value *X, *Y; + + // If we can ignore the sign of zeros: -(X - Y) --> (Y - X) + if (I.hasNoSignedZeros() && + match(Op, m_OneUse(m_FSub(m_Value(X), m_Value(Y))))) + return BinaryOperator::CreateFSubFMF(Y, X, &I); + + return nullptr; +} + Instruction *InstCombiner::visitFSub(BinaryOperator &I) { if (Value *V = SimplifyFSubInst(I.getOperand(0), I.getOperand(1), I.getFastMathFlags(), @@ -1760,21 +1900,12 @@ Instruction *InstCombiner::visitFSub(BinaryOperator &I) { if (I.hasNoSignedZeros() && match(Op0, m_PosZeroFP())) return BinaryOperator::CreateFNegFMF(Op1, &I); + if (Instruction *X = foldFNegIntoConstant(I)) + return X; + Value *X, *Y; Constant *C; - // Fold negation into constant operand. This is limited with one-use because - // fneg is assumed better for analysis and cheaper in codegen than fmul/fdiv. - // -(X * C) --> X * (-C) - if (match(&I, m_FNeg(m_OneUse(m_FMul(m_Value(X), m_Constant(C)))))) - return BinaryOperator::CreateFMulFMF(X, ConstantExpr::getFNeg(C), &I); - // -(X / C) --> X / (-C) - if (match(&I, m_FNeg(m_OneUse(m_FDiv(m_Value(X), m_Constant(C)))))) - return BinaryOperator::CreateFDivFMF(X, ConstantExpr::getFNeg(C), &I); - // -(C / X) --> (-C) / X - if (match(&I, m_FNeg(m_OneUse(m_FDiv(m_Constant(C), m_Value(X)))))) - return BinaryOperator::CreateFDivFMF(ConstantExpr::getFNeg(C), X, &I); - // If Op0 is not -0.0 or we can ignore -0.0: Z - (X - Y) --> Z + (Y - X) // Canonicalize to fadd to make analysis easier. // This can also help codegen because fadd is commutative. |