diff options
Diffstat (limited to 'lib/Transforms/InstCombine')
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineAddSub.cpp | 193 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | 120 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineAtomicRMW.cpp | 159 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineCalls.cpp | 1150 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineCasts.cpp | 90 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineCompares.cpp | 643 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineInternal.h | 99 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp | 62 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineMulDivRem.cpp | 103 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombinePHI.cpp | 15 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineSelect.cpp | 288 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineShifts.cpp | 98 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp | 112 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineVectorOps.cpp | 321 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstructionCombining.cpp | 348 |
15 files changed, 2509 insertions, 1292 deletions
diff --git a/lib/Transforms/InstCombine/InstCombineAddSub.cpp b/lib/Transforms/InstCombine/InstCombineAddSub.cpp index 6e196bfdbd25e..ba15b023f2a32 100644 --- a/lib/Transforms/InstCombine/InstCombineAddSub.cpp +++ b/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. diff --git a/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp index 404c2ad7e6e70..2b9859b602f49 100644 --- a/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ b/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -1,9 +1,8 @@ //===- InstCombineAndOrXor.cpp --------------------------------------------===// // -// 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 // //===----------------------------------------------------------------------===// // @@ -968,7 +967,7 @@ static Value *foldSignedTruncationCheck(ICmpInst *ICmp0, ICmpInst *ICmp1, // Can it be decomposed into icmp eq (X & Mask), 0 ? if (llvm::decomposeBitTestICmp(ICmp->getOperand(0), ICmp->getOperand(1), Pred, X, UnsetBitsMask, - /*LookThruTrunc=*/false) && + /*LookThroughTrunc=*/false) && Pred == ICmpInst::ICMP_EQ) return true; // Is it icmp eq (X & Mask), 0 already? @@ -1022,6 +1021,36 @@ static Value *foldSignedTruncationCheck(ICmpInst *ICmp0, ICmpInst *ICmp1, CxtI.getName() + ".simplified"); } +/// Reduce a pair of compares that check if a value has exactly 1 bit set. +static Value *foldIsPowerOf2(ICmpInst *Cmp0, ICmpInst *Cmp1, bool JoinedByAnd, + InstCombiner::BuilderTy &Builder) { + // Handle 'and' / 'or' commutation: make the equality check the first operand. + if (JoinedByAnd && Cmp1->getPredicate() == ICmpInst::ICMP_NE) + std::swap(Cmp0, Cmp1); + else if (!JoinedByAnd && Cmp1->getPredicate() == ICmpInst::ICMP_EQ) + std::swap(Cmp0, Cmp1); + + // (X != 0) && (ctpop(X) u< 2) --> ctpop(X) == 1 + CmpInst::Predicate Pred0, Pred1; + Value *X; + if (JoinedByAnd && match(Cmp0, m_ICmp(Pred0, m_Value(X), m_ZeroInt())) && + match(Cmp1, m_ICmp(Pred1, m_Intrinsic<Intrinsic::ctpop>(m_Specific(X)), + m_SpecificInt(2))) && + Pred0 == ICmpInst::ICMP_NE && Pred1 == ICmpInst::ICMP_ULT) { + Value *CtPop = Cmp1->getOperand(0); + return Builder.CreateICmpEQ(CtPop, ConstantInt::get(CtPop->getType(), 1)); + } + // (X == 0) || (ctpop(X) u> 1) --> ctpop(X) != 1 + if (!JoinedByAnd && match(Cmp0, m_ICmp(Pred0, m_Value(X), m_ZeroInt())) && + match(Cmp1, m_ICmp(Pred1, m_Intrinsic<Intrinsic::ctpop>(m_Specific(X)), + m_SpecificInt(1))) && + Pred0 == ICmpInst::ICMP_EQ && Pred1 == ICmpInst::ICMP_UGT) { + Value *CtPop = Cmp1->getOperand(0); + return Builder.CreateICmpNE(CtPop, ConstantInt::get(CtPop->getType(), 1)); + } + return nullptr; +} + /// Fold (icmp)&(icmp) if possible. Value *InstCombiner::foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &CxtI) { @@ -1064,6 +1093,9 @@ Value *InstCombiner::foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, if (Value *V = foldSignedTruncationCheck(LHS, RHS, CxtI, Builder)) return V; + if (Value *V = foldIsPowerOf2(LHS, RHS, true /* JoinedByAnd */, Builder)) + return V; + // This only handles icmp of constants: (icmp1 A, C1) & (icmp2 B, C2). Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0); ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS->getOperand(1)); @@ -1259,6 +1291,52 @@ Value *InstCombiner::foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd) return nullptr; } +/// 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 +/// an unlikely pattern for a large number of logic ops and fcmps. +static Instruction *reassociateFCmps(BinaryOperator &BO, + InstCombiner::BuilderTy &Builder) { + Instruction::BinaryOps Opcode = BO.getOpcode(); + assert((Opcode == Instruction::And || Opcode == Instruction::Or) && + "Expecting and/or op for fcmp transform"); + + // There are 4 commuted variants of the pattern. Canonicalize operands of this + // logic op so an fcmp is operand 0 and a matching logic op is operand 1. + Value *Op0 = BO.getOperand(0), *Op1 = BO.getOperand(1), *X; + FCmpInst::Predicate Pred; + if (match(Op1, m_FCmp(Pred, m_Value(), m_AnyZeroFP()))) + std::swap(Op0, Op1); + + // Match inner binop and the predicate for combining 2 NAN checks into 1. + BinaryOperator *BO1; + FCmpInst::Predicate NanPred = Opcode == Instruction::And ? FCmpInst::FCMP_ORD + : FCmpInst::FCMP_UNO; + if (!match(Op0, m_FCmp(Pred, m_Value(X), m_AnyZeroFP())) || Pred != NanPred || + !match(Op1, m_BinOp(BO1)) || BO1->getOpcode() != Opcode) + return nullptr; + + // The inner logic op must have a matching fcmp operand. + Value *BO10 = BO1->getOperand(0), *BO11 = BO1->getOperand(1), *Y; + if (!match(BO10, m_FCmp(Pred, m_Value(Y), m_AnyZeroFP())) || + Pred != NanPred || X->getType() != Y->getType()) + std::swap(BO10, BO11); + + if (!match(BO10, m_FCmp(Pred, m_Value(Y), m_AnyZeroFP())) || + Pred != NanPred || X->getType() != Y->getType()) + return nullptr; + + // and (fcmp ord X, 0), (and (fcmp ord Y, 0), Z) --> and (fcmp ord X, Y), Z + // or (fcmp uno X, 0), (or (fcmp uno Y, 0), Z) --> or (fcmp uno X, Y), Z + Value *NewFCmp = Builder.CreateFCmp(Pred, X, Y); + if (auto *NewFCmpInst = dyn_cast<FCmpInst>(NewFCmp)) { + // Intersect FMF from the 2 source fcmps. + NewFCmpInst->copyIRFlags(Op0); + NewFCmpInst->andIRFlags(BO10); + } + return BinaryOperator::Create(Opcode, NewFCmp, BO11); +} + /// Match De Morgan's Laws: /// (~A & ~B) == (~(A | B)) /// (~A | ~B) == (~(A & B)) @@ -1619,6 +1697,7 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) { if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) { // ((C1 OP zext(X)) & C2) -> zext((C1-X) & C2) if C2 fits in the bitwidth // of X and OP behaves well when given trunc(C1) and X. + // TODO: Do this for vectors by using m_APInt isntead of m_ConstantInt. switch (Op0I->getOpcode()) { default: break; @@ -1629,7 +1708,10 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) { case Instruction::Sub: Value *X; ConstantInt *C1; - if (match(Op0I, m_c_BinOp(m_ZExt(m_Value(X)), m_ConstantInt(C1)))) { + // TODO: The one use restrictions could be relaxed a little if the AND + // is going to be removed. + if (match(Op0I, m_OneUse(m_c_BinOp(m_OneUse(m_ZExt(m_Value(X))), + m_ConstantInt(C1))))) { if (AndRHSMask.isIntN(X->getType()->getScalarSizeInBits())) { auto *TruncC1 = ConstantExpr::getTrunc(C1, X->getType()); Value *BinOp; @@ -1747,6 +1829,9 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) { if (Value *Res = foldLogicOfFCmps(LHS, RHS, true)) return replaceInstUsesWith(I, Res); + if (Instruction *FoldedFCmps = reassociateFCmps(I, Builder)) + return FoldedFCmps; + if (Instruction *CastedAnd = foldCastedBitwiseLogic(I)) return CastedAnd; @@ -1820,14 +1905,18 @@ static Instruction *matchRotate(Instruction &Or) { // First, find an or'd pair of opposite shifts with the same shifted operand: // or (lshr ShVal, ShAmt0), (shl ShVal, ShAmt1) - Value *Or0 = Or.getOperand(0), *Or1 = Or.getOperand(1); + BinaryOperator *Or0, *Or1; + if (!match(Or.getOperand(0), m_BinOp(Or0)) || + !match(Or.getOperand(1), m_BinOp(Or1))) + return nullptr; + Value *ShVal, *ShAmt0, *ShAmt1; if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(ShVal), m_Value(ShAmt0)))) || !match(Or1, m_OneUse(m_LogicalShift(m_Specific(ShVal), m_Value(ShAmt1))))) return nullptr; - auto ShiftOpcode0 = cast<BinaryOperator>(Or0)->getOpcode(); - auto ShiftOpcode1 = cast<BinaryOperator>(Or1)->getOpcode(); + BinaryOperator::BinaryOps ShiftOpcode0 = Or0->getOpcode(); + BinaryOperator::BinaryOps ShiftOpcode1 = Or1->getOpcode(); if (ShiftOpcode0 == ShiftOpcode1) return nullptr; @@ -1842,6 +1931,13 @@ static Instruction *matchRotate(Instruction &Or) { match(R, m_And(m_Neg(m_Specific(X)), m_SpecificInt(Mask)))) return X; + // Similar to above, but the shift amount may be extended after masking, + // so return the extended value as the parameter for the intrinsic. + if (match(L, m_ZExt(m_And(m_Value(X), m_SpecificInt(Mask)))) && + match(R, m_And(m_Neg(m_ZExt(m_And(m_Specific(X), m_SpecificInt(Mask)))), + m_SpecificInt(Mask)))) + return L; + return nullptr; }; @@ -2083,6 +2179,9 @@ Value *InstCombiner::foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, false, Builder)) return V; + if (Value *V = foldIsPowerOf2(LHS, RHS, false /* JoinedByAnd */, Builder)) + return V; + // This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2). if (!LHSC || !RHSC) return nullptr; @@ -2412,6 +2511,9 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { if (Value *Res = foldLogicOfFCmps(LHS, RHS, false)) return replaceInstUsesWith(I, Res); + if (Instruction *FoldedFCmps = reassociateFCmps(I, Builder)) + return FoldedFCmps; + if (Instruction *CastedOr = foldCastedBitwiseLogic(I)) return CastedOr; diff --git a/lib/Transforms/InstCombine/InstCombineAtomicRMW.cpp b/lib/Transforms/InstCombine/InstCombineAtomicRMW.cpp new file mode 100644 index 0000000000000..5f37a00f56cf5 --- /dev/null +++ b/lib/Transforms/InstCombine/InstCombineAtomicRMW.cpp @@ -0,0 +1,159 @@ +//===- InstCombineAtomicRMW.cpp -------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// This file implements the visit functions for atomic rmw instructions. +// +//===----------------------------------------------------------------------===// +#include "InstCombineInternal.h" +#include "llvm/IR/Instructions.h" + +using namespace llvm; + +namespace { +/// Return true if and only if the given instruction does not modify the memory +/// location referenced. Note that an idemptent atomicrmw may still have +/// ordering effects on nearby instructions, or be volatile. +/// TODO: Common w/ the version in AtomicExpandPass, and change the term used. +/// Idemptotent is confusing in this context. +bool isIdempotentRMW(AtomicRMWInst& RMWI) { + if (auto CF = dyn_cast<ConstantFP>(RMWI.getValOperand())) + switch(RMWI.getOperation()) { + case AtomicRMWInst::FAdd: // -0.0 + return CF->isZero() && CF->isNegative(); + case AtomicRMWInst::FSub: // +0.0 + return CF->isZero() && !CF->isNegative(); + default: + return false; + }; + + auto C = dyn_cast<ConstantInt>(RMWI.getValOperand()); + if(!C) + return false; + + switch(RMWI.getOperation()) { + case AtomicRMWInst::Add: + case AtomicRMWInst::Sub: + case AtomicRMWInst::Or: + case AtomicRMWInst::Xor: + return C->isZero(); + case AtomicRMWInst::And: + return C->isMinusOne(); + case AtomicRMWInst::Min: + return C->isMaxValue(true); + case AtomicRMWInst::Max: + return C->isMinValue(true); + case AtomicRMWInst::UMin: + return C->isMaxValue(false); + case AtomicRMWInst::UMax: + return C->isMinValue(false); + default: + return false; + } +} + +/// Return true if the given instruction always produces a value in memory +/// equivalent to its value operand. +bool isSaturating(AtomicRMWInst& RMWI) { + if (auto CF = dyn_cast<ConstantFP>(RMWI.getValOperand())) + switch(RMWI.getOperation()) { + case AtomicRMWInst::FAdd: + case AtomicRMWInst::FSub: + return CF->isNaN(); + default: + return false; + }; + + auto C = dyn_cast<ConstantInt>(RMWI.getValOperand()); + if(!C) + return false; + + switch(RMWI.getOperation()) { + default: + return false; + case AtomicRMWInst::Xchg: + return true; + case AtomicRMWInst::Or: + return C->isAllOnesValue(); + case AtomicRMWInst::And: + return C->isZero(); + case AtomicRMWInst::Min: + return C->isMinValue(true); + case AtomicRMWInst::Max: + return C->isMaxValue(true); + case AtomicRMWInst::UMin: + return C->isMinValue(false); + case AtomicRMWInst::UMax: + return C->isMaxValue(false); + }; +} +} + +Instruction *InstCombiner::visitAtomicRMWInst(AtomicRMWInst &RMWI) { + + // Volatile RMWs perform a load and a store, we cannot replace this by just a + // load or just a store. We chose not to canonicalize out of general paranoia + // about user expectations around volatile. + if (RMWI.isVolatile()) + return nullptr; + + // Any atomicrmw op which produces a known result in memory can be + // replaced w/an atomicrmw xchg. + if (isSaturating(RMWI) && + RMWI.getOperation() != AtomicRMWInst::Xchg) { + RMWI.setOperation(AtomicRMWInst::Xchg); + return &RMWI; + } + + AtomicOrdering Ordering = RMWI.getOrdering(); + assert(Ordering != AtomicOrdering::NotAtomic && + Ordering != AtomicOrdering::Unordered && + "AtomicRMWs don't make sense with Unordered or NotAtomic"); + + // Any atomicrmw xchg with no uses can be converted to a atomic store if the + // ordering is compatible. + if (RMWI.getOperation() == AtomicRMWInst::Xchg && + RMWI.use_empty()) { + if (Ordering != AtomicOrdering::Release && + Ordering != AtomicOrdering::Monotonic) + return nullptr; + auto *SI = new StoreInst(RMWI.getValOperand(), + RMWI.getPointerOperand(), &RMWI); + SI->setAtomic(Ordering, RMWI.getSyncScopeID()); + SI->setAlignment(DL.getABITypeAlignment(RMWI.getType())); + return eraseInstFromFunction(RMWI); + } + + if (!isIdempotentRMW(RMWI)) + return nullptr; + + // We chose to canonicalize all idempotent operations to an single + // operation code and constant. This makes it easier for the rest of the + // optimizer to match easily. The choices of or w/0 and fadd w/-0.0 are + // arbitrary. + if (RMWI.getType()->isIntegerTy() && + RMWI.getOperation() != AtomicRMWInst::Or) { + RMWI.setOperation(AtomicRMWInst::Or); + RMWI.setOperand(1, ConstantInt::get(RMWI.getType(), 0)); + return &RMWI; + } else if (RMWI.getType()->isFloatingPointTy() && + RMWI.getOperation() != AtomicRMWInst::FAdd) { + RMWI.setOperation(AtomicRMWInst::FAdd); + RMWI.setOperand(1, ConstantFP::getNegativeZero(RMWI.getType())); + return &RMWI; + } + + // Check if the required ordering is compatible with an atomic load. + if (Ordering != AtomicOrdering::Acquire && + Ordering != AtomicOrdering::Monotonic) + return nullptr; + + LoadInst *Load = new LoadInst(RMWI.getType(), RMWI.getPointerOperand()); + Load->setAtomic(Ordering, RMWI.getSyncScopeID()); + Load->setAlignment(DL.getABITypeAlignment(RMWI.getType())); + return Load; +} diff --git a/lib/Transforms/InstCombine/InstCombineCalls.cpp b/lib/Transforms/InstCombine/InstCombineCalls.cpp index aeb25d530d71b..4b3333affa724 100644 --- a/lib/Transforms/InstCombine/InstCombineCalls.cpp +++ b/lib/Transforms/InstCombine/InstCombineCalls.cpp @@ -1,19 +1,19 @@ //===- InstCombineCalls.cpp -----------------------------------------------===// // -// 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 // //===----------------------------------------------------------------------===// // -// This file implements the visitCall and visitInvoke functions. +// This file implements the visitCall, visitInvoke, and visitCallBr functions. // //===----------------------------------------------------------------------===// #include "InstCombineInternal.h" #include "llvm/ADT/APFloat.h" #include "llvm/ADT/APInt.h" +#include "llvm/ADT/APSInt.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/None.h" #include "llvm/ADT/Optional.h" @@ -23,12 +23,12 @@ #include "llvm/ADT/Twine.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/Loads.h" #include "llvm/Analysis/MemoryBuiltins.h" -#include "llvm/Transforms/Utils/Local.h" #include "llvm/Analysis/ValueTracking.h" +#include "llvm/Analysis/VectorUtils.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/BasicBlock.h" -#include "llvm/IR/CallSite.h" #include "llvm/IR/Constant.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" @@ -58,6 +58,7 @@ #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/InstCombine/InstCombineWorklist.h" +#include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/SimplifyLibCalls.h" #include <algorithm> #include <cassert> @@ -121,6 +122,15 @@ Instruction *InstCombiner::SimplifyAnyMemTransfer(AnyMemTransferInst *MI) { return MI; } + // If we have a store to a location which is known constant, we can conclude + // that the store must be storing the constant value (else the memory + // wouldn't be constant), and this must be a noop. + if (AA->pointsToConstantMemory(MI->getDest())) { + // Set the size of the copy to 0, it will be deleted on the next iteration. + MI->setLength(Constant::getNullValue(MI->getLength()->getType())); + return MI; + } + // If MemCpyInst length is 1/2/4/8 bytes then replace memcpy with // load/store. ConstantInt *MemOpLength = dyn_cast<ConstantInt>(MI->getLength()); @@ -173,7 +183,7 @@ Instruction *InstCombiner::SimplifyAnyMemTransfer(AnyMemTransferInst *MI) { Value *Src = Builder.CreateBitCast(MI->getArgOperand(1), NewSrcPtrTy); Value *Dest = Builder.CreateBitCast(MI->getArgOperand(0), NewDstPtrTy); - LoadInst *L = Builder.CreateLoad(Src); + LoadInst *L = Builder.CreateLoad(IntType, Src); // Alignment from the mem intrinsic will be better, so use it. L->setAlignment(CopySrcAlign); if (CopyMD) @@ -219,6 +229,15 @@ Instruction *InstCombiner::SimplifyAnyMemSet(AnyMemSetInst *MI) { return MI; } + // If we have a store to a location which is known constant, we can conclude + // that the store must be storing the constant value (else the memory + // wouldn't be constant), and this must be a noop. + if (AA->pointsToConstantMemory(MI->getDest())) { + // Set the size of the copy to 0, it will be deleted on the next iteration. + MI->setLength(Constant::getNullValue(MI->getLength()->getType())); + return MI; + } + // Extract the length and alignment and fill if they are constant. ConstantInt *LenC = dyn_cast<ConstantInt>(MI->getLength()); ConstantInt *FillC = dyn_cast<ConstantInt>(MI->getValue()); @@ -523,7 +542,8 @@ static Value *simplifyX86varShift(const IntrinsicInst &II, return Builder.CreateAShr(Vec, ShiftVec); } -static Value *simplifyX86pack(IntrinsicInst &II, bool IsSigned) { +static Value *simplifyX86pack(IntrinsicInst &II, + InstCombiner::BuilderTy &Builder, bool IsSigned) { Value *Arg0 = II.getArgOperand(0); Value *Arg1 = II.getArgOperand(1); Type *ResTy = II.getType(); @@ -534,167 +554,58 @@ static Value *simplifyX86pack(IntrinsicInst &II, bool IsSigned) { Type *ArgTy = Arg0->getType(); unsigned NumLanes = ResTy->getPrimitiveSizeInBits() / 128; - unsigned NumDstElts = ResTy->getVectorNumElements(); unsigned NumSrcElts = ArgTy->getVectorNumElements(); - assert(NumDstElts == (2 * NumSrcElts) && "Unexpected packing types"); + assert(ResTy->getVectorNumElements() == (2 * NumSrcElts) && + "Unexpected packing types"); - unsigned NumDstEltsPerLane = NumDstElts / NumLanes; unsigned NumSrcEltsPerLane = NumSrcElts / NumLanes; unsigned DstScalarSizeInBits = ResTy->getScalarSizeInBits(); - assert(ArgTy->getScalarSizeInBits() == (2 * DstScalarSizeInBits) && + unsigned SrcScalarSizeInBits = ArgTy->getScalarSizeInBits(); + assert(SrcScalarSizeInBits == (2 * DstScalarSizeInBits) && "Unexpected packing types"); // Constant folding. - auto *Cst0 = dyn_cast<Constant>(Arg0); - auto *Cst1 = dyn_cast<Constant>(Arg1); - if (!Cst0 || !Cst1) + if (!isa<Constant>(Arg0) || !isa<Constant>(Arg1)) return nullptr; - SmallVector<Constant *, 32> Vals; - for (unsigned Lane = 0; Lane != NumLanes; ++Lane) { - for (unsigned Elt = 0; Elt != NumDstEltsPerLane; ++Elt) { - unsigned SrcIdx = Lane * NumSrcEltsPerLane + Elt % NumSrcEltsPerLane; - auto *Cst = (Elt >= NumSrcEltsPerLane) ? Cst1 : Cst0; - auto *COp = Cst->getAggregateElement(SrcIdx); - if (COp && isa<UndefValue>(COp)) { - Vals.push_back(UndefValue::get(ResTy->getScalarType())); - continue; - } - - auto *CInt = dyn_cast_or_null<ConstantInt>(COp); - if (!CInt) - return nullptr; - - APInt Val = CInt->getValue(); - assert(Val.getBitWidth() == ArgTy->getScalarSizeInBits() && - "Unexpected constant bitwidth"); - - if (IsSigned) { - // PACKSS: Truncate signed value with signed saturation. - // Source values less than dst minint are saturated to minint. - // Source values greater than dst maxint are saturated to maxint. - if (Val.isSignedIntN(DstScalarSizeInBits)) - Val = Val.trunc(DstScalarSizeInBits); - else if (Val.isNegative()) - Val = APInt::getSignedMinValue(DstScalarSizeInBits); - else - Val = APInt::getSignedMaxValue(DstScalarSizeInBits); - } else { - // PACKUS: Truncate signed value with unsigned saturation. - // Source values less than zero are saturated to zero. - // Source values greater than dst maxuint are saturated to maxuint. - if (Val.isIntN(DstScalarSizeInBits)) - Val = Val.trunc(DstScalarSizeInBits); - else if (Val.isNegative()) - Val = APInt::getNullValue(DstScalarSizeInBits); - else - Val = APInt::getAllOnesValue(DstScalarSizeInBits); - } - - Vals.push_back(ConstantInt::get(ResTy->getScalarType(), Val)); - } - } - - return ConstantVector::get(Vals); -} - -// Replace X86-specific intrinsics with generic floor-ceil where applicable. -static Value *simplifyX86round(IntrinsicInst &II, - InstCombiner::BuilderTy &Builder) { - ConstantInt *Arg = nullptr; - Intrinsic::ID IntrinsicID = II.getIntrinsicID(); - - if (IntrinsicID == Intrinsic::x86_sse41_round_ss || - IntrinsicID == Intrinsic::x86_sse41_round_sd) - Arg = dyn_cast<ConstantInt>(II.getArgOperand(2)); - else if (IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_ss || - IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_sd) - Arg = dyn_cast<ConstantInt>(II.getArgOperand(4)); - else - Arg = dyn_cast<ConstantInt>(II.getArgOperand(1)); - if (!Arg) - return nullptr; - unsigned RoundControl = Arg->getZExtValue(); - - Arg = nullptr; - unsigned SAE = 0; - if (IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_ps_512 || - IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_pd_512) - Arg = dyn_cast<ConstantInt>(II.getArgOperand(4)); - else if (IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_ss || - IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_sd) - Arg = dyn_cast<ConstantInt>(II.getArgOperand(5)); - else - SAE = 4; - if (!SAE) { - if (!Arg) - return nullptr; - SAE = Arg->getZExtValue(); + // Clamp Values - signed/unsigned both use signed clamp values, but they + // differ on the min/max values. + APInt MinValue, MaxValue; + if (IsSigned) { + // PACKSS: Truncate signed value with signed saturation. + // Source values less than dst minint are saturated to minint. + // Source values greater than dst maxint are saturated to maxint. + MinValue = + APInt::getSignedMinValue(DstScalarSizeInBits).sext(SrcScalarSizeInBits); + MaxValue = + APInt::getSignedMaxValue(DstScalarSizeInBits).sext(SrcScalarSizeInBits); + } else { + // PACKUS: Truncate signed value with unsigned saturation. + // Source values less than zero are saturated to zero. + // Source values greater than dst maxuint are saturated to maxuint. + MinValue = APInt::getNullValue(SrcScalarSizeInBits); + MaxValue = APInt::getLowBitsSet(SrcScalarSizeInBits, DstScalarSizeInBits); } - if (SAE != 4 || (RoundControl != 2 /*ceil*/ && RoundControl != 1 /*floor*/)) - return nullptr; + auto *MinC = Constant::getIntegerValue(ArgTy, MinValue); + auto *MaxC = Constant::getIntegerValue(ArgTy, MaxValue); + Arg0 = Builder.CreateSelect(Builder.CreateICmpSLT(Arg0, MinC), MinC, Arg0); + Arg1 = Builder.CreateSelect(Builder.CreateICmpSLT(Arg1, MinC), MinC, Arg1); + Arg0 = Builder.CreateSelect(Builder.CreateICmpSGT(Arg0, MaxC), MaxC, Arg0); + Arg1 = Builder.CreateSelect(Builder.CreateICmpSGT(Arg1, MaxC), MaxC, Arg1); - Value *Src, *Dst, *Mask; - bool IsScalar = false; - if (IntrinsicID == Intrinsic::x86_sse41_round_ss || - IntrinsicID == Intrinsic::x86_sse41_round_sd || - IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_ss || - IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_sd) { - IsScalar = true; - if (IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_ss || - IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_sd) { - Mask = II.getArgOperand(3); - Value *Zero = Constant::getNullValue(Mask->getType()); - Mask = Builder.CreateAnd(Mask, 1); - Mask = Builder.CreateICmp(ICmpInst::ICMP_NE, Mask, Zero); - Dst = II.getArgOperand(2); - } else - Dst = II.getArgOperand(0); - Src = Builder.CreateExtractElement(II.getArgOperand(1), (uint64_t)0); - } else { - Src = II.getArgOperand(0); - if (IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_ps_128 || - IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_ps_256 || - IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_ps_512 || - IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_pd_128 || - IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_pd_256 || - IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_pd_512) { - Dst = II.getArgOperand(2); - Mask = II.getArgOperand(3); - } else { - Dst = Src; - Mask = ConstantInt::getAllOnesValue( - Builder.getIntNTy(Src->getType()->getVectorNumElements())); - } + // Shuffle clamped args together at the lane level. + SmallVector<unsigned, 32> PackMask; + for (unsigned Lane = 0; Lane != NumLanes; ++Lane) { + for (unsigned Elt = 0; Elt != NumSrcEltsPerLane; ++Elt) + PackMask.push_back(Elt + (Lane * NumSrcEltsPerLane)); + for (unsigned Elt = 0; Elt != NumSrcEltsPerLane; ++Elt) + PackMask.push_back(Elt + (Lane * NumSrcEltsPerLane) + NumSrcElts); } + auto *Shuffle = Builder.CreateShuffleVector(Arg0, Arg1, PackMask); - Intrinsic::ID ID = (RoundControl == 2) ? Intrinsic::ceil : Intrinsic::floor; - Value *Res = Builder.CreateUnaryIntrinsic(ID, Src, &II); - if (!IsScalar) { - if (auto *C = dyn_cast<Constant>(Mask)) - if (C->isAllOnesValue()) - return Res; - auto *MaskTy = VectorType::get( - Builder.getInt1Ty(), cast<IntegerType>(Mask->getType())->getBitWidth()); - Mask = Builder.CreateBitCast(Mask, MaskTy); - unsigned Width = Src->getType()->getVectorNumElements(); - if (MaskTy->getVectorNumElements() > Width) { - uint32_t Indices[4]; - for (unsigned i = 0; i != Width; ++i) - Indices[i] = i; - Mask = Builder.CreateShuffleVector(Mask, Mask, - makeArrayRef(Indices, Width)); - } - return Builder.CreateSelect(Mask, Res, Dst); - } - if (IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_ss || - IntrinsicID == Intrinsic::x86_avx512_mask_rndscale_sd) { - Dst = Builder.CreateExtractElement(Dst, (uint64_t)0); - Res = Builder.CreateSelect(Mask, Res, Dst); - Dst = II.getArgOperand(0); - } - return Builder.CreateInsertElement(Dst, Res, (uint64_t)0); + // Truncate to dst size. + return Builder.CreateTrunc(Shuffle, ResTy); } static Value *simplifyX86movmsk(const IntrinsicInst &II, @@ -711,43 +622,44 @@ static Value *simplifyX86movmsk(const IntrinsicInst &II, if (!ArgTy->isVectorTy()) return nullptr; - if (auto *C = dyn_cast<Constant>(Arg)) { - // Extract signbits of the vector input and pack into integer result. - APInt Result(ResTy->getPrimitiveSizeInBits(), 0); - for (unsigned I = 0, E = ArgTy->getVectorNumElements(); I != E; ++I) { - auto *COp = C->getAggregateElement(I); - if (!COp) - return nullptr; - if (isa<UndefValue>(COp)) - continue; + // Expand MOVMSK to compare/bitcast/zext: + // e.g. PMOVMSKB(v16i8 x): + // %cmp = icmp slt <16 x i8> %x, zeroinitializer + // %int = bitcast <16 x i1> %cmp to i16 + // %res = zext i16 %int to i32 + unsigned NumElts = ArgTy->getVectorNumElements(); + Type *IntegerVecTy = VectorType::getInteger(cast<VectorType>(ArgTy)); + Type *IntegerTy = Builder.getIntNTy(NumElts); - auto *CInt = dyn_cast<ConstantInt>(COp); - auto *CFp = dyn_cast<ConstantFP>(COp); - if (!CInt && !CFp) - return nullptr; + Value *Res = Builder.CreateBitCast(Arg, IntegerVecTy); + Res = Builder.CreateICmpSLT(Res, Constant::getNullValue(IntegerVecTy)); + Res = Builder.CreateBitCast(Res, IntegerTy); + Res = Builder.CreateZExtOrTrunc(Res, ResTy); + return Res; +} - if ((CInt && CInt->isNegative()) || (CFp && CFp->isNegative())) - Result.setBit(I); - } - return Constant::getIntegerValue(ResTy, Result); - } +static Value *simplifyX86addcarry(const IntrinsicInst &II, + InstCombiner::BuilderTy &Builder) { + Value *CarryIn = II.getArgOperand(0); + Value *Op1 = II.getArgOperand(1); + Value *Op2 = II.getArgOperand(2); + Type *RetTy = II.getType(); + Type *OpTy = Op1->getType(); + assert(RetTy->getStructElementType(0)->isIntegerTy(8) && + RetTy->getStructElementType(1) == OpTy && OpTy == Op2->getType() && + "Unexpected types for x86 addcarry"); - // Look for a sign-extended boolean source vector as the argument to this - // movmsk. If the argument is bitcast, look through that, but make sure the - // source of that bitcast is still a vector with the same number of elements. - // TODO: We can also convert a bitcast with wider elements, but that requires - // duplicating the bool source sign bits to match the number of elements - // expected by the movmsk call. - Arg = peekThroughBitcast(Arg); - Value *X; - if (Arg->getType()->isVectorTy() && - Arg->getType()->getVectorNumElements() == ArgTy->getVectorNumElements() && - match(Arg, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) { - // call iM movmsk(sext <N x i1> X) --> zext (bitcast <N x i1> X to iN) to iM - unsigned NumElts = X->getType()->getVectorNumElements(); - Type *ScalarTy = Type::getIntNTy(Arg->getContext(), NumElts); - Value *BC = Builder.CreateBitCast(X, ScalarTy); - return Builder.CreateZExtOrTrunc(BC, ResTy); + // If carry-in is zero, this is just an unsigned add with overflow. + if (match(CarryIn, m_ZeroInt())) { + Value *UAdd = Builder.CreateIntrinsic(Intrinsic::uadd_with_overflow, OpTy, + { Op1, Op2 }); + // The types have to be adjusted to match the x86 call types. + Value *UAddResult = Builder.CreateExtractValue(UAdd, 0); + Value *UAddOV = Builder.CreateZExt(Builder.CreateExtractValue(UAdd, 1), + Builder.getInt8Ty()); + Value *Res = UndefValue::get(RetTy); + Res = Builder.CreateInsertValue(Res, UAddOV, 0); + return Builder.CreateInsertValue(Res, UAddResult, 1); } return nullptr; @@ -892,7 +804,7 @@ static Value *simplifyX86extrq(IntrinsicInst &II, Value *Op0, if (II.getIntrinsicID() == Intrinsic::x86_sse4a_extrq) { Value *Args[] = {Op0, CILength, CIIndex}; Module *M = II.getModule(); - Value *F = Intrinsic::getDeclaration(M, Intrinsic::x86_sse4a_extrqi); + Function *F = Intrinsic::getDeclaration(M, Intrinsic::x86_sse4a_extrqi); return Builder.CreateCall(F, Args); } } @@ -993,7 +905,7 @@ static Value *simplifyX86insertq(IntrinsicInst &II, Value *Op0, Value *Op1, Value *Args[] = {Op0, Op1, CILength, CIIndex}; Module *M = II.getModule(); - Value *F = Intrinsic::getDeclaration(M, Intrinsic::x86_sse4a_insertqi); + Function *F = Intrinsic::getDeclaration(M, Intrinsic::x86_sse4a_insertqi); return Builder.CreateCall(F, Args); } @@ -1134,82 +1046,42 @@ static Value *simplifyX86vpermv(const IntrinsicInst &II, return Builder.CreateShuffleVector(V1, V2, ShuffleMask); } -/// Decode XOP integer vector comparison intrinsics. -static Value *simplifyX86vpcom(const IntrinsicInst &II, - InstCombiner::BuilderTy &Builder, - bool IsSigned) { - if (auto *CInt = dyn_cast<ConstantInt>(II.getArgOperand(2))) { - uint64_t Imm = CInt->getZExtValue() & 0x7; - VectorType *VecTy = cast<VectorType>(II.getType()); - CmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE; - - switch (Imm) { - case 0x0: - Pred = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; - break; - case 0x1: - Pred = IsSigned ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; - break; - case 0x2: - Pred = IsSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; - break; - case 0x3: - Pred = IsSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE; - break; - case 0x4: - Pred = ICmpInst::ICMP_EQ; break; - case 0x5: - Pred = ICmpInst::ICMP_NE; break; - case 0x6: - return ConstantInt::getSigned(VecTy, 0); // FALSE - case 0x7: - return ConstantInt::getSigned(VecTy, -1); // TRUE - } - - if (Value *Cmp = Builder.CreateICmp(Pred, II.getArgOperand(0), - II.getArgOperand(1))) - return Builder.CreateSExtOrTrunc(Cmp, VecTy); - } - return nullptr; -} - -static bool maskIsAllOneOrUndef(Value *Mask) { - auto *ConstMask = dyn_cast<Constant>(Mask); - if (!ConstMask) - return false; - if (ConstMask->isAllOnesValue() || isa<UndefValue>(ConstMask)) - return true; - for (unsigned I = 0, E = ConstMask->getType()->getVectorNumElements(); I != E; - ++I) { - if (auto *MaskElt = ConstMask->getAggregateElement(I)) - if (MaskElt->isAllOnesValue() || isa<UndefValue>(MaskElt)) - continue; - return false; - } - return true; -} +// TODO, Obvious Missing Transforms: +// * Narrow width by halfs excluding zero/undef lanes +Value *InstCombiner::simplifyMaskedLoad(IntrinsicInst &II) { + Value *LoadPtr = II.getArgOperand(0); + unsigned Alignment = cast<ConstantInt>(II.getArgOperand(1))->getZExtValue(); -static Value *simplifyMaskedLoad(const IntrinsicInst &II, - InstCombiner::BuilderTy &Builder) { // If the mask is all ones or undefs, this is a plain vector load of the 1st // argument. - if (maskIsAllOneOrUndef(II.getArgOperand(2))) { - Value *LoadPtr = II.getArgOperand(0); - unsigned Alignment = cast<ConstantInt>(II.getArgOperand(1))->getZExtValue(); - return Builder.CreateAlignedLoad(LoadPtr, Alignment, "unmaskedload"); + if (maskIsAllOneOrUndef(II.getArgOperand(2))) + return Builder.CreateAlignedLoad(II.getType(), LoadPtr, Alignment, + "unmaskedload"); + + // If we can unconditionally load from this address, replace with a + // load/select idiom. TODO: use DT for context sensitive query + if (isDereferenceableAndAlignedPointer(LoadPtr, II.getType(), Alignment, + II.getModule()->getDataLayout(), + &II, nullptr)) { + Value *LI = Builder.CreateAlignedLoad(II.getType(), LoadPtr, Alignment, + "unmaskedload"); + return Builder.CreateSelect(II.getArgOperand(2), LI, II.getArgOperand(3)); } return nullptr; } -static Instruction *simplifyMaskedStore(IntrinsicInst &II, InstCombiner &IC) { +// TODO, Obvious Missing Transforms: +// * Single constant active lane -> store +// * Narrow width by halfs excluding zero/undef lanes +Instruction *InstCombiner::simplifyMaskedStore(IntrinsicInst &II) { auto *ConstMask = dyn_cast<Constant>(II.getArgOperand(3)); if (!ConstMask) return nullptr; // If the mask is all zeros, this instruction does nothing. if (ConstMask->isNullValue()) - return IC.eraseInstFromFunction(II); + return eraseInstFromFunction(II); // If the mask is all ones, this is a plain vector store of the 1st argument. if (ConstMask->isAllOnesValue()) { @@ -1218,14 +1090,57 @@ static Instruction *simplifyMaskedStore(IntrinsicInst &II, InstCombiner &IC) { return new StoreInst(II.getArgOperand(0), StorePtr, false, Alignment); } + // Use masked off lanes to simplify operands via SimplifyDemandedVectorElts + APInt DemandedElts = possiblyDemandedEltsInMask(ConstMask); + APInt UndefElts(DemandedElts.getBitWidth(), 0); + if (Value *V = SimplifyDemandedVectorElts(II.getOperand(0), + DemandedElts, UndefElts)) { + II.setOperand(0, V); + return &II; + } + return nullptr; } -static Instruction *simplifyMaskedGather(IntrinsicInst &II, InstCombiner &IC) { - // If the mask is all zeros, return the "passthru" argument of the gather. - auto *ConstMask = dyn_cast<Constant>(II.getArgOperand(2)); - if (ConstMask && ConstMask->isNullValue()) - return IC.replaceInstUsesWith(II, II.getArgOperand(3)); +// TODO, Obvious Missing Transforms: +// * Single constant active lane load -> load +// * Dereferenceable address & few lanes -> scalarize speculative load/selects +// * Adjacent vector addresses -> masked.load +// * Narrow width by halfs excluding zero/undef lanes +// * Vector splat address w/known mask -> scalar load +// * Vector incrementing address -> vector masked load +Instruction *InstCombiner::simplifyMaskedGather(IntrinsicInst &II) { + return nullptr; +} + +// TODO, Obvious Missing Transforms: +// * Single constant active lane -> store +// * Adjacent vector addresses -> masked.store +// * Narrow store width by halfs excluding zero/undef lanes +// * Vector splat address w/known mask -> scalar store +// * Vector incrementing address -> vector masked store +Instruction *InstCombiner::simplifyMaskedScatter(IntrinsicInst &II) { + auto *ConstMask = dyn_cast<Constant>(II.getArgOperand(3)); + if (!ConstMask) + return nullptr; + + // If the mask is all zeros, a scatter does nothing. + if (ConstMask->isNullValue()) + return eraseInstFromFunction(II); + + // Use masked off lanes to simplify operands via SimplifyDemandedVectorElts + APInt DemandedElts = possiblyDemandedEltsInMask(ConstMask); + APInt UndefElts(DemandedElts.getBitWidth(), 0); + if (Value *V = SimplifyDemandedVectorElts(II.getOperand(0), + DemandedElts, UndefElts)) { + II.setOperand(0, V); + return &II; + } + if (Value *V = SimplifyDemandedVectorElts(II.getOperand(1), + DemandedElts, UndefElts)) { + II.setOperand(1, V); + return &II; + } return nullptr; } @@ -1264,25 +1179,41 @@ static Instruction *simplifyInvariantGroupIntrinsic(IntrinsicInst &II, return cast<Instruction>(Result); } -static Instruction *simplifyMaskedScatter(IntrinsicInst &II, InstCombiner &IC) { - // If the mask is all zeros, a scatter does nothing. - auto *ConstMask = dyn_cast<Constant>(II.getArgOperand(3)); - if (ConstMask && ConstMask->isNullValue()) - return IC.eraseInstFromFunction(II); - - return nullptr; -} - static Instruction *foldCttzCtlz(IntrinsicInst &II, InstCombiner &IC) { assert((II.getIntrinsicID() == Intrinsic::cttz || II.getIntrinsicID() == Intrinsic::ctlz) && "Expected cttz or ctlz intrinsic"); + bool IsTZ = II.getIntrinsicID() == Intrinsic::cttz; Value *Op0 = II.getArgOperand(0); + Value *X; + // ctlz(bitreverse(x)) -> cttz(x) + // cttz(bitreverse(x)) -> ctlz(x) + if (match(Op0, m_BitReverse(m_Value(X)))) { + Intrinsic::ID ID = IsTZ ? Intrinsic::ctlz : Intrinsic::cttz; + Function *F = Intrinsic::getDeclaration(II.getModule(), ID, II.getType()); + return CallInst::Create(F, {X, II.getArgOperand(1)}); + } + + if (IsTZ) { + // cttz(-x) -> cttz(x) + if (match(Op0, m_Neg(m_Value(X)))) { + II.setOperand(0, X); + return &II; + } + + // cttz(abs(x)) -> cttz(x) + // cttz(nabs(x)) -> cttz(x) + Value *Y; + SelectPatternFlavor SPF = matchSelectPattern(Op0, X, Y).Flavor; + if (SPF == SPF_ABS || SPF == SPF_NABS) { + II.setOperand(0, X); + return &II; + } + } KnownBits Known = IC.computeKnownBits(Op0, 0, &II); // Create a mask for bits above (ctlz) or below (cttz) the first known one. - bool IsTZ = II.getIntrinsicID() == Intrinsic::cttz; unsigned PossibleZeros = IsTZ ? Known.countMaxTrailingZeros() : Known.countMaxLeadingZeros(); unsigned DefiniteZeros = IsTZ ? Known.countMinTrailingZeros() @@ -1328,6 +1259,14 @@ static Instruction *foldCtpop(IntrinsicInst &II, InstCombiner &IC) { assert(II.getIntrinsicID() == Intrinsic::ctpop && "Expected ctpop intrinsic"); Value *Op0 = II.getArgOperand(0); + Value *X; + // ctpop(bitreverse(x)) -> ctpop(x) + // ctpop(bswap(x)) -> ctpop(x) + if (match(Op0, m_BitReverse(m_Value(X))) || match(Op0, m_BSwap(m_Value(X)))) { + II.setOperand(0, X); + return &II; + } + // FIXME: Try to simplify vectors of integers. auto *IT = dyn_cast<IntegerType>(Op0->getType()); if (!IT) @@ -1513,7 +1452,7 @@ static Value *simplifyNeonVld1(const IntrinsicInst &II, auto *BCastInst = Builder.CreateBitCast(II.getArgOperand(0), PointerType::get(II.getType(), 0)); - return Builder.CreateAlignedLoad(BCastInst, Alignment); + return Builder.CreateAlignedLoad(II.getType(), BCastInst, Alignment); } // Returns true iff the 2 intrinsics have the same operands, limiting the @@ -1827,8 +1766,18 @@ static Instruction *canonicalizeConstantArg0ToArg1(CallInst &Call) { return nullptr; } +Instruction *InstCombiner::foldIntrinsicWithOverflowCommon(IntrinsicInst *II) { + WithOverflowInst *WO = cast<WithOverflowInst>(II); + Value *OperationResult = nullptr; + Constant *OverflowResult = nullptr; + if (OptimizeOverflowCheck(WO->getBinaryOp(), WO->isSigned(), WO->getLHS(), + WO->getRHS(), *WO, OperationResult, OverflowResult)) + return CreateOverflowTuple(WO, OperationResult, OverflowResult); + return nullptr; +} + /// CallInst simplification. This mostly only handles folding of intrinsic -/// instructions. For normal calls, it allows visitCallSite to do the heavy +/// instructions. For normal calls, it allows visitCallBase to do the heavy /// lifting. Instruction *InstCombiner::visitCallInst(CallInst &CI) { if (Value *V = SimplifyCall(&CI, SQ.getWithInstruction(&CI))) @@ -1845,10 +1794,10 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { } IntrinsicInst *II = dyn_cast<IntrinsicInst>(&CI); - if (!II) return visitCallSite(&CI); + if (!II) return visitCallBase(CI); - // Intrinsics cannot occur in an invoke, so handle them here instead of in - // visitCallSite. + // Intrinsics cannot occur in an invoke or a callbr, so handle them here + // instead of in visitCallBase. if (auto *MI = dyn_cast<AnyMemIntrinsic>(II)) { bool Changed = false; @@ -1908,6 +1857,18 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { if (Changed) return II; } + // For vector result intrinsics, use the generic demanded vector support. + if (II->getType()->isVectorTy()) { + auto VWidth = II->getType()->getVectorNumElements(); + APInt UndefElts(VWidth, 0); + APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth)); + if (Value *V = SimplifyDemandedVectorElts(II, AllOnesEltMask, UndefElts)) { + if (V != II) + return replaceInstUsesWith(*II, V); + return II; + } + } + if (Instruction *I = SimplifyNVVMIntrinsic(II, *this)) return I; @@ -1918,12 +1879,12 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { return SimplifyDemandedVectorElts(Op, DemandedElts, UndefElts); }; - switch (II->getIntrinsicID()) { + Intrinsic::ID IID = II->getIntrinsicID(); + switch (IID) { default: break; case Intrinsic::objectsize: - if (ConstantInt *N = - lowerObjectSizeCall(II, DL, &TLI, /*MustSucceed=*/false)) - return replaceInstUsesWith(CI, N); + if (Value *V = lowerObjectSizeCall(II, DL, &TLI, /*MustSucceed=*/false)) + return replaceInstUsesWith(CI, V); return nullptr; case Intrinsic::bswap: { Value *IIOperand = II->getArgOperand(0); @@ -1940,15 +1901,15 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { break; } case Intrinsic::masked_load: - if (Value *SimplifiedMaskedOp = simplifyMaskedLoad(*II, Builder)) + if (Value *SimplifiedMaskedOp = simplifyMaskedLoad(*II)) return replaceInstUsesWith(CI, SimplifiedMaskedOp); break; case Intrinsic::masked_store: - return simplifyMaskedStore(*II, *this); + return simplifyMaskedStore(*II); case Intrinsic::masked_gather: - return simplifyMaskedGather(*II, *this); + return simplifyMaskedGather(*II); case Intrinsic::masked_scatter: - return simplifyMaskedScatter(*II, *this); + return simplifyMaskedScatter(*II); case Intrinsic::launder_invariant_group: case Intrinsic::strip_invariant_group: if (auto *SkippedBarrier = simplifyInvariantGroupIntrinsic(*II, *this)) @@ -1982,33 +1943,62 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { case Intrinsic::fshl: case Intrinsic::fshr: { - const APInt *SA; - if (match(II->getArgOperand(2), m_APInt(SA))) { - Value *Op0 = II->getArgOperand(0), *Op1 = II->getArgOperand(1); - unsigned BitWidth = SA->getBitWidth(); - uint64_t ShiftAmt = SA->urem(BitWidth); - assert(ShiftAmt != 0 && "SimplifyCall should have handled zero shift"); - // Normalize to funnel shift left. - if (II->getIntrinsicID() == Intrinsic::fshr) - ShiftAmt = BitWidth - ShiftAmt; + Value *Op0 = II->getArgOperand(0), *Op1 = II->getArgOperand(1); + Type *Ty = II->getType(); + unsigned BitWidth = Ty->getScalarSizeInBits(); + Constant *ShAmtC; + if (match(II->getArgOperand(2), m_Constant(ShAmtC)) && + !isa<ConstantExpr>(ShAmtC) && !ShAmtC->containsConstantExpression()) { + // Canonicalize a shift amount constant operand to modulo the bit-width. + Constant *WidthC = ConstantInt::get(Ty, BitWidth); + Constant *ModuloC = ConstantExpr::getURem(ShAmtC, WidthC); + if (ModuloC != ShAmtC) { + II->setArgOperand(2, ModuloC); + return II; + } + assert(ConstantExpr::getICmp(ICmpInst::ICMP_UGT, WidthC, ShAmtC) == + ConstantInt::getTrue(CmpInst::makeCmpResultType(Ty)) && + "Shift amount expected to be modulo bitwidth"); + + // Canonicalize funnel shift right by constant to funnel shift left. This + // is not entirely arbitrary. For historical reasons, the backend may + // recognize rotate left patterns but miss rotate right patterns. + if (IID == Intrinsic::fshr) { + // fshr X, Y, C --> fshl X, Y, (BitWidth - C) + Constant *LeftShiftC = ConstantExpr::getSub(WidthC, ShAmtC); + Module *Mod = II->getModule(); + Function *Fshl = Intrinsic::getDeclaration(Mod, Intrinsic::fshl, Ty); + return CallInst::Create(Fshl, { Op0, Op1, LeftShiftC }); + } + assert(IID == Intrinsic::fshl && + "All funnel shifts by simple constants should go left"); + + // fshl(X, 0, C) --> shl X, C + // fshl(X, undef, C) --> shl X, C + if (match(Op1, m_ZeroInt()) || match(Op1, m_Undef())) + return BinaryOperator::CreateShl(Op0, ShAmtC); - // fshl(X, 0, C) -> shl X, C - // fshl(X, undef, C) -> shl X, C - if (match(Op1, m_Zero()) || match(Op1, m_Undef())) - return BinaryOperator::CreateShl( - Op0, ConstantInt::get(II->getType(), ShiftAmt)); + // fshl(0, X, C) --> lshr X, (BW-C) + // fshl(undef, X, C) --> lshr X, (BW-C) + if (match(Op0, m_ZeroInt()) || match(Op0, m_Undef())) + return BinaryOperator::CreateLShr(Op1, + ConstantExpr::getSub(WidthC, ShAmtC)); - // fshl(0, X, C) -> lshr X, (BW-C) - // fshl(undef, X, C) -> lshr X, (BW-C) - if (match(Op0, m_Zero()) || match(Op0, m_Undef())) - return BinaryOperator::CreateLShr( - Op1, ConstantInt::get(II->getType(), BitWidth - ShiftAmt)); + // fshl i16 X, X, 8 --> bswap i16 X (reduce to more-specific form) + if (Op0 == Op1 && BitWidth == 16 && match(ShAmtC, m_SpecificInt(8))) { + Module *Mod = II->getModule(); + Function *Bswap = Intrinsic::getDeclaration(Mod, Intrinsic::bswap, Ty); + return CallInst::Create(Bswap, { Op0 }); + } } + // Left or right might be masked. + if (SimplifyDemandedInstructionBits(*II)) + return &CI; + // The shift amount (operand 2) of a funnel shift is modulo the bitwidth, // so only the low bits of the shift amount are demanded if the bitwidth is // a power-of-2. - unsigned BitWidth = II->getType()->getScalarSizeInBits(); if (!isPowerOf2_32(BitWidth)) break; APInt Op2Demanded = APInt::getLowBitsSet(BitWidth, Log2_32_Ceil(BitWidth)); @@ -2018,7 +2008,34 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { break; } case Intrinsic::uadd_with_overflow: - case Intrinsic::sadd_with_overflow: + case Intrinsic::sadd_with_overflow: { + if (Instruction *I = canonicalizeConstantArg0ToArg1(CI)) + return I; + if (Instruction *I = foldIntrinsicWithOverflowCommon(II)) + return I; + + // Given 2 constant operands whose sum does not overflow: + // uaddo (X +nuw C0), C1 -> uaddo X, C0 + C1 + // saddo (X +nsw C0), C1 -> saddo X, C0 + C1 + Value *X; + const APInt *C0, *C1; + Value *Arg0 = II->getArgOperand(0); + Value *Arg1 = II->getArgOperand(1); + bool IsSigned = IID == Intrinsic::sadd_with_overflow; + bool HasNWAdd = IsSigned ? match(Arg0, m_NSWAdd(m_Value(X), m_APInt(C0))) + : match(Arg0, m_NUWAdd(m_Value(X), m_APInt(C0))); + if (HasNWAdd && match(Arg1, m_APInt(C1))) { + bool Overflow; + APInt NewC = + IsSigned ? C1->sadd_ov(*C0, Overflow) : C1->uadd_ov(*C0, Overflow); + if (!Overflow) + return replaceInstUsesWith( + *II, Builder.CreateBinaryIntrinsic( + IID, X, ConstantInt::get(Arg1->getType(), NewC))); + } + break; + } + case Intrinsic::umul_with_overflow: case Intrinsic::smul_with_overflow: if (Instruction *I = canonicalizeConstantArg0ToArg1(CI)) @@ -2026,16 +2043,29 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { LLVM_FALLTHROUGH; case Intrinsic::usub_with_overflow: + if (Instruction *I = foldIntrinsicWithOverflowCommon(II)) + return I; + break; + case Intrinsic::ssub_with_overflow: { - OverflowCheckFlavor OCF = - IntrinsicIDToOverflowCheckFlavor(II->getIntrinsicID()); - assert(OCF != OCF_INVALID && "unexpected!"); + if (Instruction *I = foldIntrinsicWithOverflowCommon(II)) + return I; - Value *OperationResult = nullptr; - Constant *OverflowResult = nullptr; - if (OptimizeOverflowCheck(OCF, II->getArgOperand(0), II->getArgOperand(1), - *II, OperationResult, OverflowResult)) - return CreateOverflowTuple(II, OperationResult, OverflowResult); + Constant *C; + Value *Arg0 = II->getArgOperand(0); + Value *Arg1 = II->getArgOperand(1); + // Given a constant C that is not the minimum signed value + // for an integer of a given bit width: + // + // ssubo X, C -> saddo X, -C + if (match(Arg1, m_Constant(C)) && C->isNotMinSignedValue()) { + Value *NegVal = ConstantExpr::getNeg(C); + // Build a saddo call that is equivalent to the discovered + // ssubo call. + return replaceInstUsesWith( + *II, Builder.CreateBinaryIntrinsic(Intrinsic::sadd_with_overflow, + Arg0, NegVal)); + } break; } @@ -2047,39 +2077,32 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { LLVM_FALLTHROUGH; case Intrinsic::usub_sat: case Intrinsic::ssub_sat: { - Value *Arg0 = II->getArgOperand(0); - Value *Arg1 = II->getArgOperand(1); - Intrinsic::ID IID = II->getIntrinsicID(); + SaturatingInst *SI = cast<SaturatingInst>(II); + Type *Ty = SI->getType(); + Value *Arg0 = SI->getLHS(); + Value *Arg1 = SI->getRHS(); // Make use of known overflow information. - OverflowResult OR; - switch (IID) { - default: - llvm_unreachable("Unexpected intrinsic!"); - case Intrinsic::uadd_sat: - OR = computeOverflowForUnsignedAdd(Arg0, Arg1, II); - if (OR == OverflowResult::NeverOverflows) - return BinaryOperator::CreateNUWAdd(Arg0, Arg1); - if (OR == OverflowResult::AlwaysOverflows) - return replaceInstUsesWith(*II, - ConstantInt::getAllOnesValue(II->getType())); - break; - case Intrinsic::usub_sat: - OR = computeOverflowForUnsignedSub(Arg0, Arg1, II); - if (OR == OverflowResult::NeverOverflows) - return BinaryOperator::CreateNUWSub(Arg0, Arg1); - if (OR == OverflowResult::AlwaysOverflows) - return replaceInstUsesWith(*II, - ConstantInt::getNullValue(II->getType())); - break; - case Intrinsic::sadd_sat: - if (willNotOverflowSignedAdd(Arg0, Arg1, *II)) - return BinaryOperator::CreateNSWAdd(Arg0, Arg1); - break; - case Intrinsic::ssub_sat: - if (willNotOverflowSignedSub(Arg0, Arg1, *II)) - return BinaryOperator::CreateNSWSub(Arg0, Arg1); - break; + OverflowResult OR = computeOverflow(SI->getBinaryOp(), SI->isSigned(), + Arg0, Arg1, SI); + switch (OR) { + case OverflowResult::MayOverflow: + break; + case OverflowResult::NeverOverflows: + if (SI->isSigned()) + return BinaryOperator::CreateNSW(SI->getBinaryOp(), Arg0, Arg1); + else + return BinaryOperator::CreateNUW(SI->getBinaryOp(), Arg0, Arg1); + case OverflowResult::AlwaysOverflowsLow: { + unsigned BitWidth = Ty->getScalarSizeInBits(); + APInt Min = APSInt::getMinValue(BitWidth, !SI->isSigned()); + return replaceInstUsesWith(*SI, ConstantInt::get(Ty, Min)); + } + case OverflowResult::AlwaysOverflowsHigh: { + unsigned BitWidth = Ty->getScalarSizeInBits(); + APInt Max = APSInt::getMaxValue(BitWidth, !SI->isSigned()); + return replaceInstUsesWith(*SI, ConstantInt::get(Ty, Max)); + } } // ssub.sat(X, C) -> sadd.sat(X, -C) if C != MIN @@ -2101,7 +2124,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { APInt NewVal; bool IsUnsigned = IID == Intrinsic::uadd_sat || IID == Intrinsic::usub_sat; - if (Other->getIntrinsicID() == II->getIntrinsicID() && + if (Other->getIntrinsicID() == IID && match(Arg1, m_APInt(Val)) && match(Other->getArgOperand(0), m_Value(X)) && match(Other->getArgOperand(1), m_APInt(Val2))) { @@ -2136,7 +2159,6 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { return I; Value *Arg0 = II->getArgOperand(0); Value *Arg1 = II->getArgOperand(1); - Intrinsic::ID IID = II->getIntrinsicID(); Value *X, *Y; if (match(Arg0, m_FNeg(m_Value(X))) && match(Arg1, m_FNeg(m_Value(Y))) && (Arg0->hasOneUse() || Arg1->hasOneUse())) { @@ -2266,8 +2288,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { Value *ExtSrc; if (match(II->getArgOperand(0), m_OneUse(m_FPExt(m_Value(ExtSrc))))) { // Narrow the call: intrinsic (fpext x) -> fpext (intrinsic x) - Value *NarrowII = - Builder.CreateUnaryIntrinsic(II->getIntrinsicID(), ExtSrc, II); + Value *NarrowII = Builder.CreateUnaryIntrinsic(IID, ExtSrc, II); return new FPExtInst(NarrowII, II->getType()); } break; @@ -2302,7 +2323,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { &DT) >= 16) { Value *Ptr = Builder.CreateBitCast(II->getArgOperand(0), PointerType::getUnqual(II->getType())); - return new LoadInst(Ptr); + return new LoadInst(II->getType(), Ptr); } break; case Intrinsic::ppc_vsx_lxvw4x: @@ -2310,7 +2331,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { // Turn PPC VSX loads into normal loads. Value *Ptr = Builder.CreateBitCast(II->getArgOperand(0), PointerType::getUnqual(II->getType())); - return new LoadInst(Ptr, Twine(""), false, 1); + return new LoadInst(II->getType(), Ptr, Twine(""), false, 1); } case Intrinsic::ppc_altivec_stvx: case Intrinsic::ppc_altivec_stvxl: @@ -2338,7 +2359,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { II->getType()->getVectorNumElements()); Value *Ptr = Builder.CreateBitCast(II->getArgOperand(0), PointerType::getUnqual(VTy)); - Value *Load = Builder.CreateLoad(Ptr); + Value *Load = Builder.CreateLoad(VTy, Ptr); return new FPExtInst(Load, II->getType()); } break; @@ -2348,7 +2369,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { &DT) >= 32) { Value *Ptr = Builder.CreateBitCast(II->getArgOperand(0), PointerType::getUnqual(II->getType())); - return new LoadInst(Ptr); + return new LoadInst(II->getType(), Ptr); } break; case Intrinsic::ppc_qpx_qvstfs: @@ -2499,22 +2520,6 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { break; } - case Intrinsic::x86_sse41_round_ps: - case Intrinsic::x86_sse41_round_pd: - case Intrinsic::x86_avx_round_ps_256: - case Intrinsic::x86_avx_round_pd_256: - case Intrinsic::x86_avx512_mask_rndscale_ps_128: - case Intrinsic::x86_avx512_mask_rndscale_ps_256: - case Intrinsic::x86_avx512_mask_rndscale_ps_512: - case Intrinsic::x86_avx512_mask_rndscale_pd_128: - case Intrinsic::x86_avx512_mask_rndscale_pd_256: - case Intrinsic::x86_avx512_mask_rndscale_pd_512: - case Intrinsic::x86_avx512_mask_rndscale_ss: - case Intrinsic::x86_avx512_mask_rndscale_sd: - if (Value *V = simplifyX86round(*II, Builder)) - return replaceInstUsesWith(*II, V); - break; - case Intrinsic::x86_mmx_pmovmskb: case Intrinsic::x86_sse_movmsk_ps: case Intrinsic::x86_sse2_movmsk_pd: @@ -2620,7 +2625,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { Value *Arg1 = II->getArgOperand(1); Value *V; - switch (II->getIntrinsicID()) { + switch (IID) { default: llvm_unreachable("Case stmts out of sync!"); case Intrinsic::x86_avx512_add_ps_512: case Intrinsic::x86_avx512_add_pd_512: @@ -2664,7 +2669,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { Value *RHS = Builder.CreateExtractElement(Arg1, (uint64_t)0); Value *V; - switch (II->getIntrinsicID()) { + switch (IID) { default: llvm_unreachable("Case stmts out of sync!"); case Intrinsic::x86_avx512_mask_add_ss_round: case Intrinsic::x86_avx512_mask_add_sd_round: @@ -2706,44 +2711,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { return replaceInstUsesWith(*II, V); } } - LLVM_FALLTHROUGH; - - // X86 scalar intrinsics simplified with SimplifyDemandedVectorElts. - case Intrinsic::x86_avx512_mask_max_ss_round: - case Intrinsic::x86_avx512_mask_min_ss_round: - case Intrinsic::x86_avx512_mask_max_sd_round: - case Intrinsic::x86_avx512_mask_min_sd_round: - case Intrinsic::x86_sse_cmp_ss: - case Intrinsic::x86_sse_min_ss: - case Intrinsic::x86_sse_max_ss: - case Intrinsic::x86_sse2_cmp_sd: - case Intrinsic::x86_sse2_min_sd: - case Intrinsic::x86_sse2_max_sd: - case Intrinsic::x86_xop_vfrcz_ss: - case Intrinsic::x86_xop_vfrcz_sd: { - unsigned VWidth = II->getType()->getVectorNumElements(); - APInt UndefElts(VWidth, 0); - APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth)); - if (Value *V = SimplifyDemandedVectorElts(II, AllOnesEltMask, UndefElts)) { - if (V != II) - return replaceInstUsesWith(*II, V); - return II; - } - break; - } - case Intrinsic::x86_sse41_round_ss: - case Intrinsic::x86_sse41_round_sd: { - unsigned VWidth = II->getType()->getVectorNumElements(); - APInt UndefElts(VWidth, 0); - APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth)); - if (Value *V = SimplifyDemandedVectorElts(II, AllOnesEltMask, UndefElts)) { - if (V != II) - return replaceInstUsesWith(*II, V); - return II; - } else if (Value *V = simplifyX86round(*II, Builder)) - return replaceInstUsesWith(*II, V); break; - } // Constant fold ashr( <A x Bi>, Ci ). // Constant fold lshr( <A x Bi>, Ci ). @@ -2860,7 +2828,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { case Intrinsic::x86_avx2_packsswb: case Intrinsic::x86_avx512_packssdw_512: case Intrinsic::x86_avx512_packsswb_512: - if (Value *V = simplifyX86pack(*II, true)) + if (Value *V = simplifyX86pack(*II, Builder, true)) return replaceInstUsesWith(*II, V); break; @@ -2870,7 +2838,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { case Intrinsic::x86_avx2_packuswb: case Intrinsic::x86_avx512_packusdw_512: case Intrinsic::x86_avx512_packuswb_512: - if (Value *V = simplifyX86pack(*II, false)) + if (Value *V = simplifyX86pack(*II, Builder, false)) return replaceInstUsesWith(*II, V); break; @@ -3168,19 +3136,9 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { return nullptr; break; - case Intrinsic::x86_xop_vpcomb: - case Intrinsic::x86_xop_vpcomd: - case Intrinsic::x86_xop_vpcomq: - case Intrinsic::x86_xop_vpcomw: - if (Value *V = simplifyX86vpcom(*II, Builder, true)) - return replaceInstUsesWith(*II, V); - break; - - case Intrinsic::x86_xop_vpcomub: - case Intrinsic::x86_xop_vpcomud: - case Intrinsic::x86_xop_vpcomuq: - case Intrinsic::x86_xop_vpcomuw: - if (Value *V = simplifyX86vpcom(*II, Builder, false)) + case Intrinsic::x86_addcarry_32: + case Intrinsic::x86_addcarry_64: + if (Value *V = simplifyX86addcarry(*II, Builder)) return replaceInstUsesWith(*II, V); break; @@ -3296,8 +3254,8 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { } // Check for constant LHS & RHS - in this case we just simplify. - bool Zext = (II->getIntrinsicID() == Intrinsic::arm_neon_vmullu || - II->getIntrinsicID() == Intrinsic::aarch64_neon_umull); + bool Zext = (IID == Intrinsic::arm_neon_vmullu || + IID == Intrinsic::aarch64_neon_umull); VectorType *NewVT = cast<VectorType>(II->getType()); if (Constant *CV0 = dyn_cast<Constant>(Arg0)) { if (Constant *CV1 = dyn_cast<Constant>(Arg1)) { @@ -3374,7 +3332,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { APFloat Significand = frexp(C->getValueAPF(), Exp, APFloat::rmNearestTiesToEven); - if (II->getIntrinsicID() == Intrinsic::amdgcn_frexp_mant) { + if (IID == Intrinsic::amdgcn_frexp_mant) { return replaceInstUsesWith(CI, ConstantFP::get(II->getContext(), Significand)); } @@ -3559,7 +3517,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { } } - bool Signed = II->getIntrinsicID() == Intrinsic::amdgcn_sbfe; + bool Signed = IID == Intrinsic::amdgcn_sbfe; if (!CWidth || !COffset) break; @@ -3587,15 +3545,12 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { } case Intrinsic::amdgcn_exp: case Intrinsic::amdgcn_exp_compr: { - ConstantInt *En = dyn_cast<ConstantInt>(II->getArgOperand(1)); - if (!En) // Illegal. - break; - + ConstantInt *En = cast<ConstantInt>(II->getArgOperand(1)); unsigned EnBits = En->getZExtValue(); if (EnBits == 0xf) break; // All inputs enabled. - bool IsCompr = II->getIntrinsicID() == Intrinsic::amdgcn_exp_compr; + bool IsCompr = IID == Intrinsic::amdgcn_exp_compr; bool Changed = false; for (int I = 0; I < (IsCompr ? 2 : 4); ++I) { if ((!IsCompr && (EnBits & (1 << I)) == 0) || @@ -3680,13 +3635,10 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { } case Intrinsic::amdgcn_icmp: case Intrinsic::amdgcn_fcmp: { - const ConstantInt *CC = dyn_cast<ConstantInt>(II->getArgOperand(2)); - if (!CC) - break; - + const ConstantInt *CC = cast<ConstantInt>(II->getArgOperand(2)); // Guard against invalid arguments. int64_t CCVal = CC->getZExtValue(); - bool IsInteger = II->getIntrinsicID() == Intrinsic::amdgcn_icmp; + bool IsInteger = IID == Intrinsic::amdgcn_icmp; if ((IsInteger && (CCVal < CmpInst::FIRST_ICMP_PREDICATE || CCVal > CmpInst::LAST_ICMP_PREDICATE)) || (!IsInteger && (CCVal < CmpInst::FIRST_FCMP_PREDICATE || @@ -3709,7 +3661,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { // register (which contains the bitmask of live threads). So a // comparison that always returns true is the same as a read of the // EXEC register. - Value *NewF = Intrinsic::getDeclaration( + Function *NewF = Intrinsic::getDeclaration( II->getModule(), Intrinsic::read_register, II->getType()); Metadata *MDArgs[] = {MDString::get(II->getContext(), "exec")}; MDNode *MD = MDNode::get(II->getContext(), MDArgs); @@ -3804,8 +3756,10 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { } else if (!Ty->isFloatTy() && !Ty->isDoubleTy() && !Ty->isHalfTy()) break; - Value *NewF = Intrinsic::getDeclaration(II->getModule(), NewIID, - SrcLHS->getType()); + Function *NewF = + Intrinsic::getDeclaration(II->getModule(), NewIID, + { II->getType(), + SrcLHS->getType() }); Value *Args[] = { SrcLHS, SrcRHS, ConstantInt::get(CC->getType(), SrcPred) }; CallInst *NewCall = Builder.CreateCall(NewF, Args); @@ -3833,11 +3787,10 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { case Intrinsic::amdgcn_update_dpp: { Value *Old = II->getArgOperand(0); - auto BC = dyn_cast<ConstantInt>(II->getArgOperand(5)); - auto RM = dyn_cast<ConstantInt>(II->getArgOperand(3)); - auto BM = dyn_cast<ConstantInt>(II->getArgOperand(4)); - if (!BC || !RM || !BM || - BC->isZeroValue() || + auto BC = cast<ConstantInt>(II->getArgOperand(5)); + auto RM = cast<ConstantInt>(II->getArgOperand(3)); + auto BM = cast<ConstantInt>(II->getArgOperand(4)); + if (BC->isZeroValue() || RM->getZExtValue() != 0xF || BM->getZExtValue() != 0xF || isa<UndefValue>(Old)) @@ -3847,6 +3800,37 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { II->setOperand(0, UndefValue::get(Old->getType())); return II; } + case Intrinsic::amdgcn_readfirstlane: + case Intrinsic::amdgcn_readlane: { + // A constant value is trivially uniform. + if (Constant *C = dyn_cast<Constant>(II->getArgOperand(0))) + return replaceInstUsesWith(*II, C); + + // The rest of these may not be safe if the exec may not be the same between + // the def and use. + Value *Src = II->getArgOperand(0); + Instruction *SrcInst = dyn_cast<Instruction>(Src); + if (SrcInst && SrcInst->getParent() != II->getParent()) + break; + + // readfirstlane (readfirstlane x) -> readfirstlane x + // readlane (readfirstlane x), y -> readfirstlane x + if (match(Src, m_Intrinsic<Intrinsic::amdgcn_readfirstlane>())) + return replaceInstUsesWith(*II, Src); + + if (IID == Intrinsic::amdgcn_readfirstlane) { + // readfirstlane (readlane x, y) -> readlane x, y + if (match(Src, m_Intrinsic<Intrinsic::amdgcn_readlane>())) + return replaceInstUsesWith(*II, Src); + } else { + // readlane (readlane x, y), y -> readlane x, y + if (match(Src, m_Intrinsic<Intrinsic::amdgcn_readlane>( + m_Value(), m_Specific(II->getArgOperand(1))))) + return replaceInstUsesWith(*II, Src); + } + + break; + } case Intrinsic::stackrestore: { // If the save is right next to the restore, remove the restore. This can // happen when variable allocas are DCE'd. @@ -3870,14 +3854,14 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { break; } if (CallInst *BCI = dyn_cast<CallInst>(BI)) { - if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(BCI)) { + if (auto *II2 = dyn_cast<IntrinsicInst>(BCI)) { // If there is a stackrestore below this one, remove this one. - if (II->getIntrinsicID() == Intrinsic::stackrestore) + if (II2->getIntrinsicID() == Intrinsic::stackrestore) return eraseInstFromFunction(CI); // Bail if we cross over an intrinsic with side effects, such as // llvm.stacksave, llvm.read_register, or llvm.setjmp. - if (II->mayHaveSideEffects()) { + if (II2->mayHaveSideEffects()) { CannotRemove = true; break; } @@ -3920,16 +3904,20 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { // Canonicalize assume(a && b) -> assume(a); assume(b); // Note: New assumption intrinsics created here are registered by // the InstCombineIRInserter object. - Value *AssumeIntrinsic = II->getCalledValue(), *A, *B; + FunctionType *AssumeIntrinsicTy = II->getFunctionType(); + Value *AssumeIntrinsic = II->getCalledValue(); + Value *A, *B; if (match(IIOperand, m_And(m_Value(A), m_Value(B)))) { - Builder.CreateCall(AssumeIntrinsic, A, II->getName()); - Builder.CreateCall(AssumeIntrinsic, B, II->getName()); + Builder.CreateCall(AssumeIntrinsicTy, AssumeIntrinsic, A, II->getName()); + Builder.CreateCall(AssumeIntrinsicTy, AssumeIntrinsic, B, II->getName()); return eraseInstFromFunction(*II); } // assume(!(a || b)) -> assume(!a); assume(!b); if (match(IIOperand, m_Not(m_Or(m_Value(A), m_Value(B))))) { - Builder.CreateCall(AssumeIntrinsic, Builder.CreateNot(A), II->getName()); - Builder.CreateCall(AssumeIntrinsic, Builder.CreateNot(B), II->getName()); + Builder.CreateCall(AssumeIntrinsicTy, AssumeIntrinsic, + Builder.CreateNot(A), II->getName()); + Builder.CreateCall(AssumeIntrinsicTy, AssumeIntrinsic, + Builder.CreateNot(B), II->getName()); return eraseInstFromFunction(*II); } @@ -4036,7 +4024,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { break; } } - return visitCallSite(II); + return visitCallBase(*II); } // Fence instruction simplification @@ -4051,12 +4039,17 @@ Instruction *InstCombiner::visitFenceInst(FenceInst &FI) { // InvokeInst simplification Instruction *InstCombiner::visitInvokeInst(InvokeInst &II) { - return visitCallSite(&II); + return visitCallBase(II); +} + +// CallBrInst simplification +Instruction *InstCombiner::visitCallBrInst(CallBrInst &CBI) { + return visitCallBase(CBI); } /// If this cast does not affect the value passed through the varargs area, we /// can eliminate the use of the cast. -static bool isSafeToEliminateVarargsCast(const CallSite CS, +static bool isSafeToEliminateVarargsCast(const CallBase &Call, const DataLayout &DL, const CastInst *const CI, const int ix) { @@ -4068,18 +4061,20 @@ static bool isSafeToEliminateVarargsCast(const CallSite CS, // TODO: This is probably something which should be expanded to all // intrinsics since the entire point of intrinsics is that // they are understandable by the optimizer. - if (isStatepoint(CS) || isGCRelocate(CS) || isGCResult(CS)) + if (isStatepoint(&Call) || isGCRelocate(&Call) || isGCResult(&Call)) return false; // The size of ByVal or InAlloca arguments is derived from the type, so we // can't change to a type with a different size. If the size were // passed explicitly we could avoid this check. - if (!CS.isByValOrInAllocaArgument(ix)) + if (!Call.isByValOrInAllocaArgument(ix)) return true; Type* SrcTy = cast<PointerType>(CI->getOperand(0)->getType())->getElementType(); - Type* DstTy = cast<PointerType>(CI->getType())->getElementType(); + Type *DstTy = Call.isByValArgument(ix) + ? Call.getParamByValType(ix) + : cast<PointerType>(CI->getType())->getElementType(); if (!SrcTy->isSized() || !DstTy->isSized()) return false; if (DL.getTypeAllocSize(SrcTy) != DL.getTypeAllocSize(DstTy)) @@ -4096,7 +4091,7 @@ Instruction *InstCombiner::tryOptimizeCall(CallInst *CI) { auto InstCombineErase = [this](Instruction *I) { eraseInstFromFunction(*I); }; - LibCallSimplifier Simplifier(DL, &TLI, ORE, InstCombineRAUW, + LibCallSimplifier Simplifier(DL, &TLI, ORE, BFI, PSI, InstCombineRAUW, InstCombineErase); if (Value *With = Simplifier.optimizeCall(CI)) { ++NumSimplified; @@ -4182,10 +4177,10 @@ static IntrinsicInst *findInitTrampoline(Value *Callee) { return nullptr; } -/// Improvements for call and invoke instructions. -Instruction *InstCombiner::visitCallSite(CallSite CS) { - if (isAllocLikeFn(CS.getInstruction(), &TLI)) - return visitAllocSite(*CS.getInstruction()); +/// Improvements for call, callbr and invoke instructions. +Instruction *InstCombiner::visitCallBase(CallBase &Call) { + if (isAllocLikeFn(&Call, &TLI)) + return visitAllocSite(Call); bool Changed = false; @@ -4195,52 +4190,50 @@ Instruction *InstCombiner::visitCallSite(CallSite CS) { SmallVector<unsigned, 4> ArgNos; unsigned ArgNo = 0; - for (Value *V : CS.args()) { + for (Value *V : Call.args()) { if (V->getType()->isPointerTy() && - !CS.paramHasAttr(ArgNo, Attribute::NonNull) && - isKnownNonZero(V, DL, 0, &AC, CS.getInstruction(), &DT)) + !Call.paramHasAttr(ArgNo, Attribute::NonNull) && + isKnownNonZero(V, DL, 0, &AC, &Call, &DT)) ArgNos.push_back(ArgNo); ArgNo++; } - assert(ArgNo == CS.arg_size() && "sanity check"); + assert(ArgNo == Call.arg_size() && "sanity check"); if (!ArgNos.empty()) { - AttributeList AS = CS.getAttributes(); - LLVMContext &Ctx = CS.getInstruction()->getContext(); + AttributeList AS = Call.getAttributes(); + LLVMContext &Ctx = Call.getContext(); AS = AS.addParamAttribute(Ctx, ArgNos, Attribute::get(Ctx, Attribute::NonNull)); - CS.setAttributes(AS); + Call.setAttributes(AS); Changed = true; } // If the callee is a pointer to a function, attempt to move any casts to the - // arguments of the call/invoke. - Value *Callee = CS.getCalledValue(); - if (!isa<Function>(Callee) && transformConstExprCastCall(CS)) + // arguments of the call/callbr/invoke. + Value *Callee = Call.getCalledValue(); + if (!isa<Function>(Callee) && transformConstExprCastCall(Call)) return nullptr; if (Function *CalleeF = dyn_cast<Function>(Callee)) { // Remove the convergent attr on calls when the callee is not convergent. - if (CS.isConvergent() && !CalleeF->isConvergent() && + if (Call.isConvergent() && !CalleeF->isConvergent() && !CalleeF->isIntrinsic()) { - LLVM_DEBUG(dbgs() << "Removing convergent attr from instr " - << CS.getInstruction() << "\n"); - CS.setNotConvergent(); - return CS.getInstruction(); + LLVM_DEBUG(dbgs() << "Removing convergent attr from instr " << Call + << "\n"); + Call.setNotConvergent(); + return &Call; } // If the call and callee calling conventions don't match, this call must // be unreachable, as the call is undefined. - if (CalleeF->getCallingConv() != CS.getCallingConv() && + if (CalleeF->getCallingConv() != Call.getCallingConv() && // Only do this for calls to a function with a body. A prototype may // not actually end up matching the implementation's calling conv for a // variety of reasons (e.g. it may be written in assembly). !CalleeF->isDeclaration()) { - Instruction *OldCall = CS.getInstruction(); - new StoreInst(ConstantInt::getTrue(Callee->getContext()), - UndefValue::get(Type::getInt1PtrTy(Callee->getContext())), - OldCall); + Instruction *OldCall = &Call; + CreateNonTerminatorUnreachable(OldCall); // If OldCall does not return void then replaceAllUsesWith undef. // This allows ValueHandlers and custom metadata to adjust itself. if (!OldCall->getType()->isVoidTy()) @@ -4248,40 +4241,35 @@ Instruction *InstCombiner::visitCallSite(CallSite CS) { if (isa<CallInst>(OldCall)) return eraseInstFromFunction(*OldCall); - // We cannot remove an invoke, because it would change the CFG, just - // change the callee to a null pointer. - cast<InvokeInst>(OldCall)->setCalledFunction( - Constant::getNullValue(CalleeF->getType())); + // We cannot remove an invoke or a callbr, because it would change thexi + // CFG, just change the callee to a null pointer. + cast<CallBase>(OldCall)->setCalledFunction( + CalleeF->getFunctionType(), + Constant::getNullValue(CalleeF->getType())); return nullptr; } } if ((isa<ConstantPointerNull>(Callee) && - !NullPointerIsDefined(CS.getInstruction()->getFunction())) || + !NullPointerIsDefined(Call.getFunction())) || isa<UndefValue>(Callee)) { - // If CS does not return void then replaceAllUsesWith undef. + // If Call does not return void then replaceAllUsesWith undef. // This allows ValueHandlers and custom metadata to adjust itself. - if (!CS.getInstruction()->getType()->isVoidTy()) - replaceInstUsesWith(*CS.getInstruction(), - UndefValue::get(CS.getInstruction()->getType())); + if (!Call.getType()->isVoidTy()) + replaceInstUsesWith(Call, UndefValue::get(Call.getType())); - if (isa<InvokeInst>(CS.getInstruction())) { - // Can't remove an invoke because we cannot change the CFG. + if (Call.isTerminator()) { + // Can't remove an invoke or callbr because we cannot change the CFG. return nullptr; } - // This instruction is not reachable, just remove it. We insert a store to - // undef so that we know that this code is not reachable, despite the fact - // that we can't modify the CFG here. - new StoreInst(ConstantInt::getTrue(Callee->getContext()), - UndefValue::get(Type::getInt1PtrTy(Callee->getContext())), - CS.getInstruction()); - - return eraseInstFromFunction(*CS.getInstruction()); + // This instruction is not reachable, just remove it. + CreateNonTerminatorUnreachable(&Call); + return eraseInstFromFunction(Call); } if (IntrinsicInst *II = findInitTrampoline(Callee)) - return transformCallThroughTrampoline(CS, II); + return transformCallThroughTrampoline(Call, *II); PointerType *PTy = cast<PointerType>(Callee->getType()); FunctionType *FTy = cast<FunctionType>(PTy->getElementType()); @@ -4289,39 +4277,48 @@ Instruction *InstCombiner::visitCallSite(CallSite CS) { int ix = FTy->getNumParams(); // See if we can optimize any arguments passed through the varargs area of // the call. - for (CallSite::arg_iterator I = CS.arg_begin() + FTy->getNumParams(), - E = CS.arg_end(); I != E; ++I, ++ix) { + for (auto I = Call.arg_begin() + FTy->getNumParams(), E = Call.arg_end(); + I != E; ++I, ++ix) { CastInst *CI = dyn_cast<CastInst>(*I); - if (CI && isSafeToEliminateVarargsCast(CS, DL, CI, ix)) { + if (CI && isSafeToEliminateVarargsCast(Call, DL, CI, ix)) { *I = CI->getOperand(0); + + // Update the byval type to match the argument type. + if (Call.isByValArgument(ix)) { + Call.removeParamAttr(ix, Attribute::ByVal); + Call.addParamAttr( + ix, Attribute::getWithByValType( + Call.getContext(), + CI->getOperand(0)->getType()->getPointerElementType())); + } Changed = true; } } } - if (isa<InlineAsm>(Callee) && !CS.doesNotThrow()) { + if (isa<InlineAsm>(Callee) && !Call.doesNotThrow()) { // Inline asm calls cannot throw - mark them 'nounwind'. - CS.setDoesNotThrow(); + Call.setDoesNotThrow(); Changed = true; } // Try to optimize the call if possible, we require DataLayout for most of // this. None of these calls are seen as possibly dead so go ahead and // delete the instruction now. - if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) { + if (CallInst *CI = dyn_cast<CallInst>(&Call)) { Instruction *I = tryOptimizeCall(CI); // If we changed something return the result, etc. Otherwise let // the fallthrough check. if (I) return eraseInstFromFunction(*I); } - return Changed ? CS.getInstruction() : nullptr; + return Changed ? &Call : nullptr; } /// If the callee is a constexpr cast of a function, attempt to move the cast to -/// the arguments of the call/invoke. -bool InstCombiner::transformConstExprCastCall(CallSite CS) { - auto *Callee = dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts()); +/// the arguments of the call/callbr/invoke. +bool InstCombiner::transformConstExprCastCall(CallBase &Call) { + auto *Callee = dyn_cast<Function>(Call.getCalledValue()->stripPointerCasts()); if (!Callee) return false; @@ -4335,11 +4332,11 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) { // prototype with the exception of pointee types. The code below doesn't // implement that, so we can't do this transform. // TODO: Do the transform if it only requires adding pointer casts. - if (CS.isMustTailCall()) + if (Call.isMustTailCall()) return false; - Instruction *Caller = CS.getInstruction(); - const AttributeList &CallerPAL = CS.getAttributes(); + Instruction *Caller = &Call; + const AttributeList &CallerPAL = Call.getAttributes(); // Okay, this is a cast from a function to a different type. Unless doing so // would cause a type conversion of one of our arguments, change this call to @@ -4370,20 +4367,24 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) { return false; // Attribute not compatible with transformed value. } - // If the callsite is an invoke instruction, and the return value is used by - // a PHI node in a successor, we cannot change the return type of the call - // because there is no place to put the cast instruction (without breaking - // the critical edge). Bail out in this case. - if (!Caller->use_empty()) + // If the callbase is an invoke/callbr instruction, and the return value is + // used by a PHI node in a successor, we cannot change the return type of + // the call because there is no place to put the cast instruction (without + // breaking the critical edge). Bail out in this case. + if (!Caller->use_empty()) { if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) for (User *U : II->users()) if (PHINode *PN = dyn_cast<PHINode>(U)) if (PN->getParent() == II->getNormalDest() || PN->getParent() == II->getUnwindDest()) return false; + // FIXME: Be conservative for callbr to avoid a quadratic search. + if (isa<CallBrInst>(Caller)) + return false; + } } - unsigned NumActualArgs = CS.arg_size(); + unsigned NumActualArgs = Call.arg_size(); unsigned NumCommonArgs = std::min(FT->getNumParams(), NumActualArgs); // Prevent us turning: @@ -4398,7 +4399,7 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) { Callee->getAttributes().hasAttrSomewhere(Attribute::ByVal)) return false; - CallSite::arg_iterator AI = CS.arg_begin(); + auto AI = Call.arg_begin(); for (unsigned i = 0, e = NumCommonArgs; i != e; ++i, ++AI) { Type *ParamTy = FT->getParamType(i); Type *ActTy = (*AI)->getType(); @@ -4410,7 +4411,7 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) { .overlaps(AttributeFuncs::typeIncompatible(ParamTy))) return false; // Attribute not compatible with transformed value. - if (CS.isInAllocaArgument(i)) + if (Call.isInAllocaArgument(i)) return false; // Cannot transform to and from inalloca. // If the parameter is passed as a byval argument, then we have to have a @@ -4420,7 +4421,7 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) { if (!ParamPTy || !ParamPTy->getElementType()->isSized()) return false; - Type *CurElTy = ActTy->getPointerElementType(); + Type *CurElTy = Call.getParamByValType(i); if (DL.getTypeAllocSize(CurElTy) != DL.getTypeAllocSize(ParamPTy->getElementType())) return false; @@ -4435,7 +4436,7 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) { // If the callee is just a declaration, don't change the varargsness of the // call. We don't want to introduce a varargs call where one doesn't // already exist. - PointerType *APTy = cast<PointerType>(CS.getCalledValue()->getType()); + PointerType *APTy = cast<PointerType>(Call.getCalledValue()->getType()); if (FT->isVarArg()!=cast<FunctionType>(APTy->getElementType())->isVarArg()) return false; @@ -4474,7 +4475,8 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) { // with the existing attributes. Wipe out any problematic attributes. RAttrs.remove(AttributeFuncs::typeIncompatible(NewRetTy)); - AI = CS.arg_begin(); + LLVMContext &Ctx = Call.getContext(); + AI = Call.arg_begin(); for (unsigned i = 0; i != NumCommonArgs; ++i, ++AI) { Type *ParamTy = FT->getParamType(i); @@ -4484,7 +4486,12 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) { Args.push_back(NewArg); // Add any parameter attributes. - ArgAttrs.push_back(CallerPAL.getParamAttributes(i)); + if (CallerPAL.hasParamAttribute(i, Attribute::ByVal)) { + AttrBuilder AB(CallerPAL.getParamAttributes(i)); + AB.addByValAttr(NewArg->getType()->getPointerElementType()); + ArgAttrs.push_back(AttributeSet::get(Ctx, AB)); + } else + ArgAttrs.push_back(CallerPAL.getParamAttributes(i)); } // If the function takes more arguments than the call was taking, add them @@ -4523,45 +4530,50 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) { assert((ArgAttrs.size() == FT->getNumParams() || FT->isVarArg()) && "missing argument attributes"); - LLVMContext &Ctx = Callee->getContext(); AttributeList NewCallerPAL = AttributeList::get( Ctx, FnAttrs, AttributeSet::get(Ctx, RAttrs), ArgAttrs); SmallVector<OperandBundleDef, 1> OpBundles; - CS.getOperandBundlesAsDefs(OpBundles); + Call.getOperandBundlesAsDefs(OpBundles); - CallSite NewCS; + CallBase *NewCall; if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) { - NewCS = Builder.CreateInvoke(Callee, II->getNormalDest(), - II->getUnwindDest(), Args, OpBundles); + NewCall = Builder.CreateInvoke(Callee, II->getNormalDest(), + II->getUnwindDest(), Args, OpBundles); + } else if (CallBrInst *CBI = dyn_cast<CallBrInst>(Caller)) { + NewCall = Builder.CreateCallBr(Callee, CBI->getDefaultDest(), + CBI->getIndirectDests(), Args, OpBundles); } else { - NewCS = Builder.CreateCall(Callee, Args, OpBundles); - cast<CallInst>(NewCS.getInstruction()) - ->setTailCallKind(cast<CallInst>(Caller)->getTailCallKind()); + NewCall = Builder.CreateCall(Callee, Args, OpBundles); + cast<CallInst>(NewCall)->setTailCallKind( + cast<CallInst>(Caller)->getTailCallKind()); } - NewCS->takeName(Caller); - NewCS.setCallingConv(CS.getCallingConv()); - NewCS.setAttributes(NewCallerPAL); + NewCall->takeName(Caller); + NewCall->setCallingConv(Call.getCallingConv()); + NewCall->setAttributes(NewCallerPAL); // Preserve the weight metadata for the new call instruction. The metadata // is used by SamplePGO to check callsite's hotness. uint64_t W; if (Caller->extractProfTotalWeight(W)) - NewCS->setProfWeight(W); + NewCall->setProfWeight(W); // Insert a cast of the return type as necessary. - Instruction *NC = NewCS.getInstruction(); + Instruction *NC = NewCall; Value *NV = NC; if (OldRetTy != NV->getType() && !Caller->use_empty()) { if (!NV->getType()->isVoidTy()) { NV = NC = CastInst::CreateBitOrPointerCast(NC, OldRetTy); NC->setDebugLoc(Caller->getDebugLoc()); - // If this is an invoke instruction, we should insert it after the first - // non-phi, instruction in the normal successor block. + // If this is an invoke/callbr instruction, we should insert it after the + // first non-phi instruction in the normal successor block. if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) { BasicBlock::iterator I = II->getNormalDest()->getFirstInsertionPt(); InsertNewInstBefore(NC, *I); + } else if (CallBrInst *CBI = dyn_cast<CallBrInst>(Caller)) { + BasicBlock::iterator I = CBI->getDefaultDest()->getFirstInsertionPt(); + InsertNewInstBefore(NC, *I); } else { // Otherwise, it's a call, just insert cast right after the call. InsertNewInstBefore(NC, *Caller); @@ -4590,23 +4602,20 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) { /// Turn a call to a function created by init_trampoline / adjust_trampoline /// intrinsic pair into a direct call to the underlying function. Instruction * -InstCombiner::transformCallThroughTrampoline(CallSite CS, - IntrinsicInst *Tramp) { - Value *Callee = CS.getCalledValue(); - PointerType *PTy = cast<PointerType>(Callee->getType()); - FunctionType *FTy = cast<FunctionType>(PTy->getElementType()); - AttributeList Attrs = CS.getAttributes(); +InstCombiner::transformCallThroughTrampoline(CallBase &Call, + IntrinsicInst &Tramp) { + Value *Callee = Call.getCalledValue(); + Type *CalleeTy = Callee->getType(); + FunctionType *FTy = Call.getFunctionType(); + AttributeList Attrs = Call.getAttributes(); // If the call already has the 'nest' attribute somewhere then give up - // otherwise 'nest' would occur twice after splicing in the chain. if (Attrs.hasAttrSomewhere(Attribute::Nest)) return nullptr; - assert(Tramp && - "transformCallThroughTrampoline called with incorrect CallSite."); - - Function *NestF =cast<Function>(Tramp->getArgOperand(1)->stripPointerCasts()); - FunctionType *NestFTy = cast<FunctionType>(NestF->getValueType()); + Function *NestF = cast<Function>(Tramp.getArgOperand(1)->stripPointerCasts()); + FunctionType *NestFTy = NestF->getFunctionType(); AttributeList NestAttrs = NestF->getAttributes(); if (!NestAttrs.isEmpty()) { @@ -4628,22 +4637,21 @@ InstCombiner::transformCallThroughTrampoline(CallSite CS, } if (NestTy) { - Instruction *Caller = CS.getInstruction(); std::vector<Value*> NewArgs; std::vector<AttributeSet> NewArgAttrs; - NewArgs.reserve(CS.arg_size() + 1); - NewArgAttrs.reserve(CS.arg_size()); + NewArgs.reserve(Call.arg_size() + 1); + NewArgAttrs.reserve(Call.arg_size()); // Insert the nest argument into the call argument list, which may // mean appending it. Likewise for attributes. { unsigned ArgNo = 0; - CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); + auto I = Call.arg_begin(), E = Call.arg_end(); do { if (ArgNo == NestArgNo) { // Add the chain argument and attributes. - Value *NestVal = Tramp->getArgOperand(2); + Value *NestVal = Tramp.getArgOperand(2); if (NestVal->getType() != NestTy) NestVal = Builder.CreateBitCast(NestVal, NestTy, "nest"); NewArgs.push_back(NestVal); @@ -4705,24 +4713,30 @@ InstCombiner::transformCallThroughTrampoline(CallSite CS, Attrs.getRetAttributes(), NewArgAttrs); SmallVector<OperandBundleDef, 1> OpBundles; - CS.getOperandBundlesAsDefs(OpBundles); + Call.getOperandBundlesAsDefs(OpBundles); Instruction *NewCaller; - if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) { - NewCaller = InvokeInst::Create(NewCallee, + if (InvokeInst *II = dyn_cast<InvokeInst>(&Call)) { + NewCaller = InvokeInst::Create(NewFTy, NewCallee, II->getNormalDest(), II->getUnwindDest(), NewArgs, OpBundles); cast<InvokeInst>(NewCaller)->setCallingConv(II->getCallingConv()); cast<InvokeInst>(NewCaller)->setAttributes(NewPAL); + } else if (CallBrInst *CBI = dyn_cast<CallBrInst>(&Call)) { + NewCaller = + CallBrInst::Create(NewFTy, NewCallee, CBI->getDefaultDest(), + CBI->getIndirectDests(), NewArgs, OpBundles); + cast<CallBrInst>(NewCaller)->setCallingConv(CBI->getCallingConv()); + cast<CallBrInst>(NewCaller)->setAttributes(NewPAL); } else { - NewCaller = CallInst::Create(NewCallee, NewArgs, OpBundles); + NewCaller = CallInst::Create(NewFTy, NewCallee, NewArgs, OpBundles); cast<CallInst>(NewCaller)->setTailCallKind( - cast<CallInst>(Caller)->getTailCallKind()); + cast<CallInst>(Call).getTailCallKind()); cast<CallInst>(NewCaller)->setCallingConv( - cast<CallInst>(Caller)->getCallingConv()); + cast<CallInst>(Call).getCallingConv()); cast<CallInst>(NewCaller)->setAttributes(NewPAL); } - NewCaller->setDebugLoc(Caller->getDebugLoc()); + NewCaller->setDebugLoc(Call.getDebugLoc()); return NewCaller; } @@ -4731,9 +4745,7 @@ InstCombiner::transformCallThroughTrampoline(CallSite CS, // Replace the trampoline call with a direct call. Since there is no 'nest' // parameter, there is no need to adjust the argument list. Let the generic // code sort out any function type mismatches. - Constant *NewCallee = - NestF->getType() == PTy ? NestF : - ConstantExpr::getBitCast(NestF, PTy); - CS.setCalledFunction(NewCallee); - return CS.getInstruction(); + Constant *NewCallee = ConstantExpr::getBitCast(NestF, CalleeTy); + Call.setCalledFunction(FTy, NewCallee); + return &Call; } diff --git a/lib/Transforms/InstCombine/InstCombineCasts.cpp b/lib/Transforms/InstCombine/InstCombineCasts.cpp index 1201ac196ec04..2c9ba203fbf3d 100644 --- a/lib/Transforms/InstCombine/InstCombineCasts.cpp +++ b/lib/Transforms/InstCombine/InstCombineCasts.cpp @@ -1,9 +1,8 @@ //===- InstCombineCasts.cpp -----------------------------------------------===// // -// 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 // //===----------------------------------------------------------------------===// // @@ -1373,10 +1372,8 @@ Instruction *InstCombiner::visitSExt(SExtInst &CI) { // If we know that the value being extended is positive, we can use a zext // instead. KnownBits Known = computeKnownBits(Src, 0, &CI); - if (Known.isNonNegative()) { - Value *ZExt = Builder.CreateZExt(Src, DestTy); - return replaceInstUsesWith(CI, ZExt); - } + if (Known.isNonNegative()) + return CastInst::Create(Instruction::ZExt, Src, DestTy); // Try to extend the entire expression tree to the wide destination type. if (shouldChangeType(SrcTy, DestTy) && canEvaluateSExtd(Src, DestTy)) { @@ -1618,12 +1615,20 @@ Instruction *InstCombiner::visitFPTrunc(FPTruncInst &FPT) { return CastInst::CreateFPCast(ExactResult, Ty); } } + } - // (fptrunc (fneg x)) -> (fneg (fptrunc x)) - Value *X; - if (match(OpI, m_FNeg(m_Value(X)))) { + // (fptrunc (fneg x)) -> (fneg (fptrunc x)) + Value *X; + Instruction *Op = dyn_cast<Instruction>(FPT.getOperand(0)); + if (Op && Op->hasOneUse()) { + if (match(Op, m_FNeg(m_Value(X)))) { Value *InnerTrunc = Builder.CreateFPTrunc(X, Ty); - return BinaryOperator::CreateFNegFMF(InnerTrunc, OpI); + + // FIXME: Once we're sure that unary FNeg optimizations are on par with + // binary FNeg, this should always return a unary operator. + if (isa<BinaryOperator>(Op)) + return BinaryOperator::CreateFNegFMF(InnerTrunc, Op); + return UnaryOperator::CreateFNegFMF(InnerTrunc, Op); } } @@ -1657,8 +1662,8 @@ Instruction *InstCombiner::visitFPTrunc(FPTruncInst &FPT) { II->getIntrinsicID(), Ty); SmallVector<OperandBundleDef, 1> OpBundles; II->getOperandBundlesAsDefs(OpBundles); - CallInst *NewCI = CallInst::Create(Overload, { InnerTrunc }, OpBundles, - II->getName()); + CallInst *NewCI = + CallInst::Create(Overload, {InnerTrunc}, OpBundles, II->getName()); NewCI->copyFastMathFlags(II); return NewCI; } @@ -2167,7 +2172,7 @@ Instruction *InstCombiner::optimizeBitCastFromPhi(CastInst &CI, PHINode *PN) { SmallSetVector<PHINode *, 4> OldPhiNodes; // Find all of the A->B casts and PHI nodes. - // We need to inpect all related PHI nodes, but PHIs can be cyclic, so + // We need to inspect all related PHI nodes, but PHIs can be cyclic, so // OldPhiNodes is used to track all known PHI nodes, before adding a new // PHI to PhiWorklist, it is checked against and added to OldPhiNodes first. PhiWorklist.push_back(PN); @@ -2242,20 +2247,43 @@ Instruction *InstCombiner::optimizeBitCastFromPhi(CastInst &CI, PHINode *PN) { } } + // Traverse all accumulated PHI nodes and process its users, + // which are Stores and BitcCasts. Without this processing + // NewPHI nodes could be replicated and could lead to extra + // moves generated after DeSSA. // If there is a store with type B, change it to type A. - for (User *U : PN->users()) { - auto *SI = dyn_cast<StoreInst>(U); - if (SI && SI->isSimple() && SI->getOperand(0) == PN) { - Builder.SetInsertPoint(SI); - auto *NewBC = - cast<BitCastInst>(Builder.CreateBitCast(NewPNodes[PN], SrcTy)); - SI->setOperand(0, NewBC); - Worklist.Add(SI); - assert(hasStoreUsersOnly(*NewBC)); + + + // Replace users of BitCast B->A with NewPHI. These will help + // later to get rid off a closure formed by OldPHI nodes. + Instruction *RetVal = nullptr; + for (auto *OldPN : OldPhiNodes) { + PHINode *NewPN = NewPNodes[OldPN]; + for (User *V : OldPN->users()) { + if (auto *SI = dyn_cast<StoreInst>(V)) { + if (SI->isSimple() && SI->getOperand(0) == OldPN) { + Builder.SetInsertPoint(SI); + auto *NewBC = + cast<BitCastInst>(Builder.CreateBitCast(NewPN, SrcTy)); + SI->setOperand(0, NewBC); + Worklist.Add(SI); + assert(hasStoreUsersOnly(*NewBC)); + } + } + else if (auto *BCI = dyn_cast<BitCastInst>(V)) { + // Verify it's a B->A cast. + Type *TyB = BCI->getOperand(0)->getType(); + Type *TyA = BCI->getType(); + if (TyA == DestTy && TyB == SrcTy) { + Instruction *I = replaceInstUsesWith(*BCI, NewPN); + if (BCI == &CI) + RetVal = I; + } + } } } - return replaceInstUsesWith(CI, NewPNodes[PN]); + return RetVal; } Instruction *InstCombiner::visitBitCast(BitCastInst &CI) { @@ -2310,7 +2338,8 @@ Instruction *InstCombiner::visitBitCast(BitCastInst &CI) { // If we found a path from the src to dest, create the getelementptr now. if (SrcElTy == DstElTy) { SmallVector<Value *, 8> Idxs(NumZeros + 1, Builder.getInt32(0)); - return GetElementPtrInst::CreateInBounds(Src, Idxs); + return GetElementPtrInst::CreateInBounds(SrcPTy->getElementType(), Src, + Idxs); } } @@ -2355,11 +2384,10 @@ Instruction *InstCombiner::visitBitCast(BitCastInst &CI) { } // Otherwise, see if our source is an insert. If so, then use the scalar - // component directly. - if (InsertElementInst *IEI = - dyn_cast<InsertElementInst>(CI.getOperand(0))) - return CastInst::Create(Instruction::BitCast, IEI->getOperand(1), - DestTy); + // component directly: + // bitcast (inselt <1 x elt> V, X, 0) to <n x m> --> bitcast X to <n x m> + if (auto *InsElt = dyn_cast<InsertElementInst>(Src)) + return new BitCastInst(InsElt->getOperand(1), DestTy); } } diff --git a/lib/Transforms/InstCombine/InstCombineCompares.cpp b/lib/Transforms/InstCombine/InstCombineCompares.cpp index b5bbb09935e27..3a4283ae54066 100644 --- a/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ b/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -1,9 +1,8 @@ //===- InstCombineCompares.cpp --------------------------------------------===// // -// 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 // //===----------------------------------------------------------------------===// // @@ -704,7 +703,10 @@ static Value *rewriteGEPAsOffset(Value *Start, Value *Base, continue; if (auto *CI = dyn_cast<CastInst>(Val)) { - NewInsts[CI] = NewInsts[CI->getOperand(0)]; + // Don't get rid of the intermediate variable here; the store can grow + // the map which will invalidate the reference to the input value. + Value *V = NewInsts[CI->getOperand(0)]; + NewInsts[CI] = V; continue; } if (auto *GEP = dyn_cast<GEPOperator>(Val)) { @@ -1292,8 +1294,8 @@ static Instruction *processUGT_ADDCST_ADD(ICmpInst &I, Value *A, Value *B, // use the sadd_with_overflow intrinsic to efficiently compute both the // result and the overflow bit. Type *NewType = IntegerType::get(OrigAdd->getContext(), NewWidth); - Value *F = Intrinsic::getDeclaration(I.getModule(), - Intrinsic::sadd_with_overflow, NewType); + Function *F = Intrinsic::getDeclaration( + I.getModule(), Intrinsic::sadd_with_overflow, NewType); InstCombiner::BuilderTy &Builder = IC.Builder; @@ -1315,14 +1317,16 @@ static Instruction *processUGT_ADDCST_ADD(ICmpInst &I, Value *A, Value *B, return ExtractValueInst::Create(Call, 1, "sadd.overflow"); } -// Handle (icmp sgt smin(PosA, B) 0) -> (icmp sgt B 0) +// Handle icmp pred X, 0 Instruction *InstCombiner::foldICmpWithZero(ICmpInst &Cmp) { CmpInst::Predicate Pred = Cmp.getPredicate(); - Value *X = Cmp.getOperand(0); + if (!match(Cmp.getOperand(1), m_Zero())) + return nullptr; - if (match(Cmp.getOperand(1), m_Zero()) && Pred == ICmpInst::ICMP_SGT) { + // (icmp sgt smin(PosA, B) 0) -> (icmp sgt B 0) + if (Pred == ICmpInst::ICMP_SGT) { Value *A, *B; - SelectPatternResult SPR = matchSelectPattern(X, A, B); + SelectPatternResult SPR = matchSelectPattern(Cmp.getOperand(0), A, B); if (SPR.Flavor == SPF_SMIN) { if (isKnownPositive(A, DL, 0, &AC, &Cmp, &DT)) return new ICmpInst(Pred, B, Cmp.getOperand(1)); @@ -1330,6 +1334,20 @@ Instruction *InstCombiner::foldICmpWithZero(ICmpInst &Cmp) { return new ICmpInst(Pred, A, Cmp.getOperand(1)); } } + + // Given: + // icmp eq/ne (urem %x, %y), 0 + // Iff %x has 0 or 1 bits set, and %y has at least 2 bits set, omit 'urem': + // icmp eq/ne %x, 0 + Value *X, *Y; + if (match(Cmp.getOperand(0), m_URem(m_Value(X), m_Value(Y))) && + ICmpInst::isEquality(Pred)) { + KnownBits XKnown = computeKnownBits(X, 0, &Cmp); + KnownBits YKnown = computeKnownBits(Y, 0, &Cmp); + if (XKnown.countMaxPopulation() == 1 && YKnown.countMinPopulation() >= 2) + return new ICmpInst(Pred, X, Cmp.getOperand(1)); + } + return nullptr; } @@ -1624,20 +1642,43 @@ Instruction *InstCombiner::foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And, Instruction *InstCombiner::foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And, const APInt &C1) { + bool isICMP_NE = Cmp.getPredicate() == ICmpInst::ICMP_NE; + // For vectors: icmp ne (and X, 1), 0 --> trunc X to N x i1 // TODO: We canonicalize to the longer form for scalars because we have // better analysis/folds for icmp, and codegen may be better with icmp. - if (Cmp.getPredicate() == CmpInst::ICMP_NE && Cmp.getType()->isVectorTy() && - C1.isNullValue() && match(And->getOperand(1), m_One())) + if (isICMP_NE && Cmp.getType()->isVectorTy() && C1.isNullValue() && + match(And->getOperand(1), m_One())) return new TruncInst(And->getOperand(0), Cmp.getType()); const APInt *C2; - if (!match(And->getOperand(1), m_APInt(C2))) + Value *X; + if (!match(And, m_And(m_Value(X), m_APInt(C2)))) return nullptr; + // Don't perform the following transforms if the AND has multiple uses if (!And->hasOneUse()) return nullptr; + if (Cmp.isEquality() && C1.isNullValue()) { + // Restrict this fold to single-use 'and' (PR10267). + // Replace (and X, (1 << size(X)-1) != 0) with X s< 0 + if (C2->isSignMask()) { + Constant *Zero = Constant::getNullValue(X->getType()); + auto NewPred = isICMP_NE ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_SGE; + return new ICmpInst(NewPred, X, Zero); + } + + // Restrict this fold only for single-use 'and' (PR10267). + // ((%x & C) == 0) --> %x u< (-C) iff (-C) is power of two. + if ((~(*C2) + 1).isPowerOf2()) { + Constant *NegBOC = + ConstantExpr::getNeg(cast<Constant>(And->getOperand(1))); + auto NewPred = isICMP_NE ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_ULT; + return new ICmpInst(NewPred, X, NegBOC); + } + } + // If the LHS is an 'and' of a truncate and we can widen the and/compare to // the input width without changing the value produced, eliminate the cast: // @@ -1772,13 +1813,22 @@ Instruction *InstCombiner::foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or, ConstantInt::get(V->getType(), 1)); } - // X | C == C --> X <=u C - // X | C != C --> X >u C - // iff C+1 is a power of 2 (C is a bitmask of the low bits) - if (Cmp.isEquality() && Cmp.getOperand(1) == Or->getOperand(1) && - (C + 1).isPowerOf2()) { - Pred = (Pred == CmpInst::ICMP_EQ) ? CmpInst::ICMP_ULE : CmpInst::ICMP_UGT; - return new ICmpInst(Pred, Or->getOperand(0), Or->getOperand(1)); + Value *OrOp0 = Or->getOperand(0), *OrOp1 = Or->getOperand(1); + if (Cmp.isEquality() && Cmp.getOperand(1) == OrOp1) { + // X | C == C --> X <=u C + // X | C != C --> X >u C + // iff C+1 is a power of 2 (C is a bitmask of the low bits) + if ((C + 1).isPowerOf2()) { + Pred = (Pred == CmpInst::ICMP_EQ) ? CmpInst::ICMP_ULE : CmpInst::ICMP_UGT; + return new ICmpInst(Pred, OrOp0, OrOp1); + } + // More general: are all bits outside of a mask constant set or not set? + // X | C == C --> (X & ~C) == 0 + // X | C != C --> (X & ~C) != 0 + if (Or->hasOneUse()) { + Value *A = Builder.CreateAnd(OrOp0, ~C); + return new ICmpInst(Pred, A, ConstantInt::getNullValue(OrOp0->getType())); + } } if (!Cmp.isEquality() || !C.isNullValue() || !Or->hasOneUse()) @@ -1799,8 +1849,8 @@ Instruction *InstCombiner::foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or, // Are we using xors to bitwise check for a pair of (in)equalities? Convert to // a shorter form that has more potential to be folded even further. Value *X1, *X2, *X3, *X4; - if (match(Or->getOperand(0), m_OneUse(m_Xor(m_Value(X1), m_Value(X2)))) && - match(Or->getOperand(1), m_OneUse(m_Xor(m_Value(X3), m_Value(X4))))) { + if (match(OrOp0, m_OneUse(m_Xor(m_Value(X1), m_Value(X2)))) && + match(OrOp1, m_OneUse(m_Xor(m_Value(X3), m_Value(X4))))) { // ((X1 ^ X2) || (X3 ^ X4)) == 0 --> (X1 == X2) && (X3 == X4) // ((X1 ^ X2) || (X3 ^ X4)) != 0 --> (X1 != X2) || (X3 != X4) Value *Cmp12 = Builder.CreateICmp(Pred, X1, X2); @@ -1994,6 +2044,27 @@ Instruction *InstCombiner::foldICmpShlConstant(ICmpInst &Cmp, And, Constant::getNullValue(ShType)); } + // Simplify 'shl' inequality test into 'and' equality test. + if (Cmp.isUnsigned() && Shl->hasOneUse()) { + // (X l<< C2) u<=/u> C1 iff C1+1 is power of two -> X & (~C1 l>> C2) ==/!= 0 + if ((C + 1).isPowerOf2() && + (Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_UGT)) { + Value *And = Builder.CreateAnd(X, (~C).lshr(ShiftAmt->getZExtValue())); + return new ICmpInst(Pred == ICmpInst::ICMP_ULE ? ICmpInst::ICMP_EQ + : ICmpInst::ICMP_NE, + And, Constant::getNullValue(ShType)); + } + // (X l<< C2) u</u>= C1 iff C1 is power of two -> X & (-C1 l>> C2) ==/!= 0 + if (C.isPowerOf2() && + (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_UGE)) { + Value *And = + Builder.CreateAnd(X, (~(C - 1)).lshr(ShiftAmt->getZExtValue())); + return new ICmpInst(Pred == ICmpInst::ICMP_ULT ? ICmpInst::ICMP_EQ + : ICmpInst::ICMP_NE, + And, Constant::getNullValue(ShType)); + } + } + // Transform (icmp pred iM (shl iM %v, N), C) // -> (icmp pred i(M-N) (trunc %v iM to i(M-N)), (trunc (C>>N)) // Transform the shl to a trunc if (trunc (C>>N)) has no loss and M-N. @@ -2313,6 +2384,16 @@ Instruction *InstCombiner::foldICmpSubConstant(ICmpInst &Cmp, const APInt &C) { Value *X = Sub->getOperand(0), *Y = Sub->getOperand(1); ICmpInst::Predicate Pred = Cmp.getPredicate(); + const APInt *C2; + APInt SubResult; + + // (icmp P (sub nuw|nsw C2, Y), C) -> (icmp swap(P) Y, C2-C) + if (match(X, m_APInt(C2)) && + ((Cmp.isUnsigned() && Sub->hasNoUnsignedWrap()) || + (Cmp.isSigned() && Sub->hasNoSignedWrap())) && + !subWithOverflow(SubResult, *C2, C, Cmp.isSigned())) + return new ICmpInst(Cmp.getSwappedPredicate(), Y, + ConstantInt::get(Y->getType(), SubResult)); // The following transforms are only worth it if the only user of the subtract // is the icmp. @@ -2337,7 +2418,6 @@ Instruction *InstCombiner::foldICmpSubConstant(ICmpInst &Cmp, return new ICmpInst(ICmpInst::ICMP_SLE, X, Y); } - const APInt *C2; if (!match(X, m_APInt(C2))) return nullptr; @@ -2482,20 +2562,76 @@ Instruction *InstCombiner::foldICmpSelectConstant(ICmpInst &Cmp, // the entire original Cmp can be simplified to a false. Value *Cond = Builder.getFalse(); if (TrueWhenLessThan) - Cond = Builder.CreateOr(Cond, Builder.CreateICmp(ICmpInst::ICMP_SLT, OrigLHS, OrigRHS)); + Cond = Builder.CreateOr(Cond, Builder.CreateICmp(ICmpInst::ICMP_SLT, + OrigLHS, OrigRHS)); if (TrueWhenEqual) - Cond = Builder.CreateOr(Cond, Builder.CreateICmp(ICmpInst::ICMP_EQ, OrigLHS, OrigRHS)); + Cond = Builder.CreateOr(Cond, Builder.CreateICmp(ICmpInst::ICMP_EQ, + OrigLHS, OrigRHS)); if (TrueWhenGreaterThan) - Cond = Builder.CreateOr(Cond, Builder.CreateICmp(ICmpInst::ICMP_SGT, OrigLHS, OrigRHS)); + Cond = Builder.CreateOr(Cond, Builder.CreateICmp(ICmpInst::ICMP_SGT, + OrigLHS, OrigRHS)); return replaceInstUsesWith(Cmp, Cond); } return nullptr; } -Instruction *InstCombiner::foldICmpBitCastConstant(ICmpInst &Cmp, - BitCastInst *Bitcast, - const APInt &C) { +static Instruction *foldICmpBitCast(ICmpInst &Cmp, + InstCombiner::BuilderTy &Builder) { + auto *Bitcast = dyn_cast<BitCastInst>(Cmp.getOperand(0)); + if (!Bitcast) + return nullptr; + + ICmpInst::Predicate Pred = Cmp.getPredicate(); + Value *Op1 = Cmp.getOperand(1); + Value *BCSrcOp = Bitcast->getOperand(0); + + // Make sure the bitcast doesn't change the number of vector elements. + if (Bitcast->getSrcTy()->getScalarSizeInBits() == + Bitcast->getDestTy()->getScalarSizeInBits()) { + // Zero-equality and sign-bit checks are preserved through sitofp + bitcast. + Value *X; + if (match(BCSrcOp, m_SIToFP(m_Value(X)))) { + // icmp eq (bitcast (sitofp X)), 0 --> icmp eq X, 0 + // icmp ne (bitcast (sitofp X)), 0 --> icmp ne X, 0 + // icmp slt (bitcast (sitofp X)), 0 --> icmp slt X, 0 + // icmp sgt (bitcast (sitofp X)), 0 --> icmp sgt X, 0 + if ((Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_SLT || + Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_SGT) && + match(Op1, m_Zero())) + return new ICmpInst(Pred, X, ConstantInt::getNullValue(X->getType())); + + // icmp slt (bitcast (sitofp X)), 1 --> icmp slt X, 1 + if (Pred == ICmpInst::ICMP_SLT && match(Op1, m_One())) + return new ICmpInst(Pred, X, ConstantInt::get(X->getType(), 1)); + + // icmp sgt (bitcast (sitofp X)), -1 --> icmp sgt X, -1 + if (Pred == ICmpInst::ICMP_SGT && match(Op1, m_AllOnes())) + return new ICmpInst(Pred, X, + ConstantInt::getAllOnesValue(X->getType())); + } + + // Zero-equality checks are preserved through unsigned floating-point casts: + // icmp eq (bitcast (uitofp X)), 0 --> icmp eq X, 0 + // icmp ne (bitcast (uitofp X)), 0 --> icmp ne X, 0 + if (match(BCSrcOp, m_UIToFP(m_Value(X)))) + if (Cmp.isEquality() && match(Op1, m_Zero())) + return new ICmpInst(Pred, X, ConstantInt::getNullValue(X->getType())); + } + + // Test to see if the operands of the icmp are casted versions of other + // values. If the ptr->ptr cast can be stripped off both arguments, do so. + if (Bitcast->getType()->isPointerTy() && + (isa<Constant>(Op1) || isa<BitCastInst>(Op1))) { + // If operand #1 is a bitcast instruction, it must also be a ptr->ptr cast + // so eliminate it as well. + if (auto *BC2 = dyn_cast<BitCastInst>(Op1)) + Op1 = BC2->getOperand(0); + + Op1 = Builder.CreateBitCast(Op1, BCSrcOp->getType()); + return new ICmpInst(Pred, BCSrcOp, Op1); + } + // Folding: icmp <pred> iN X, C // where X = bitcast <M x iK> (shufflevector <M x iK> %vec, undef, SC)) to iN // and C is a splat of a K-bit pattern @@ -2503,28 +2639,28 @@ Instruction *InstCombiner::foldICmpBitCastConstant(ICmpInst &Cmp, // Into: // %E = extractelement <M x iK> %vec, i32 C' // icmp <pred> iK %E, trunc(C) - if (!Bitcast->getType()->isIntegerTy() || + const APInt *C; + if (!match(Cmp.getOperand(1), m_APInt(C)) || + !Bitcast->getType()->isIntegerTy() || !Bitcast->getSrcTy()->isIntOrIntVectorTy()) return nullptr; - Value *BCIOp = Bitcast->getOperand(0); - Value *Vec = nullptr; // 1st vector arg of the shufflevector - Constant *Mask = nullptr; // Mask arg of the shufflevector - if (match(BCIOp, + Value *Vec; + Constant *Mask; + if (match(BCSrcOp, m_ShuffleVector(m_Value(Vec), m_Undef(), m_Constant(Mask)))) { // Check whether every element of Mask is the same constant if (auto *Elem = dyn_cast_or_null<ConstantInt>(Mask->getSplatValue())) { - auto *VecTy = cast<VectorType>(BCIOp->getType()); + auto *VecTy = cast<VectorType>(BCSrcOp->getType()); auto *EltTy = cast<IntegerType>(VecTy->getElementType()); - auto Pred = Cmp.getPredicate(); - if (C.isSplat(EltTy->getBitWidth())) { + if (C->isSplat(EltTy->getBitWidth())) { // Fold the icmp based on the value of C // If C is M copies of an iK sized bit pattern, // then: // => %E = extractelement <N x iK> %vec, i32 Elem // icmp <pred> iK %SplatVal, <pattern> Value *Extract = Builder.CreateExtractElement(Vec, Elem); - Value *NewC = ConstantInt::get(EltTy, C.trunc(EltTy->getBitWidth())); + Value *NewC = ConstantInt::get(EltTy, C->trunc(EltTy->getBitWidth())); return new ICmpInst(Pred, Extract, NewC); } } @@ -2606,13 +2742,9 @@ Instruction *InstCombiner::foldICmpInstWithConstant(ICmpInst &Cmp) { return I; } - if (auto *BCI = dyn_cast<BitCastInst>(Cmp.getOperand(0))) { - if (Instruction *I = foldICmpBitCastConstant(Cmp, BCI, *C)) + if (auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0))) + if (Instruction *I = foldICmpIntrinsicWithConstant(Cmp, II, *C)) return I; - } - - if (Instruction *I = foldICmpIntrinsicWithConstant(Cmp, *C)) - return I; return nullptr; } @@ -2711,24 +2843,6 @@ Instruction *InstCombiner::foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp, if (C == *BOC && C.isPowerOf2()) return new ICmpInst(isICMP_NE ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE, BO, Constant::getNullValue(RHS->getType())); - - // Don't perform the following transforms if the AND has multiple uses - if (!BO->hasOneUse()) - break; - - // Replace (and X, (1 << size(X)-1) != 0) with x s< 0 - if (BOC->isSignMask()) { - Constant *Zero = Constant::getNullValue(BOp0->getType()); - auto NewPred = isICMP_NE ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_SGE; - return new ICmpInst(NewPred, BOp0, Zero); - } - - // ((X & ~7) == 0) --> X < 8 - if (C.isNullValue() && (~(*BOC) + 1).isPowerOf2()) { - Constant *NegBOC = ConstantExpr::getNeg(cast<Constant>(BOp1)); - auto NewPred = isICMP_NE ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_ULT; - return new ICmpInst(NewPred, BOp0, NegBOC); - } } break; } @@ -2756,14 +2870,10 @@ Instruction *InstCombiner::foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp, return nullptr; } -/// Fold an icmp with LLVM intrinsic and constant operand: icmp Pred II, C. -Instruction *InstCombiner::foldICmpIntrinsicWithConstant(ICmpInst &Cmp, - const APInt &C) { - IntrinsicInst *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0)); - if (!II || !Cmp.isEquality()) - return nullptr; - - // Handle icmp {eq|ne} <intrinsic>, Constant. +/// Fold an equality icmp with LLVM intrinsic and constant operand. +Instruction *InstCombiner::foldICmpEqIntrinsicWithConstant(ICmpInst &Cmp, + IntrinsicInst *II, + const APInt &C) { Type *Ty = II->getType(); unsigned BitWidth = C.getBitWidth(); switch (II->getIntrinsicID()) { @@ -2823,6 +2933,65 @@ Instruction *InstCombiner::foldICmpIntrinsicWithConstant(ICmpInst &Cmp, return nullptr; } +/// Fold an icmp with LLVM intrinsic and constant operand: icmp Pred II, C. +Instruction *InstCombiner::foldICmpIntrinsicWithConstant(ICmpInst &Cmp, + IntrinsicInst *II, + const APInt &C) { + if (Cmp.isEquality()) + return foldICmpEqIntrinsicWithConstant(Cmp, II, C); + + Type *Ty = II->getType(); + unsigned BitWidth = C.getBitWidth(); + switch (II->getIntrinsicID()) { + case Intrinsic::ctlz: { + // ctlz(0bXXXXXXXX) > 3 -> 0bXXXXXXXX < 0b00010000 + if (Cmp.getPredicate() == ICmpInst::ICMP_UGT && C.ult(BitWidth)) { + unsigned Num = C.getLimitedValue(); + APInt Limit = APInt::getOneBitSet(BitWidth, BitWidth - Num - 1); + return CmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_ULT, + II->getArgOperand(0), ConstantInt::get(Ty, Limit)); + } + + // ctlz(0bXXXXXXXX) < 3 -> 0bXXXXXXXX > 0b00011111 + if (Cmp.getPredicate() == ICmpInst::ICMP_ULT && + C.uge(1) && C.ule(BitWidth)) { + unsigned Num = C.getLimitedValue(); + APInt Limit = APInt::getLowBitsSet(BitWidth, BitWidth - Num); + return CmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_UGT, + II->getArgOperand(0), ConstantInt::get(Ty, Limit)); + } + break; + } + case Intrinsic::cttz: { + // Limit to one use to ensure we don't increase instruction count. + if (!II->hasOneUse()) + return nullptr; + + // cttz(0bXXXXXXXX) > 3 -> 0bXXXXXXXX & 0b00001111 == 0 + if (Cmp.getPredicate() == ICmpInst::ICMP_UGT && C.ult(BitWidth)) { + APInt Mask = APInt::getLowBitsSet(BitWidth, C.getLimitedValue() + 1); + return CmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_EQ, + Builder.CreateAnd(II->getArgOperand(0), Mask), + ConstantInt::getNullValue(Ty)); + } + + // cttz(0bXXXXXXXX) < 3 -> 0bXXXXXXXX & 0b00000111 != 0 + if (Cmp.getPredicate() == ICmpInst::ICMP_ULT && + C.uge(1) && C.ule(BitWidth)) { + APInt Mask = APInt::getLowBitsSet(BitWidth, C.getLimitedValue()); + return CmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_NE, + Builder.CreateAnd(II->getArgOperand(0), Mask), + ConstantInt::getNullValue(Ty)); + } + break; + } + default: + break; + } + + return nullptr; +} + /// Handle icmp with constant (but not simple integer constant) RHS. Instruction *InstCombiner::foldICmpInstWithConstantNotInt(ICmpInst &I) { Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); @@ -2983,6 +3152,10 @@ static Value *foldICmpWithLowBitMaskedVal(ICmpInst &I, // x s> x & (-1 >> y) -> x s> (-1 >> y) if (X != I.getOperand(0)) // X must be on LHS of comparison! return nullptr; // Ignore the other case. + if (!match(M, m_Constant())) // Can not do this fold with non-constant. + return nullptr; + if (!match(M, m_NonNegative())) // Must not have any -1 vector elements. + return nullptr; DstPred = ICmpInst::Predicate::ICMP_SGT; break; case ICmpInst::Predicate::ICMP_SGE: @@ -3009,6 +3182,10 @@ static Value *foldICmpWithLowBitMaskedVal(ICmpInst &I, // x s<= x & (-1 >> y) -> x s<= (-1 >> y) if (X != I.getOperand(0)) // X must be on LHS of comparison! return nullptr; // Ignore the other case. + if (!match(M, m_Constant())) // Can not do this fold with non-constant. + return nullptr; + if (!match(M, m_NonNegative())) // Must not have any -1 vector elements. + return nullptr; DstPred = ICmpInst::Predicate::ICMP_SLE; break; default: @@ -3093,6 +3270,64 @@ foldICmpWithTruncSignExtendedVal(ICmpInst &I, return T1; } +// Given pattern: +// icmp eq/ne (and ((x shift Q), (y oppositeshift K))), 0 +// we should move shifts to the same hand of 'and', i.e. rewrite as +// icmp eq/ne (and (x shift (Q+K)), y), 0 iff (Q+K) u< bitwidth(x) +// We are only interested in opposite logical shifts here. +// If we can, we want to end up creating 'lshr' shift. +static Value * +foldShiftIntoShiftInAnotherHandOfAndInICmp(ICmpInst &I, const SimplifyQuery SQ, + InstCombiner::BuilderTy &Builder) { + if (!I.isEquality() || !match(I.getOperand(1), m_Zero()) || + !I.getOperand(0)->hasOneUse()) + return nullptr; + + auto m_AnyLogicalShift = m_LogicalShift(m_Value(), m_Value()); + auto m_AnyLShr = m_LShr(m_Value(), m_Value()); + + // Look for an 'and' of two (opposite) logical shifts. + // Pick the single-use shift as XShift. + Value *XShift, *YShift; + if (!match(I.getOperand(0), + m_c_And(m_OneUse(m_CombineAnd(m_AnyLogicalShift, m_Value(XShift))), + m_CombineAnd(m_AnyLogicalShift, m_Value(YShift))))) + return nullptr; + + // If YShift is a single-use 'lshr', swap the shifts around. + if (match(YShift, m_OneUse(m_AnyLShr))) + std::swap(XShift, YShift); + + // The shifts must be in opposite directions. + Instruction::BinaryOps XShiftOpcode = + cast<BinaryOperator>(XShift)->getOpcode(); + if (XShiftOpcode == cast<BinaryOperator>(YShift)->getOpcode()) + return nullptr; // Do not care about same-direction shifts here. + + Value *X, *XShAmt, *Y, *YShAmt; + match(XShift, m_BinOp(m_Value(X), m_Value(XShAmt))); + match(YShift, m_BinOp(m_Value(Y), m_Value(YShAmt))); + + // Can we fold (XShAmt+YShAmt) ? + Value *NewShAmt = SimplifyBinOp(Instruction::BinaryOps::Add, XShAmt, YShAmt, + SQ.getWithInstruction(&I)); + if (!NewShAmt) + return nullptr; + // Is the new shift amount smaller than the bit width? + // FIXME: could also rely on ConstantRange. + unsigned BitWidth = X->getType()->getScalarSizeInBits(); + if (!match(NewShAmt, m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULT, + APInt(BitWidth, BitWidth)))) + return nullptr; + // All good, we can do this fold. The shift is the same that was for X. + Value *T0 = XShiftOpcode == Instruction::BinaryOps::LShr + ? Builder.CreateLShr(X, NewShAmt) + : Builder.CreateShl(X, NewShAmt); + Value *T1 = Builder.CreateAnd(T0, Y); + return Builder.CreateICmp(I.getPredicate(), T1, + Constant::getNullValue(X->getType())); +} + /// Try to fold icmp (binop), X or icmp X, (binop). /// TODO: A large part of this logic is duplicated in InstSimplify's /// simplifyICmpWithBinOp(). We should be able to share that and avoid the code @@ -3448,6 +3683,9 @@ Instruction *InstCombiner::foldICmpBinOp(ICmpInst &I) { if (Value *V = foldICmpWithTruncSignExtendedVal(I, Builder)) return replaceInstUsesWith(I, V); + if (Value *V = foldShiftIntoShiftInAnotherHandOfAndInICmp(I, SQ, Builder)) + return replaceInstUsesWith(I, V); + return nullptr; } @@ -3688,6 +3926,30 @@ Instruction *InstCombiner::foldICmpEquality(ICmpInst &I) { match(Op1, m_BitReverse(m_Value(B))))) return new ICmpInst(Pred, A, B); + // Canonicalize checking for a power-of-2-or-zero value: + // (A & (A-1)) == 0 --> ctpop(A) < 2 (two commuted variants) + // ((A-1) & A) != 0 --> ctpop(A) > 1 (two commuted variants) + if (!match(Op0, m_OneUse(m_c_And(m_Add(m_Value(A), m_AllOnes()), + m_Deferred(A)))) || + !match(Op1, m_ZeroInt())) + A = nullptr; + + // (A & -A) == A --> ctpop(A) < 2 (four commuted variants) + // (-A & A) != A --> ctpop(A) > 1 (four commuted variants) + if (match(Op0, m_OneUse(m_c_And(m_Neg(m_Specific(Op1)), m_Specific(Op1))))) + A = Op1; + else if (match(Op1, + m_OneUse(m_c_And(m_Neg(m_Specific(Op0)), m_Specific(Op0))))) + A = Op0; + + if (A) { + Type *Ty = A->getType(); + CallInst *CtPop = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, A); + return Pred == ICmpInst::ICMP_EQ + ? new ICmpInst(ICmpInst::ICMP_ULT, CtPop, ConstantInt::get(Ty, 2)) + : new ICmpInst(ICmpInst::ICMP_UGT, CtPop, ConstantInt::get(Ty, 1)); + } + return nullptr; } @@ -3698,7 +3960,6 @@ Instruction *InstCombiner::foldICmpWithCastAndCast(ICmpInst &ICmp) { Value *LHSCIOp = LHSCI->getOperand(0); Type *SrcTy = LHSCIOp->getType(); Type *DestTy = LHSCI->getType(); - Value *RHSCIOp; // Turn icmp (ptrtoint x), (ptrtoint/c) into a compare of the input if the // integer type is the same size as the pointer type. @@ -3740,7 +4001,7 @@ Instruction *InstCombiner::foldICmpWithCastAndCast(ICmpInst &ICmp) { if (auto *CI = dyn_cast<CastInst>(ICmp.getOperand(1))) { // Not an extension from the same type? - RHSCIOp = CI->getOperand(0); + Value *RHSCIOp = CI->getOperand(0); if (RHSCIOp->getType() != LHSCIOp->getType()) return nullptr; @@ -3813,104 +4074,83 @@ Instruction *InstCombiner::foldICmpWithCastAndCast(ICmpInst &ICmp) { return BinaryOperator::CreateNot(Result); } -bool InstCombiner::OptimizeOverflowCheck(OverflowCheckFlavor OCF, Value *LHS, - Value *RHS, Instruction &OrigI, - Value *&Result, Constant *&Overflow) { +static bool isNeutralValue(Instruction::BinaryOps BinaryOp, Value *RHS) { + switch (BinaryOp) { + default: + llvm_unreachable("Unsupported binary op"); + case Instruction::Add: + case Instruction::Sub: + return match(RHS, m_Zero()); + case Instruction::Mul: + return match(RHS, m_One()); + } +} + +OverflowResult InstCombiner::computeOverflow( + Instruction::BinaryOps BinaryOp, bool IsSigned, + Value *LHS, Value *RHS, Instruction *CxtI) const { + switch (BinaryOp) { + default: + llvm_unreachable("Unsupported binary op"); + case Instruction::Add: + if (IsSigned) + return computeOverflowForSignedAdd(LHS, RHS, CxtI); + else + return computeOverflowForUnsignedAdd(LHS, RHS, CxtI); + case Instruction::Sub: + if (IsSigned) + return computeOverflowForSignedSub(LHS, RHS, CxtI); + else + return computeOverflowForUnsignedSub(LHS, RHS, CxtI); + case Instruction::Mul: + if (IsSigned) + return computeOverflowForSignedMul(LHS, RHS, CxtI); + else + return computeOverflowForUnsignedMul(LHS, RHS, CxtI); + } +} + +bool InstCombiner::OptimizeOverflowCheck( + Instruction::BinaryOps BinaryOp, bool IsSigned, Value *LHS, Value *RHS, + Instruction &OrigI, Value *&Result, Constant *&Overflow) { if (OrigI.isCommutative() && isa<Constant>(LHS) && !isa<Constant>(RHS)) std::swap(LHS, RHS); - auto SetResult = [&](Value *OpResult, Constant *OverflowVal, bool ReuseName) { - Result = OpResult; - Overflow = OverflowVal; - if (ReuseName) - Result->takeName(&OrigI); - return true; - }; - // If the overflow check was an add followed by a compare, the insertion point // may be pointing to the compare. We want to insert the new instructions // before the add in case there are uses of the add between the add and the // compare. Builder.SetInsertPoint(&OrigI); - switch (OCF) { - case OCF_INVALID: - llvm_unreachable("bad overflow check kind!"); - - case OCF_UNSIGNED_ADD: { - OverflowResult OR = computeOverflowForUnsignedAdd(LHS, RHS, &OrigI); - if (OR == OverflowResult::NeverOverflows) - return SetResult(Builder.CreateNUWAdd(LHS, RHS), Builder.getFalse(), - true); - - if (OR == OverflowResult::AlwaysOverflows) - return SetResult(Builder.CreateAdd(LHS, RHS), Builder.getTrue(), true); - - // Fall through uadd into sadd - LLVM_FALLTHROUGH; - } - case OCF_SIGNED_ADD: { - // X + 0 -> {X, false} - if (match(RHS, m_Zero())) - return SetResult(LHS, Builder.getFalse(), false); - - // We can strength reduce this signed add into a regular add if we can prove - // that it will never overflow. - if (OCF == OCF_SIGNED_ADD) - if (willNotOverflowSignedAdd(LHS, RHS, OrigI)) - return SetResult(Builder.CreateNSWAdd(LHS, RHS), Builder.getFalse(), - true); - break; - } - - case OCF_UNSIGNED_SUB: - case OCF_SIGNED_SUB: { - // X - 0 -> {X, false} - if (match(RHS, m_Zero())) - return SetResult(LHS, Builder.getFalse(), false); - - if (OCF == OCF_SIGNED_SUB) { - if (willNotOverflowSignedSub(LHS, RHS, OrigI)) - return SetResult(Builder.CreateNSWSub(LHS, RHS), Builder.getFalse(), - true); - } else { - if (willNotOverflowUnsignedSub(LHS, RHS, OrigI)) - return SetResult(Builder.CreateNUWSub(LHS, RHS), Builder.getFalse(), - true); - } - break; - } - - case OCF_UNSIGNED_MUL: { - OverflowResult OR = computeOverflowForUnsignedMul(LHS, RHS, &OrigI); - if (OR == OverflowResult::NeverOverflows) - return SetResult(Builder.CreateNUWMul(LHS, RHS), Builder.getFalse(), - true); - if (OR == OverflowResult::AlwaysOverflows) - return SetResult(Builder.CreateMul(LHS, RHS), Builder.getTrue(), true); - LLVM_FALLTHROUGH; + if (isNeutralValue(BinaryOp, RHS)) { + Result = LHS; + Overflow = Builder.getFalse(); + return true; } - case OCF_SIGNED_MUL: - // X * undef -> undef - if (isa<UndefValue>(RHS)) - return SetResult(RHS, UndefValue::get(Builder.getInt1Ty()), false); - - // X * 0 -> {0, false} - if (match(RHS, m_Zero())) - return SetResult(RHS, Builder.getFalse(), false); - // X * 1 -> {X, false} - if (match(RHS, m_One())) - return SetResult(LHS, Builder.getFalse(), false); - - if (OCF == OCF_SIGNED_MUL) - if (willNotOverflowSignedMul(LHS, RHS, OrigI)) - return SetResult(Builder.CreateNSWMul(LHS, RHS), Builder.getFalse(), - true); - break; + switch (computeOverflow(BinaryOp, IsSigned, LHS, RHS, &OrigI)) { + case OverflowResult::MayOverflow: + return false; + case OverflowResult::AlwaysOverflowsLow: + case OverflowResult::AlwaysOverflowsHigh: + Result = Builder.CreateBinOp(BinaryOp, LHS, RHS); + Result->takeName(&OrigI); + Overflow = Builder.getTrue(); + return true; + case OverflowResult::NeverOverflows: + Result = Builder.CreateBinOp(BinaryOp, LHS, RHS); + Result->takeName(&OrigI); + Overflow = Builder.getFalse(); + if (auto *Inst = dyn_cast<Instruction>(Result)) { + if (IsSigned) + Inst->setHasNoSignedWrap(); + else + Inst->setHasNoUnsignedWrap(); + } + return true; } - return false; + llvm_unreachable("Unexpected overflow result"); } /// Recognize and process idiom involving test for multiplication @@ -4084,8 +4324,8 @@ static Instruction *processUMulZExtIdiom(ICmpInst &I, Value *MulVal, MulA = Builder.CreateZExt(A, MulType); if (WidthB < MulWidth) MulB = Builder.CreateZExt(B, MulType); - Value *F = Intrinsic::getDeclaration(I.getModule(), - Intrinsic::umul_with_overflow, MulType); + Function *F = Intrinsic::getDeclaration( + I.getModule(), Intrinsic::umul_with_overflow, MulType); CallInst *Call = Builder.CreateCall(F, {MulA, MulB}, "umul"); IC.Worklist.Add(MulInstr); @@ -4881,61 +5121,8 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) { return New; } - // Zero-equality and sign-bit checks are preserved through sitofp + bitcast. - Value *X; - if (match(Op0, m_BitCast(m_SIToFP(m_Value(X))))) { - // icmp eq (bitcast (sitofp X)), 0 --> icmp eq X, 0 - // icmp ne (bitcast (sitofp X)), 0 --> icmp ne X, 0 - // icmp slt (bitcast (sitofp X)), 0 --> icmp slt X, 0 - // icmp sgt (bitcast (sitofp X)), 0 --> icmp sgt X, 0 - if ((Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_SLT || - Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_SGT) && - match(Op1, m_Zero())) - return new ICmpInst(Pred, X, ConstantInt::getNullValue(X->getType())); - - // icmp slt (bitcast (sitofp X)), 1 --> icmp slt X, 1 - if (Pred == ICmpInst::ICMP_SLT && match(Op1, m_One())) - return new ICmpInst(Pred, X, ConstantInt::get(X->getType(), 1)); - - // icmp sgt (bitcast (sitofp X)), -1 --> icmp sgt X, -1 - if (Pred == ICmpInst::ICMP_SGT && match(Op1, m_AllOnes())) - return new ICmpInst(Pred, X, ConstantInt::getAllOnesValue(X->getType())); - } - - // Zero-equality checks are preserved through unsigned floating-point casts: - // icmp eq (bitcast (uitofp X)), 0 --> icmp eq X, 0 - // icmp ne (bitcast (uitofp X)), 0 --> icmp ne X, 0 - if (match(Op0, m_BitCast(m_UIToFP(m_Value(X))))) - if (I.isEquality() && match(Op1, m_Zero())) - return new ICmpInst(Pred, X, ConstantInt::getNullValue(X->getType())); - - // Test to see if the operands of the icmp are casted versions of other - // values. If the ptr->ptr cast can be stripped off both arguments, we do so - // now. - if (BitCastInst *CI = dyn_cast<BitCastInst>(Op0)) { - if (Op0->getType()->isPointerTy() && - (isa<Constant>(Op1) || isa<BitCastInst>(Op1))) { - // We keep moving the cast from the left operand over to the right - // operand, where it can often be eliminated completely. - Op0 = CI->getOperand(0); - - // If operand #1 is a bitcast instruction, it must also be a ptr->ptr cast - // so eliminate it as well. - if (BitCastInst *CI2 = dyn_cast<BitCastInst>(Op1)) - Op1 = CI2->getOperand(0); - - // If Op1 is a constant, we can fold the cast into the constant. - if (Op0->getType() != Op1->getType()) { - if (Constant *Op1C = dyn_cast<Constant>(Op1)) { - Op1 = ConstantExpr::getBitCast(Op1C, Op0->getType()); - } else { - // Otherwise, cast the RHS right before the icmp - Op1 = Builder.CreateBitCast(Op1, Op0->getType()); - } - } - return new ICmpInst(I.getPredicate(), Op0, Op1); - } - } + if (Instruction *Res = foldICmpBitCast(I, Builder)) + return Res; if (isa<CastInst>(Op0)) { // Handle the special case of: icmp (cast bool to X), <cst> @@ -4984,8 +5171,8 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) { isa<IntegerType>(A->getType())) { Value *Result; Constant *Overflow; - if (OptimizeOverflowCheck(OCF_UNSIGNED_ADD, A, B, *AddI, Result, - Overflow)) { + if (OptimizeOverflowCheck(Instruction::Add, /*Signed*/false, A, B, + *AddI, Result, Overflow)) { replaceInstUsesWith(*AddI, Result); return replaceInstUsesWith(I, Overflow); } @@ -5411,6 +5598,8 @@ Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) { return replaceInstUsesWith(I, V); // Simplify 'fcmp pred X, X' + Type *OpType = Op0->getType(); + assert(OpType == Op1->getType() && "fcmp with different-typed operands?"); if (Op0 == Op1) { switch (Pred) { default: break; @@ -5420,7 +5609,7 @@ Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) { case FCmpInst::FCMP_UNE: // True if unordered or not equal // Canonicalize these to be 'fcmp uno %X, 0.0'. I.setPredicate(FCmpInst::FCMP_UNO); - I.setOperand(1, Constant::getNullValue(Op0->getType())); + I.setOperand(1, Constant::getNullValue(OpType)); return &I; case FCmpInst::FCMP_ORD: // True if ordered (no nans) @@ -5429,7 +5618,7 @@ Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) { case FCmpInst::FCMP_OLE: // True if ordered and less than or equal // Canonicalize these to be 'fcmp ord %X, 0.0'. I.setPredicate(FCmpInst::FCMP_ORD); - I.setOperand(1, Constant::getNullValue(Op0->getType())); + I.setOperand(1, Constant::getNullValue(OpType)); return &I; } } @@ -5438,15 +5627,20 @@ Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) { // then canonicalize the operand to 0.0. if (Pred == CmpInst::FCMP_ORD || Pred == CmpInst::FCMP_UNO) { if (!match(Op0, m_PosZeroFP()) && isKnownNeverNaN(Op0, &TLI)) { - I.setOperand(0, ConstantFP::getNullValue(Op0->getType())); + I.setOperand(0, ConstantFP::getNullValue(OpType)); return &I; } if (!match(Op1, m_PosZeroFP()) && isKnownNeverNaN(Op1, &TLI)) { - I.setOperand(1, ConstantFP::getNullValue(Op0->getType())); + I.setOperand(1, ConstantFP::getNullValue(OpType)); return &I; } } + // fcmp pred (fneg X), (fneg Y) -> fcmp swap(pred) X, Y + Value *X, *Y; + if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_FNeg(m_Value(Y)))) + return new FCmpInst(I.getSwappedPredicate(), X, Y, "", &I); + // Test if the FCmpInst instruction is used exclusively by a select as // part of a minimum or maximum operation. If so, refrain from doing // any other folding. This helps out other analyses which understand @@ -5465,7 +5659,7 @@ Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) { // The sign of 0.0 is ignored by fcmp, so canonicalize to +0.0: // fcmp Pred X, -0.0 --> fcmp Pred X, 0.0 if (match(Op1, m_AnyZeroFP()) && !match(Op1, m_PosZeroFP())) { - I.setOperand(1, ConstantFP::getNullValue(Op1->getType())); + I.setOperand(1, ConstantFP::getNullValue(OpType)); return &I; } @@ -5505,12 +5699,7 @@ Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) { if (Instruction *R = foldFabsWithFcmpZero(I)) return R; - Value *X, *Y; if (match(Op0, m_FNeg(m_Value(X)))) { - // fcmp pred (fneg X), (fneg Y) -> fcmp swap(pred) X, Y - if (match(Op1, m_FNeg(m_Value(Y)))) - return new FCmpInst(I.getSwappedPredicate(), X, Y, "", &I); - // fcmp pred (fneg X), C --> fcmp swap(pred) X, -C Constant *C; if (match(Op1, m_Constant(C))) { diff --git a/lib/Transforms/InstCombine/InstCombineInternal.h b/lib/Transforms/InstCombine/InstCombineInternal.h index 2de41bd5bef5d..434b0d5912157 100644 --- a/lib/Transforms/InstCombine/InstCombineInternal.h +++ b/lib/Transforms/InstCombine/InstCombineInternal.h @@ -1,9 +1,8 @@ //===- InstCombineInternal.h - InstCombine pass internals -------*- 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 // //===----------------------------------------------------------------------===// // @@ -53,13 +52,14 @@ namespace llvm { class APInt; class AssumptionCache; -class CallSite; +class BlockFrequencyInfo; class DataLayout; class DominatorTree; class GEPOperator; class GlobalVariable; class LoopInfo; class OptimizationRemarkEmitter; +class ProfileSummaryInfo; class TargetLibraryInfo; class User; @@ -185,40 +185,6 @@ static inline bool IsFreeToInvert(Value *V, bool WillInvertAllUses) { return false; } -/// Specific patterns of overflow check idioms that we match. -enum OverflowCheckFlavor { - OCF_UNSIGNED_ADD, - OCF_SIGNED_ADD, - OCF_UNSIGNED_SUB, - OCF_SIGNED_SUB, - OCF_UNSIGNED_MUL, - OCF_SIGNED_MUL, - - OCF_INVALID -}; - -/// Returns the OverflowCheckFlavor corresponding to a overflow_with_op -/// intrinsic. -static inline OverflowCheckFlavor -IntrinsicIDToOverflowCheckFlavor(unsigned ID) { - switch (ID) { - default: - return OCF_INVALID; - case Intrinsic::uadd_with_overflow: - return OCF_UNSIGNED_ADD; - case Intrinsic::sadd_with_overflow: - return OCF_SIGNED_ADD; - case Intrinsic::usub_with_overflow: - return OCF_UNSIGNED_SUB; - case Intrinsic::ssub_with_overflow: - return OCF_SIGNED_SUB; - case Intrinsic::umul_with_overflow: - return OCF_UNSIGNED_MUL; - case Intrinsic::smul_with_overflow: - return OCF_SIGNED_MUL; - } -} - /// Some binary operators require special handling to avoid poison and undefined /// behavior. If a constant vector has undef elements, replace those undefs with /// identity constants if possible because those are always safe to execute. @@ -306,6 +272,8 @@ private: const DataLayout &DL; const SimplifyQuery SQ; OptimizationRemarkEmitter &ORE; + BlockFrequencyInfo *BFI; + ProfileSummaryInfo *PSI; // Optional analyses. When non-null, these can both be used to do better // combining and will be updated to reflect any changes. @@ -317,11 +285,11 @@ public: InstCombiner(InstCombineWorklist &Worklist, BuilderTy &Builder, bool MinimizeSize, bool ExpensiveCombines, AliasAnalysis *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT, - OptimizationRemarkEmitter &ORE, const DataLayout &DL, - LoopInfo *LI) + OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, + ProfileSummaryInfo *PSI, const DataLayout &DL, LoopInfo *LI) : Worklist(Worklist), Builder(Builder), MinimizeSize(MinimizeSize), ExpensiveCombines(ExpensiveCombines), AA(AA), AC(AC), TLI(TLI), DT(DT), - DL(DL), SQ(DL, &TLI, &DT, &AC), ORE(ORE), LI(LI) {} + DL(DL), SQ(DL, &TLI, &DT, &AC), ORE(ORE), BFI(BFI), PSI(PSI), LI(LI) {} /// Run the combiner over the entire worklist until it is empty. /// @@ -345,6 +313,7 @@ public: // I - Change was made, I is still valid, I may be dead though // otherwise - Change was made, replace I with returned instruction // + Instruction *visitFNeg(UnaryOperator &I); Instruction *visitAdd(BinaryOperator &I); Instruction *visitFAdd(BinaryOperator &I); Value *OptimizePointerDifference(Value *LHS, Value *RHS, Type *Ty); @@ -394,6 +363,7 @@ public: Instruction *visitSelectInst(SelectInst &SI); Instruction *visitCallInst(CallInst &CI); Instruction *visitInvokeInst(InvokeInst &II); + Instruction *visitCallBrInst(CallBrInst &CBI); Instruction *SliceUpIllegalIntegerPHI(PHINode &PN); Instruction *visitPHINode(PHINode &PN); @@ -403,6 +373,7 @@ public: Instruction *visitFree(CallInst &FI); Instruction *visitLoadInst(LoadInst &LI); Instruction *visitStoreInst(StoreInst &SI); + Instruction *visitAtomicRMWInst(AtomicRMWInst &SI); Instruction *visitBranchInst(BranchInst &BI); Instruction *visitFenceInst(FenceInst &FI); Instruction *visitSwitchInst(SwitchInst &SI); @@ -464,16 +435,22 @@ private: /// operation in OperationResult and result of the overflow check in /// OverflowResult, and return true. If no simplification is possible, /// returns false. - bool OptimizeOverflowCheck(OverflowCheckFlavor OCF, Value *LHS, Value *RHS, + bool OptimizeOverflowCheck(Instruction::BinaryOps BinaryOp, bool IsSigned, + Value *LHS, Value *RHS, Instruction &CtxI, Value *&OperationResult, Constant *&OverflowResult); - Instruction *visitCallSite(CallSite CS); + Instruction *visitCallBase(CallBase &Call); Instruction *tryOptimizeCall(CallInst *CI); - bool transformConstExprCastCall(CallSite CS); - Instruction *transformCallThroughTrampoline(CallSite CS, - IntrinsicInst *Tramp); + bool transformConstExprCastCall(CallBase &Call); + Instruction *transformCallThroughTrampoline(CallBase &Call, + IntrinsicInst &Tramp); + Value *simplifyMaskedLoad(IntrinsicInst &II); + Instruction *simplifyMaskedStore(IntrinsicInst &II); + Instruction *simplifyMaskedGather(IntrinsicInst &II); + Instruction *simplifyMaskedScatter(IntrinsicInst &II); + /// Transform (zext icmp) to bitwise / integer operations in order to /// eliminate it. /// @@ -592,6 +569,8 @@ private: Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D); Value *getSelectCondition(Value *A, Value *B); + Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II); + public: /// Inserts an instruction \p New before instruction \p Old /// @@ -647,6 +626,16 @@ public: return InsertValueInst::Create(Struct, Result, 0); } + /// Create and insert the idiom we use to indicate a block is unreachable + /// without having to rewrite the CFG from within InstCombine. + void CreateNonTerminatorUnreachable(Instruction *InsertAt) { + auto &Ctx = InsertAt->getContext(); + new StoreInst(ConstantInt::getTrue(Ctx), + UndefValue::get(Type::getInt1PtrTy(Ctx)), + InsertAt); + } + + /// Combiner aware instruction erasure. /// /// When dealing with an instruction that has side effects or produces a void @@ -703,7 +692,7 @@ public: } OverflowResult computeOverflowForSignedMul(const Value *LHS, - const Value *RHS, + const Value *RHS, const Instruction *CxtI) const { return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT); } @@ -731,6 +720,10 @@ public: return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT); } + OverflowResult computeOverflow( + Instruction::BinaryOps BinaryOp, bool IsSigned, + Value *LHS, Value *RHS, Instruction *CxtI) const; + /// Maximum size of array considered when transforming. uint64_t MaxArraySizeForCombine; @@ -802,8 +795,7 @@ private: Value *simplifyAMDGCNMemoryIntrinsicDemanded(IntrinsicInst *II, APInt DemandedElts, - int DmaskIdx = -1, - int TFCIdx = -1); + int DmaskIdx = -1); Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts, unsigned Depth = 0); @@ -868,8 +860,6 @@ private: Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select, ConstantInt *C); - Instruction *foldICmpBitCastConstant(ICmpInst &Cmp, BitCastInst *Bitcast, - const APInt &C); Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc, const APInt &C); Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And, @@ -904,7 +894,10 @@ private: Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp, BinaryOperator *BO, const APInt &C); - Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, const APInt &C); + Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II, + const APInt &C); + Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II, + const APInt &C); // Helpers of visitSelectInst(). Instruction *foldSelectExtConst(SelectInst &Sel); diff --git a/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp b/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp index 76ab614090faa..054fb7da09a22 100644 --- a/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp +++ b/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp @@ -1,9 +1,8 @@ //===- InstCombineLoadStoreAlloca.cpp -------------------------------------===// // -// 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 // //===----------------------------------------------------------------------===// // @@ -89,29 +88,29 @@ isOnlyCopiedFromConstantGlobal(Value *V, MemTransferInst *&TheCopy, continue; } - if (auto CS = CallSite(I)) { + if (auto *Call = dyn_cast<CallBase>(I)) { // If this is the function being called then we treat it like a load and // ignore it. - if (CS.isCallee(&U)) + if (Call->isCallee(&U)) continue; - unsigned DataOpNo = CS.getDataOperandNo(&U); - bool IsArgOperand = CS.isArgOperand(&U); + unsigned DataOpNo = Call->getDataOperandNo(&U); + bool IsArgOperand = Call->isArgOperand(&U); // Inalloca arguments are clobbered by the call. - if (IsArgOperand && CS.isInAllocaArgument(DataOpNo)) + if (IsArgOperand && Call->isInAllocaArgument(DataOpNo)) return false; // If this is a readonly/readnone call site, then we know it is just a // load (but one that potentially returns the value itself), so we can // ignore it if we know that the value isn't captured. - if (CS.onlyReadsMemory() && - (CS.getInstruction()->use_empty() || CS.doesNotCapture(DataOpNo))) + if (Call->onlyReadsMemory() && + (Call->use_empty() || Call->doesNotCapture(DataOpNo))) continue; // If this is being passed as a byval argument, the caller is making a // copy, so it is only a read of the alloca. - if (IsArgOperand && CS.isByValArgument(DataOpNo)) + if (IsArgOperand && Call->isByValArgument(DataOpNo)) continue; } @@ -213,8 +212,8 @@ static Instruction *simplifyAllocaArraySize(InstCombiner &IC, AllocaInst &AI) { Type *IdxTy = IC.getDataLayout().getIntPtrType(AI.getType()); Value *NullIdx = Constant::getNullValue(IdxTy); Value *Idx[2] = {NullIdx, NullIdx}; - Instruction *GEP = - GetElementPtrInst::CreateInBounds(New, Idx, New->getName() + ".sub"); + Instruction *GEP = GetElementPtrInst::CreateInBounds( + NewTy, New, Idx, New->getName() + ".sub"); IC.InsertNewInstBefore(GEP, *It); // Now make everything use the getelementptr instead of the original @@ -299,7 +298,7 @@ void PointerReplacer::replace(Instruction *I) { if (auto *LT = dyn_cast<LoadInst>(I)) { auto *V = getReplacement(LT->getPointerOperand()); assert(V && "Operand not replaced"); - auto *NewI = new LoadInst(V); + auto *NewI = new LoadInst(I->getType(), V); NewI->takeName(LT); IC.InsertNewInstWith(NewI, *LT); IC.replaceInstUsesWith(*LT, NewI); @@ -466,7 +465,7 @@ static LoadInst *combineLoadToNewType(InstCombiner &IC, LoadInst &LI, Type *NewT NewPtr = IC.Builder.CreateBitCast(Ptr, NewTy->getPointerTo(AS)); LoadInst *NewLoad = IC.Builder.CreateAlignedLoad( - NewPtr, LI.getAlignment(), LI.isVolatile(), LI.getName() + Suffix); + NewTy, NewPtr, LI.getAlignment(), LI.isVolatile(), LI.getName() + Suffix); NewLoad->setAtomic(LI.getOrdering(), LI.getSyncScopeID()); MDBuilder MDB(NewLoad->getContext()); for (const auto &MDPair : MD) { @@ -631,7 +630,7 @@ static Instruction *combineLoadToOperationType(InstCombiner &IC, LoadInst &LI) { // infinite loop). if (!Ty->isIntegerTy() && Ty->isSized() && DL.isLegalInteger(DL.getTypeStoreSizeInBits(Ty)) && - DL.getTypeStoreSizeInBits(Ty) == DL.getTypeSizeInBits(Ty) && + DL.typeSizeEqualsStoreSize(Ty) && !DL.isNonIntegralPointerType(Ty) && !isMinMaxWithLoads( peekThroughBitcast(LI.getPointerOperand(), /*OneUseOnly=*/true))) { @@ -725,7 +724,8 @@ static Instruction *unpackLoadToAggregate(InstCombiner &IC, LoadInst &LI) { auto *Ptr = IC.Builder.CreateInBoundsGEP(ST, Addr, makeArrayRef(Indices), Name + ".elt"); auto EltAlign = MinAlign(Align, SL->getElementOffset(i)); - auto *L = IC.Builder.CreateAlignedLoad(Ptr, EltAlign, Name + ".unpack"); + auto *L = IC.Builder.CreateAlignedLoad(ST->getElementType(i), Ptr, + EltAlign, Name + ".unpack"); // Propagate AA metadata. It'll still be valid on the narrowed load. AAMDNodes AAMD; LI.getAAMetadata(AAMD); @@ -775,8 +775,8 @@ static Instruction *unpackLoadToAggregate(InstCombiner &IC, LoadInst &LI) { }; auto *Ptr = IC.Builder.CreateInBoundsGEP(AT, Addr, makeArrayRef(Indices), Name + ".elt"); - auto *L = IC.Builder.CreateAlignedLoad(Ptr, MinAlign(Align, Offset), - Name + ".unpack"); + auto *L = IC.Builder.CreateAlignedLoad( + AT->getElementType(), Ptr, MinAlign(Align, Offset), Name + ".unpack"); AAMDNodes AAMD; LI.getAAMetadata(AAMD); L->setAAMetadata(AAMD); @@ -1064,12 +1064,16 @@ Instruction *InstCombiner::visitLoadInst(LoadInst &LI) { if (SelectInst *SI = dyn_cast<SelectInst>(Op)) { // load (select (Cond, &V1, &V2)) --> select(Cond, load &V1, load &V2). unsigned Align = LI.getAlignment(); - if (isSafeToLoadUnconditionally(SI->getOperand(1), Align, DL, SI) && - isSafeToLoadUnconditionally(SI->getOperand(2), Align, DL, SI)) { - LoadInst *V1 = Builder.CreateLoad(SI->getOperand(1), - SI->getOperand(1)->getName()+".val"); - LoadInst *V2 = Builder.CreateLoad(SI->getOperand(2), - SI->getOperand(2)->getName()+".val"); + if (isSafeToLoadUnconditionally(SI->getOperand(1), LI.getType(), Align, + DL, SI) && + isSafeToLoadUnconditionally(SI->getOperand(2), LI.getType(), Align, + DL, SI)) { + LoadInst *V1 = + Builder.CreateLoad(LI.getType(), SI->getOperand(1), + SI->getOperand(1)->getName() + ".val"); + LoadInst *V2 = + Builder.CreateLoad(LI.getType(), SI->getOperand(2), + SI->getOperand(2)->getName() + ".val"); assert(LI.isUnordered() && "implied by above"); V1->setAlignment(Align); V1->setAtomic(LI.getOrdering(), LI.getSyncScopeID()); @@ -1436,6 +1440,12 @@ Instruction *InstCombiner::visitStoreInst(StoreInst &SI) { } } + // If we have a store to a location which is known constant, we can conclude + // that the store must be storing the constant value (else the memory + // wouldn't be constant), and this must be a noop. + if (AA->pointsToConstantMemory(Ptr)) + return eraseInstFromFunction(SI); + // Do really simple DSE, to catch cases where there are several consecutive // stores to the same location, separated by a few arithmetic operations. This // situation often occurs with bitfield accesses. diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index 7e99f3e4e500f..cc753ce05313e 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -1,9 +1,8 @@ //===- InstCombineMulDivRem.cpp -------------------------------------------===// // -// 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 // //===----------------------------------------------------------------------===// // @@ -375,11 +374,13 @@ Instruction *InstCombiner::visitFMul(BinaryOperator &I) { return BinaryOperator::CreateFMulFMF(X, ConstantExpr::getFNeg(C), &I); // Sink negation: -X * Y --> -(X * Y) - if (match(Op0, m_OneUse(m_FNeg(m_Value(X))))) + // But don't transform constant expressions because there's an inverse fold. + if (match(Op0, m_OneUse(m_FNeg(m_Value(X)))) && !isa<ConstantExpr>(Op0)) return BinaryOperator::CreateFNegFMF(Builder.CreateFMulFMF(X, Op1, &I), &I); // Sink negation: Y * -X --> -(X * Y) - if (match(Op1, m_OneUse(m_FNeg(m_Value(X))))) + // But don't transform constant expressions because there's an inverse fold. + if (match(Op1, m_OneUse(m_FNeg(m_Value(X)))) && !isa<ConstantExpr>(Op1)) return BinaryOperator::CreateFNegFMF(Builder.CreateFMulFMF(X, Op0, &I), &I); // fabs(X) * fabs(X) -> X * X @@ -431,6 +432,14 @@ Instruction *InstCombiner::visitFMul(BinaryOperator &I) { } } + Value *Z; + if (match(&I, m_c_FMul(m_OneUse(m_FDiv(m_Value(X), m_Value(Y))), + m_Value(Z)))) { + // Sink division: (X / Y) * Z --> (X * Z) / Y + Value *NewFMul = Builder.CreateFMulFMF(X, Z, &I); + return BinaryOperator::CreateFDivFMF(NewFMul, Y, &I); + } + // sqrt(X) * sqrt(Y) -> sqrt(X * Y) // nnan disallows the possibility of returning a number if both operands are // negative (in that case, we should return NaN). @@ -442,6 +451,45 @@ Instruction *InstCombiner::visitFMul(BinaryOperator &I) { return replaceInstUsesWith(I, Sqrt); } + // Like the similar transform in instsimplify, this requires 'nsz' because + // sqrt(-0.0) = -0.0, and -0.0 * -0.0 does not simplify to -0.0. + if (I.hasNoNaNs() && I.hasNoSignedZeros() && Op0 == Op1 && + Op0->hasNUses(2)) { + // Peek through fdiv to find squaring of square root: + // (X / sqrt(Y)) * (X / sqrt(Y)) --> (X * X) / Y + if (match(Op0, m_FDiv(m_Value(X), + m_Intrinsic<Intrinsic::sqrt>(m_Value(Y))))) { + Value *XX = Builder.CreateFMulFMF(X, X, &I); + return BinaryOperator::CreateFDivFMF(XX, Y, &I); + } + // (sqrt(Y) / X) * (sqrt(Y) / X) --> Y / (X * X) + if (match(Op0, m_FDiv(m_Intrinsic<Intrinsic::sqrt>(m_Value(Y)), + m_Value(X)))) { + Value *XX = Builder.CreateFMulFMF(X, X, &I); + return BinaryOperator::CreateFDivFMF(Y, XX, &I); + } + } + + // exp(X) * exp(Y) -> exp(X + Y) + // Match as long as at least one of exp has only one use. + if (match(Op0, m_Intrinsic<Intrinsic::exp>(m_Value(X))) && + match(Op1, m_Intrinsic<Intrinsic::exp>(m_Value(Y))) && + (Op0->hasOneUse() || Op1->hasOneUse())) { + Value *XY = Builder.CreateFAddFMF(X, Y, &I); + Value *Exp = Builder.CreateUnaryIntrinsic(Intrinsic::exp, XY, &I); + return replaceInstUsesWith(I, Exp); + } + + // exp2(X) * exp2(Y) -> exp2(X + Y) + // Match as long as at least one of exp2 has only one use. + if (match(Op0, m_Intrinsic<Intrinsic::exp2>(m_Value(X))) && + match(Op1, m_Intrinsic<Intrinsic::exp2>(m_Value(Y))) && + (Op0->hasOneUse() || Op1->hasOneUse())) { + Value *XY = Builder.CreateFAddFMF(X, Y, &I); + Value *Exp2 = Builder.CreateUnaryIntrinsic(Intrinsic::exp2, XY, &I); + return replaceInstUsesWith(I, Exp2); + } + // (X*Y) * X => (X*X) * Y where Y != X // The purpose is two-fold: // 1) to form a power expression (of X). @@ -576,7 +624,7 @@ static bool isMultiple(const APInt &C1, const APInt &C2, APInt &Quotient, if (IsSigned && C1.isMinSignedValue() && C2.isAllOnesValue()) return false; - APInt Remainder(C1.getBitWidth(), /*Val=*/0ULL, IsSigned); + APInt Remainder(C1.getBitWidth(), /*val=*/0ULL, IsSigned); if (IsSigned) APInt::sdivrem(C1, C2, Quotient, Remainder); else @@ -613,7 +661,7 @@ Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) { // (X / C1) / C2 -> X / (C1*C2) if ((IsSigned && match(Op0, m_SDiv(m_Value(X), m_APInt(C1)))) || (!IsSigned && match(Op0, m_UDiv(m_Value(X), m_APInt(C1))))) { - APInt Product(C1->getBitWidth(), /*Val=*/0ULL, IsSigned); + APInt Product(C1->getBitWidth(), /*val=*/0ULL, IsSigned); if (!multiplyOverflows(*C1, *C2, Product, IsSigned)) return BinaryOperator::Create(I.getOpcode(), X, ConstantInt::get(Ty, Product)); @@ -621,7 +669,7 @@ Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) { if ((IsSigned && match(Op0, m_NSWMul(m_Value(X), m_APInt(C1)))) || (!IsSigned && match(Op0, m_NUWMul(m_Value(X), m_APInt(C1))))) { - APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned); + APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned); // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1. if (isMultiple(*C2, *C1, Quotient, IsSigned)) { @@ -645,7 +693,7 @@ Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) { if ((IsSigned && match(Op0, m_NSWShl(m_Value(X), m_APInt(C1))) && *C1 != C1->getBitWidth() - 1) || (!IsSigned && match(Op0, m_NUWShl(m_Value(X), m_APInt(C1))))) { - APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned); + APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned); APInt C1Shifted = APInt::getOneBitSet( C1->getBitWidth(), static_cast<unsigned>(C1->getLimitedValue())); @@ -977,6 +1025,10 @@ Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))) return BinaryOperator::CreateNeg(Op0); + // X / INT_MIN --> X == INT_MIN + if (match(Op1, m_SignMask())) + return new ZExtInst(Builder.CreateICmpEQ(Op0, Op1), I.getType()); + const APInt *Op1C; if (match(Op1, m_APInt(Op1C))) { // sdiv exact X, C --> ashr exact X, log2(C) @@ -1001,22 +1053,25 @@ Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { Value *NarrowOp = Builder.CreateSDiv(Op0Src, NarrowDivisor); return new SExtInst(NarrowOp, Op0->getType()); } - } - if (Constant *RHS = dyn_cast<Constant>(Op1)) { - // X/INT_MIN -> X == INT_MIN - if (RHS->isMinSignedValue()) - return new ZExtInst(Builder.CreateICmpEQ(Op0, Op1), I.getType()); - - // -X/C --> X/-C provided the negation doesn't overflow. - Value *X; - if (match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) { - auto *BO = BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(RHS)); + // -X / C --> X / -C (if the negation doesn't overflow). + // TODO: This could be enhanced to handle arbitrary vector constants by + // checking if all elements are not the min-signed-val. + if (!Op1C->isMinSignedValue() && + match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) { + Constant *NegC = ConstantInt::get(I.getType(), -(*Op1C)); + Instruction *BO = BinaryOperator::CreateSDiv(X, NegC); BO->setIsExact(I.isExact()); return BO; } } + // -X / Y --> -(X / Y) + Value *Y; + if (match(&I, m_SDiv(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y)))) + return BinaryOperator::CreateNSWNeg( + Builder.CreateSDiv(X, Y, I.getName(), I.isExact())); + // If the sign bits of both operands are zero (i.e. we can prove they are // unsigned inputs), turn this into a udiv. APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits())); @@ -1161,7 +1216,8 @@ Instruction *InstCombiner::visitFDiv(BinaryOperator &I) { IRBuilder<> B(&I); IRBuilder<>::FastMathFlagGuard FMFGuard(B); B.setFastMathFlags(I.getFastMathFlags()); - AttributeList Attrs = CallSite(Op0).getCalledFunction()->getAttributes(); + AttributeList Attrs = + cast<CallBase>(Op0)->getCalledFunction()->getAttributes(); Value *Res = emitUnaryFloatFnCall(X, &TLI, LibFunc_tan, LibFunc_tanf, LibFunc_tanl, B, Attrs); if (IsCot) @@ -1305,6 +1361,11 @@ Instruction *InstCombiner::visitSRem(BinaryOperator &I) { } } + // -X srem Y --> -(X srem Y) + Value *X, *Y; + if (match(&I, m_SRem(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y)))) + return BinaryOperator::CreateNSWNeg(Builder.CreateSRem(X, Y)); + // If the sign bits of both operands are zero (i.e. we can prove they are // unsigned inputs), turn this into a urem. APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits())); diff --git a/lib/Transforms/InstCombine/InstCombinePHI.cpp b/lib/Transforms/InstCombine/InstCombinePHI.cpp index 7603cf4d79589..5820ab7266374 100644 --- a/lib/Transforms/InstCombine/InstCombinePHI.cpp +++ b/lib/Transforms/InstCombine/InstCombinePHI.cpp @@ -1,9 +1,8 @@ //===- InstCombinePHI.cpp -------------------------------------------------===// // -// 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 // //===----------------------------------------------------------------------===// // @@ -596,7 +595,8 @@ Instruction *InstCombiner::FoldPHIArgLoadIntoPHI(PHINode &PN) { Value *InVal = FirstLI->getOperand(0); NewPN->addIncoming(InVal, PN.getIncomingBlock(0)); - LoadInst *NewLI = new LoadInst(NewPN, "", isVolatile, LoadAlignment); + LoadInst *NewLI = + new LoadInst(FirstLI->getType(), NewPN, "", isVolatile, LoadAlignment); unsigned KnownIDs[] = { LLVMContext::MD_tbaa, @@ -1004,6 +1004,11 @@ Instruction *InstCombiner::SliceUpIllegalIntegerPHI(PHINode &FirstPhi) { !isa<ConstantInt>(UserI->getOperand(1))) return nullptr; + // Bail on out of range shifts. + unsigned SizeInBits = UserI->getType()->getScalarSizeInBits(); + if (cast<ConstantInt>(UserI->getOperand(1))->getValue().uge(SizeInBits)) + return nullptr; + unsigned Shift = cast<ConstantInt>(UserI->getOperand(1))->getZExtValue(); PHIUsers.push_back(PHIUsageRecord(PHIId, Shift, UserI->user_back())); } diff --git a/lib/Transforms/InstCombine/InstCombineSelect.cpp b/lib/Transforms/InstCombine/InstCombineSelect.cpp index faf58a08976dd..aefaf5af17507 100644 --- a/lib/Transforms/InstCombine/InstCombineSelect.cpp +++ b/lib/Transforms/InstCombine/InstCombineSelect.cpp @@ -1,9 +1,8 @@ //===- InstCombineSelect.cpp ----------------------------------------------===// // -// 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 // //===----------------------------------------------------------------------===// // @@ -293,6 +292,8 @@ Instruction *InstCombiner::foldSelectOpOp(SelectInst &SI, Instruction *TI, return nullptr; // If this is a cast from the same type, merge. + Value *Cond = SI.getCondition(); + Type *CondTy = Cond->getType(); if (TI->getNumOperands() == 1 && TI->isCast()) { Type *FIOpndTy = FI->getOperand(0)->getType(); if (TI->getOperand(0)->getType() != FIOpndTy) @@ -300,7 +301,6 @@ Instruction *InstCombiner::foldSelectOpOp(SelectInst &SI, Instruction *TI, // The select condition may be a vector. We may only change the operand // type if the vector width remains the same (and matches the condition). - Type *CondTy = SI.getCondition()->getType(); if (CondTy->isVectorTy()) { if (!FIOpndTy->isVectorTy()) return nullptr; @@ -327,12 +327,24 @@ Instruction *InstCombiner::foldSelectOpOp(SelectInst &SI, Instruction *TI, // Fold this by inserting a select from the input values. Value *NewSI = - Builder.CreateSelect(SI.getCondition(), TI->getOperand(0), - FI->getOperand(0), SI.getName() + ".v", &SI); + Builder.CreateSelect(Cond, TI->getOperand(0), FI->getOperand(0), + SI.getName() + ".v", &SI); return CastInst::Create(Instruction::CastOps(TI->getOpcode()), NewSI, TI->getType()); } + // Cond ? -X : -Y --> -(Cond ? X : Y) + Value *X, *Y; + if (match(TI, m_FNeg(m_Value(X))) && match(FI, m_FNeg(m_Value(Y))) && + (TI->hasOneUse() || FI->hasOneUse())) { + Value *NewSel = Builder.CreateSelect(Cond, X, Y, SI.getName() + ".v", &SI); + // TODO: Remove the hack for the binop form when the unary op is optimized + // properly with all IR passes. + if (TI->getOpcode() != Instruction::FNeg) + return BinaryOperator::CreateFNegFMF(NewSel, cast<BinaryOperator>(TI)); + return UnaryOperator::CreateFNeg(NewSel); + } + // Only handle binary operators (including two-operand getelementptr) with // one-use here. As with the cast case above, it may be possible to relax the // one-use constraint, but that needs be examined carefully since it may not @@ -374,13 +386,12 @@ Instruction *InstCombiner::foldSelectOpOp(SelectInst &SI, Instruction *TI, // If the select condition is a vector, the operands of the original select's // operands also must be vectors. This may not be the case for getelementptr // for example. - if (SI.getCondition()->getType()->isVectorTy() && - (!OtherOpT->getType()->isVectorTy() || - !OtherOpF->getType()->isVectorTy())) + if (CondTy->isVectorTy() && (!OtherOpT->getType()->isVectorTy() || + !OtherOpF->getType()->isVectorTy())) return nullptr; // If we reach here, they do have operations in common. - Value *NewSI = Builder.CreateSelect(SI.getCondition(), OtherOpT, OtherOpF, + Value *NewSI = Builder.CreateSelect(Cond, OtherOpT, OtherOpF, SI.getName() + ".v", &SI); Value *Op0 = MatchIsOpZero ? MatchOp : NewSI; Value *Op1 = MatchIsOpZero ? NewSI : MatchOp; @@ -521,6 +532,46 @@ static Instruction *foldSelectICmpAndAnd(Type *SelType, const ICmpInst *Cmp, } /// We want to turn: +/// (select (icmp sgt x, C), lshr (X, Y), ashr (X, Y)); iff C s>= -1 +/// (select (icmp slt x, C), ashr (X, Y), lshr (X, Y)); iff C s>= 0 +/// into: +/// ashr (X, Y) +static Value *foldSelectICmpLshrAshr(const ICmpInst *IC, Value *TrueVal, + Value *FalseVal, + InstCombiner::BuilderTy &Builder) { + ICmpInst::Predicate Pred = IC->getPredicate(); + Value *CmpLHS = IC->getOperand(0); + Value *CmpRHS = IC->getOperand(1); + if (!CmpRHS->getType()->isIntOrIntVectorTy()) + return nullptr; + + Value *X, *Y; + unsigned Bitwidth = CmpRHS->getType()->getScalarSizeInBits(); + if ((Pred != ICmpInst::ICMP_SGT || + !match(CmpRHS, + m_SpecificInt_ICMP(ICmpInst::ICMP_SGE, APInt(Bitwidth, -1)))) && + (Pred != ICmpInst::ICMP_SLT || + !match(CmpRHS, + m_SpecificInt_ICMP(ICmpInst::ICMP_SGE, APInt(Bitwidth, 0))))) + return nullptr; + + // Canonicalize so that ashr is in FalseVal. + if (Pred == ICmpInst::ICMP_SLT) + std::swap(TrueVal, FalseVal); + + if (match(TrueVal, m_LShr(m_Value(X), m_Value(Y))) && + match(FalseVal, m_AShr(m_Specific(X), m_Specific(Y))) && + match(CmpLHS, m_Specific(X))) { + const auto *Ashr = cast<Instruction>(FalseVal); + // if lshr is not exact and ashr is, this new ashr must not be exact. + bool IsExact = Ashr->isExact() && cast<Instruction>(TrueVal)->isExact(); + return Builder.CreateAShr(X, Y, IC->getName(), IsExact); + } + + return nullptr; +} + +/// We want to turn: /// (select (icmp eq (and X, C1), 0), Y, (or Y, C2)) /// into: /// (or (shl (and X, C1), C3), Y) @@ -623,11 +674,7 @@ static Value *foldSelectICmpAndOr(const ICmpInst *IC, Value *TrueVal, return Builder.CreateOr(V, Y); } -/// Transform patterns such as: (a > b) ? a - b : 0 -/// into: ((a > b) ? a : b) - b) -/// This produces a canonical max pattern that is more easily recognized by the -/// backend and converted into saturated subtraction instructions if those -/// exist. +/// Transform patterns such as (a > b) ? a - b : 0 into usub.sat(a, b). /// There are 8 commuted/swapped variants of this pattern. /// TODO: Also support a - UMIN(a,b) patterns. static Value *canonicalizeSaturatedSubtract(const ICmpInst *ICI, @@ -669,11 +716,73 @@ static Value *canonicalizeSaturatedSubtract(const ICmpInst *ICI, if (!TrueVal->hasOneUse()) return nullptr; - // All checks passed, convert to canonical unsigned saturated subtraction - // form: sub(max()). - // (a > b) ? a - b : 0 -> ((a > b) ? a : b) - b) - Value *Max = Builder.CreateSelect(Builder.CreateICmp(Pred, A, B), A, B); - return IsNegative ? Builder.CreateSub(B, Max) : Builder.CreateSub(Max, B); + // (a > b) ? a - b : 0 -> usub.sat(a, b) + // (a > b) ? b - a : 0 -> -usub.sat(a, b) + Value *Result = Builder.CreateBinaryIntrinsic(Intrinsic::usub_sat, A, B); + if (IsNegative) + Result = Builder.CreateNeg(Result); + return Result; +} + +static Value *canonicalizeSaturatedAdd(ICmpInst *Cmp, Value *TVal, Value *FVal, + InstCombiner::BuilderTy &Builder) { + if (!Cmp->hasOneUse()) + return nullptr; + + // Match unsigned saturated add with constant. + Value *Cmp0 = Cmp->getOperand(0); + Value *Cmp1 = Cmp->getOperand(1); + ICmpInst::Predicate Pred = Cmp->getPredicate(); + Value *X; + const APInt *C, *CmpC; + if (Pred == ICmpInst::ICMP_ULT && + match(TVal, m_Add(m_Value(X), m_APInt(C))) && X == Cmp0 && + match(FVal, m_AllOnes()) && match(Cmp1, m_APInt(CmpC)) && *CmpC == ~*C) { + // (X u< ~C) ? (X + C) : -1 --> uadd.sat(X, C) + return Builder.CreateBinaryIntrinsic( + Intrinsic::uadd_sat, X, ConstantInt::get(X->getType(), *C)); + } + + // Match unsigned saturated add of 2 variables with an unnecessary 'not'. + // There are 8 commuted variants. + // Canonicalize -1 (saturated result) to true value of the select. Just + // swapping the compare operands is legal, because the selected value is the + // same in case of equality, so we can interchange u< and u<=. + if (match(FVal, m_AllOnes())) { + std::swap(TVal, FVal); + std::swap(Cmp0, Cmp1); + } + if (!match(TVal, m_AllOnes())) + return nullptr; + + // Canonicalize predicate to 'ULT'. + if (Pred == ICmpInst::ICMP_UGT) { + Pred = ICmpInst::ICMP_ULT; + std::swap(Cmp0, Cmp1); + } + if (Pred != ICmpInst::ICMP_ULT) + return nullptr; + + // Match unsigned saturated add of 2 variables with an unnecessary 'not'. + Value *Y; + if (match(Cmp0, m_Not(m_Value(X))) && + match(FVal, m_c_Add(m_Specific(X), m_Value(Y))) && Y == Cmp1) { + // (~X u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y) + // (~X u< Y) ? -1 : (Y + X) --> uadd.sat(X, Y) + return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, X, Y); + } + // The 'not' op may be included in the sum but not the compare. + X = Cmp0; + Y = Cmp1; + if (match(FVal, m_c_Add(m_Not(m_Specific(X)), m_Specific(Y)))) { + // (X u< Y) ? -1 : (~X + Y) --> uadd.sat(~X, Y) + // (X u< Y) ? -1 : (Y + ~X) --> uadd.sat(Y, ~X) + BinaryOperator *BO = cast<BinaryOperator>(FVal); + return Builder.CreateBinaryIntrinsic( + Intrinsic::uadd_sat, BO->getOperand(0), BO->getOperand(1)); + } + + return nullptr; } /// Attempt to fold a cttz/ctlz followed by a icmp plus select into a single @@ -1043,12 +1152,18 @@ Instruction *InstCombiner::foldSelectInstWithICmp(SelectInst &SI, if (Value *V = foldSelectICmpAndOr(ICI, TrueVal, FalseVal, Builder)) return replaceInstUsesWith(SI, V); + if (Value *V = foldSelectICmpLshrAshr(ICI, TrueVal, FalseVal, Builder)) + return replaceInstUsesWith(SI, V); + if (Value *V = foldSelectCttzCtlz(ICI, TrueVal, FalseVal, Builder)) return replaceInstUsesWith(SI, V); if (Value *V = canonicalizeSaturatedSubtract(ICI, TrueVal, FalseVal, Builder)) return replaceInstUsesWith(SI, V); + if (Value *V = canonicalizeSaturatedAdd(ICI, TrueVal, FalseVal, Builder)) + return replaceInstUsesWith(SI, V); + return Changed ? &SI : nullptr; } @@ -1496,6 +1611,43 @@ static Instruction *foldSelectCmpXchg(SelectInst &SI) { return nullptr; } +static Instruction *moveAddAfterMinMax(SelectPatternFlavor SPF, Value *X, + Value *Y, + InstCombiner::BuilderTy &Builder) { + assert(SelectPatternResult::isMinOrMax(SPF) && "Expected min/max pattern"); + bool IsUnsigned = SPF == SelectPatternFlavor::SPF_UMIN || + SPF == SelectPatternFlavor::SPF_UMAX; + // TODO: If InstSimplify could fold all cases where C2 <= C1, we could change + // the constant value check to an assert. + Value *A; + const APInt *C1, *C2; + if (IsUnsigned && match(X, m_NUWAdd(m_Value(A), m_APInt(C1))) && + match(Y, m_APInt(C2)) && C2->uge(*C1) && X->hasNUses(2)) { + // umin (add nuw A, C1), C2 --> add nuw (umin A, C2 - C1), C1 + // umax (add nuw A, C1), C2 --> add nuw (umax A, C2 - C1), C1 + Value *NewMinMax = createMinMax(Builder, SPF, A, + ConstantInt::get(X->getType(), *C2 - *C1)); + return BinaryOperator::CreateNUW(BinaryOperator::Add, NewMinMax, + ConstantInt::get(X->getType(), *C1)); + } + + if (!IsUnsigned && match(X, m_NSWAdd(m_Value(A), m_APInt(C1))) && + match(Y, m_APInt(C2)) && X->hasNUses(2)) { + bool Overflow; + APInt Diff = C2->ssub_ov(*C1, Overflow); + if (!Overflow) { + // smin (add nsw A, C1), C2 --> add nsw (smin A, C2 - C1), C1 + // smax (add nsw A, C1), C2 --> add nsw (smax A, C2 - C1), C1 + Value *NewMinMax = createMinMax(Builder, SPF, A, + ConstantInt::get(X->getType(), Diff)); + return BinaryOperator::CreateNSW(BinaryOperator::Add, NewMinMax, + ConstantInt::get(X->getType(), *C1)); + } + } + + return nullptr; +} + /// Reduce a sequence of min/max with a common operand. static Instruction *factorizeMinMaxTree(SelectPatternFlavor SPF, Value *LHS, Value *RHS, @@ -1757,37 +1909,55 @@ Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { // NOTE: if we wanted to, this is where to detect MIN/MAX } + } - // Canonicalize select with fcmp to fabs(). -0.0 makes this tricky. We need - // fast-math-flags (nsz) or fsub with +0.0 (not fneg) for this to work. We - // also require nnan because we do not want to unintentionally change the - // sign of a NaN value. - Value *X = FCI->getOperand(0); - FCmpInst::Predicate Pred = FCI->getPredicate(); - if (match(FCI->getOperand(1), m_AnyZeroFP()) && FCI->hasNoNaNs()) { - // (X <= +/-0.0) ? (0.0 - X) : X --> fabs(X) - // (X > +/-0.0) ? X : (0.0 - X) --> fabs(X) - if ((X == FalseVal && Pred == FCmpInst::FCMP_OLE && - match(TrueVal, m_FSub(m_PosZeroFP(), m_Specific(X)))) || - (X == TrueVal && Pred == FCmpInst::FCMP_OGT && - match(FalseVal, m_FSub(m_PosZeroFP(), m_Specific(X))))) { - Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, FCI); - return replaceInstUsesWith(SI, Fabs); - } - // With nsz: - // (X < +/-0.0) ? -X : X --> fabs(X) - // (X <= +/-0.0) ? -X : X --> fabs(X) - // (X > +/-0.0) ? X : -X --> fabs(X) - // (X >= +/-0.0) ? X : -X --> fabs(X) - if (FCI->hasNoSignedZeros() && - ((X == FalseVal && match(TrueVal, m_FNeg(m_Specific(X))) && - (Pred == FCmpInst::FCMP_OLT || Pred == FCmpInst::FCMP_OLE)) || - (X == TrueVal && match(FalseVal, m_FNeg(m_Specific(X))) && - (Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_OGE)))) { - Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, FCI); - return replaceInstUsesWith(SI, Fabs); - } - } + // Canonicalize select with fcmp to fabs(). -0.0 makes this tricky. We need + // fast-math-flags (nsz) or fsub with +0.0 (not fneg) for this to work. We + // also require nnan because we do not want to unintentionally change the + // sign of a NaN value. + // FIXME: These folds should test/propagate FMF from the select, not the + // fsub or fneg. + // (X <= +/-0.0) ? (0.0 - X) : X --> fabs(X) + Instruction *FSub; + if (match(CondVal, m_FCmp(Pred, m_Specific(FalseVal), m_AnyZeroFP())) && + match(TrueVal, m_FSub(m_PosZeroFP(), m_Specific(FalseVal))) && + match(TrueVal, m_Instruction(FSub)) && FSub->hasNoNaNs() && + (Pred == FCmpInst::FCMP_OLE || Pred == FCmpInst::FCMP_ULE)) { + Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, FalseVal, FSub); + return replaceInstUsesWith(SI, Fabs); + } + // (X > +/-0.0) ? X : (0.0 - X) --> fabs(X) + if (match(CondVal, m_FCmp(Pred, m_Specific(TrueVal), m_AnyZeroFP())) && + match(FalseVal, m_FSub(m_PosZeroFP(), m_Specific(TrueVal))) && + match(FalseVal, m_Instruction(FSub)) && FSub->hasNoNaNs() && + (Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_UGT)) { + Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, TrueVal, FSub); + return replaceInstUsesWith(SI, Fabs); + } + // With nnan and nsz: + // (X < +/-0.0) ? -X : X --> fabs(X) + // (X <= +/-0.0) ? -X : X --> fabs(X) + Instruction *FNeg; + if (match(CondVal, m_FCmp(Pred, m_Specific(FalseVal), m_AnyZeroFP())) && + match(TrueVal, m_FNeg(m_Specific(FalseVal))) && + match(TrueVal, m_Instruction(FNeg)) && + FNeg->hasNoNaNs() && FNeg->hasNoSignedZeros() && + (Pred == FCmpInst::FCMP_OLT || Pred == FCmpInst::FCMP_OLE || + Pred == FCmpInst::FCMP_ULT || Pred == FCmpInst::FCMP_ULE)) { + Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, FalseVal, FNeg); + return replaceInstUsesWith(SI, Fabs); + } + // With nnan and nsz: + // (X > +/-0.0) ? X : -X --> fabs(X) + // (X >= +/-0.0) ? X : -X --> fabs(X) + if (match(CondVal, m_FCmp(Pred, m_Specific(TrueVal), m_AnyZeroFP())) && + match(FalseVal, m_FNeg(m_Specific(TrueVal))) && + match(FalseVal, m_Instruction(FNeg)) && + FNeg->hasNoNaNs() && FNeg->hasNoSignedZeros() && + (Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_OGE || + Pred == FCmpInst::FCMP_UGT || Pred == FCmpInst::FCMP_UGE)) { + Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, TrueVal, FNeg); + return replaceInstUsesWith(SI, Fabs); } // See if we are selecting two values based on a comparison of the two values. @@ -1895,11 +2065,27 @@ Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { if (Instruction *I = moveNotAfterMinMax(RHS, LHS)) return I; + if (Instruction *I = moveAddAfterMinMax(SPF, LHS, RHS, Builder)) + return I; + if (Instruction *I = factorizeMinMaxTree(SPF, LHS, RHS, Builder)) return I; } } + // Canonicalize select of FP values where NaN and -0.0 are not valid as + // minnum/maxnum intrinsics. + if (isa<FPMathOperator>(SI) && SI.hasNoNaNs() && SI.hasNoSignedZeros()) { + Value *X, *Y; + if (match(&SI, m_OrdFMax(m_Value(X), m_Value(Y)))) + return replaceInstUsesWith( + SI, Builder.CreateBinaryIntrinsic(Intrinsic::maxnum, X, Y, &SI)); + + if (match(&SI, m_OrdFMin(m_Value(X), m_Value(Y)))) + return replaceInstUsesWith( + SI, Builder.CreateBinaryIntrinsic(Intrinsic::minnum, X, Y, &SI)); + } + // See if we can fold the select into a phi node if the condition is a select. if (auto *PN = dyn_cast<PHINode>(SI.getCondition())) // The true/false values have to be live in the PHI predecessor's blocks. diff --git a/lib/Transforms/InstCombine/InstCombineShifts.cpp b/lib/Transforms/InstCombine/InstCombineShifts.cpp index c562d45a9e2b9..c821292400cd5 100644 --- a/lib/Transforms/InstCombine/InstCombineShifts.cpp +++ b/lib/Transforms/InstCombine/InstCombineShifts.cpp @@ -1,9 +1,8 @@ //===- InstCombineShifts.cpp ----------------------------------------------===// // -// 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 // //===----------------------------------------------------------------------===// // @@ -21,6 +20,51 @@ using namespace PatternMatch; #define DEBUG_TYPE "instcombine" +// Given pattern: +// (x shiftopcode Q) shiftopcode K +// we should rewrite it as +// x shiftopcode (Q+K) iff (Q+K) u< bitwidth(x) +// This is valid for any shift, but they must be identical. +static Instruction * +reassociateShiftAmtsOfTwoSameDirectionShifts(BinaryOperator *Sh0, + const SimplifyQuery &SQ) { + // Look for: (x shiftopcode ShAmt0) shiftopcode ShAmt1 + Value *X, *ShAmt1, *ShAmt0; + Instruction *Sh1; + if (!match(Sh0, m_Shift(m_CombineAnd(m_Shift(m_Value(X), m_Value(ShAmt1)), + m_Instruction(Sh1)), + m_Value(ShAmt0)))) + return nullptr; + + // The shift opcodes must be identical. + Instruction::BinaryOps ShiftOpcode = Sh0->getOpcode(); + if (ShiftOpcode != Sh1->getOpcode()) + return nullptr; + // Can we fold (ShAmt0+ShAmt1) ? + Value *NewShAmt = SimplifyBinOp(Instruction::BinaryOps::Add, ShAmt0, ShAmt1, + SQ.getWithInstruction(Sh0)); + if (!NewShAmt) + return nullptr; // Did not simplify. + // Is the new shift amount smaller than the bit width? + // FIXME: could also rely on ConstantRange. + unsigned BitWidth = X->getType()->getScalarSizeInBits(); + if (!match(NewShAmt, m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULT, + APInt(BitWidth, BitWidth)))) + return nullptr; + // All good, we can do this fold. + BinaryOperator *NewShift = BinaryOperator::Create(ShiftOpcode, X, NewShAmt); + // If both of the original shifts had the same flag set, preserve the flag. + if (ShiftOpcode == Instruction::BinaryOps::Shl) { + NewShift->setHasNoUnsignedWrap(Sh0->hasNoUnsignedWrap() && + Sh1->hasNoUnsignedWrap()); + NewShift->setHasNoSignedWrap(Sh0->hasNoSignedWrap() && + Sh1->hasNoSignedWrap()); + } else { + NewShift->setIsExact(Sh0->isExact() && Sh1->isExact()); + } + return NewShift; +} + Instruction *InstCombiner::commonShiftTransforms(BinaryOperator &I) { Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); assert(Op0->getType() == Op1->getType()); @@ -39,6 +83,10 @@ Instruction *InstCombiner::commonShiftTransforms(BinaryOperator &I) { if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I)) return Res; + if (Instruction *NewShift = + reassociateShiftAmtsOfTwoSameDirectionShifts(&I, SQ)) + return NewShift; + // (C1 shift (A add C2)) -> (C1 shift C2) shift A) // iff A and C2 are both positive. Value *A; @@ -313,35 +361,17 @@ static Value *getShiftedValue(Value *V, unsigned NumBits, bool isLeftShift, // If this is a bitwise operator or add with a constant RHS we might be able // to pull it through a shift. static bool canShiftBinOpWithConstantRHS(BinaryOperator &Shift, - BinaryOperator *BO, - const APInt &C) { - bool IsValid = true; // Valid only for And, Or Xor, - bool HighBitSet = false; // Transform ifhigh bit of constant set? - + BinaryOperator *BO) { switch (BO->getOpcode()) { - default: IsValid = false; break; // Do not perform transform! + default: + return false; // Do not perform transform! case Instruction::Add: - IsValid = Shift.getOpcode() == Instruction::Shl; - break; + return Shift.getOpcode() == Instruction::Shl; case Instruction::Or: case Instruction::Xor: - HighBitSet = false; - break; case Instruction::And: - HighBitSet = true; - break; + return true; } - - // If this is a signed shift right, and the high bit is modified - // by the logical operation, do not perform the transformation. - // The HighBitSet boolean indicates the value of the high bit of - // the constant which would cause it to be modified for this - // operation. - // - if (IsValid && Shift.getOpcode() == Instruction::AShr) - IsValid = C.isNegative() == HighBitSet; - - return IsValid; } Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, Constant *Op1, @@ -508,7 +538,7 @@ Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, Constant *Op1, // shift is the only use, we can pull it out of the shift. const APInt *Op0C; if (match(Op0BO->getOperand(1), m_APInt(Op0C))) { - if (canShiftBinOpWithConstantRHS(I, Op0BO, *Op0C)) { + if (canShiftBinOpWithConstantRHS(I, Op0BO)) { Constant *NewRHS = ConstantExpr::get(I.getOpcode(), cast<Constant>(Op0BO->getOperand(1)), Op1); @@ -552,7 +582,7 @@ Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, Constant *Op1, const APInt *C; if (!isa<Constant>(FalseVal) && TBO->getOperand(0) == FalseVal && match(TBO->getOperand(1), m_APInt(C)) && - canShiftBinOpWithConstantRHS(I, TBO, *C)) { + canShiftBinOpWithConstantRHS(I, TBO)) { Constant *NewRHS = ConstantExpr::get(I.getOpcode(), cast<Constant>(TBO->getOperand(1)), Op1); @@ -571,7 +601,7 @@ Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, Constant *Op1, const APInt *C; if (!isa<Constant>(TrueVal) && FBO->getOperand(0) == TrueVal && match(FBO->getOperand(1), m_APInt(C)) && - canShiftBinOpWithConstantRHS(I, FBO, *C)) { + canShiftBinOpWithConstantRHS(I, FBO)) { Constant *NewRHS = ConstantExpr::get(I.getOpcode(), cast<Constant>(FBO->getOperand(1)), Op1); @@ -601,6 +631,8 @@ Instruction *InstCombiner::visitShl(BinaryOperator &I) { Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); Type *Ty = I.getType(); + unsigned BitWidth = Ty->getScalarSizeInBits(); + const APInt *ShAmtAPInt; if (match(Op1, m_APInt(ShAmtAPInt))) { unsigned ShAmt = ShAmtAPInt->getZExtValue(); @@ -689,6 +721,12 @@ Instruction *InstCombiner::visitShl(BinaryOperator &I) { return BinaryOperator::CreateMul(X, ConstantExpr::getShl(C2, C1)); } + // (1 << (C - x)) -> ((1 << C) >> x) if C is bitwidth - 1 + if (match(Op0, m_One()) && + match(Op1, m_Sub(m_SpecificInt(BitWidth - 1), m_Value(X)))) + return BinaryOperator::CreateLShr( + ConstantInt::get(Ty, APInt::getSignMask(BitWidth)), X); + return nullptr; } diff --git a/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp b/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp index 9bf87d0246072..e0d85c4b49ae6 100644 --- a/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp +++ b/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp @@ -1,9 +1,8 @@ //===- InstCombineSimplifyDemanded.cpp ------------------------------------===// // -// 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 // //===----------------------------------------------------------------------===// // @@ -366,10 +365,9 @@ Value *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits InputKnown(SrcBitWidth); if (SimplifyDemandedBits(I, 0, InputDemandedMask, InputKnown, Depth + 1)) return I; - Known = InputKnown.zextOrTrunc(BitWidth); - // Any top bits are known to be zero. - if (BitWidth > SrcBitWidth) - Known.Zero.setBitsFrom(SrcBitWidth); + assert(InputKnown.getBitWidth() == SrcBitWidth && "Src width changed?"); + Known = InputKnown.zextOrTrunc(BitWidth, + true /* ExtendedBitsAreKnownZero */); assert(!Known.hasConflict() && "Bits known to be one AND zero?"); break; } @@ -967,26 +965,16 @@ InstCombiner::simplifyShrShlDemandedBits(Instruction *Shr, const APInt &ShrOp1, } /// Implement SimplifyDemandedVectorElts for amdgcn buffer and image intrinsics. +/// +/// Note: This only supports non-TFE/LWE image intrinsic calls; those have +/// struct returns. Value *InstCombiner::simplifyAMDGCNMemoryIntrinsicDemanded(IntrinsicInst *II, APInt DemandedElts, - int DMaskIdx, - int TFCIdx) { + int DMaskIdx) { unsigned VWidth = II->getType()->getVectorNumElements(); if (VWidth == 1) return nullptr; - // Need to change to new instruction format - ConstantInt *TFC = nullptr; - bool TFELWEEnabled = false; - if (TFCIdx > 0) { - TFC = dyn_cast<ConstantInt>(II->getArgOperand(TFCIdx)); - TFELWEEnabled = TFC->getZExtValue() & 0x1 // TFE - || TFC->getZExtValue() & 0x2; // LWE - } - - if (TFELWEEnabled) - return nullptr; // TFE not yet supported - ConstantInt *NewDMask = nullptr; if (DMaskIdx < 0) { @@ -994,10 +982,7 @@ Value *InstCombiner::simplifyAMDGCNMemoryIntrinsicDemanded(IntrinsicInst *II, // below. DemandedElts = (1 << DemandedElts.getActiveBits()) - 1; } else { - ConstantInt *DMask = dyn_cast<ConstantInt>(II->getArgOperand(DMaskIdx)); - if (!DMask) - return nullptr; // non-constant dmask is not supported by codegen - + ConstantInt *DMask = cast<ConstantInt>(II->getArgOperand(DMaskIdx)); unsigned DMaskVal = DMask->getZExtValue() & 0xf; // Mask off values that are undefined because the dmask doesn't cover them @@ -1018,8 +1003,7 @@ Value *InstCombiner::simplifyAMDGCNMemoryIntrinsicDemanded(IntrinsicInst *II, NewDMask = ConstantInt::get(DMask->getType(), NewDMaskVal); } - // TODO: Handle 3 vectors when supported in code gen. - unsigned NewNumElts = PowerOf2Ceil(DemandedElts.countPopulation()); + unsigned NewNumElts = DemandedElts.countPopulation(); if (!NewNumElts) return UndefValue::get(II->getType()); @@ -1035,13 +1019,12 @@ Value *InstCombiner::simplifyAMDGCNMemoryIntrinsicDemanded(IntrinsicInst *II, getIntrinsicInfoTableEntries(IID, Table); ArrayRef<Intrinsic::IITDescriptor> TableRef = Table; + // Validate function argument and return types, extracting overloaded types + // along the way. FunctionType *FTy = II->getCalledFunction()->getFunctionType(); SmallVector<Type *, 6> OverloadTys; - Intrinsic::matchIntrinsicType(FTy->getReturnType(), TableRef, OverloadTys); - for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) - Intrinsic::matchIntrinsicType(FTy->getParamType(i), TableRef, OverloadTys); + Intrinsic::matchIntrinsicSignature(FTy, TableRef, OverloadTys); - // Get the new return type overload of the intrinsic. Module *M = II->getParent()->getParent()->getParent(); Type *EltTy = II->getType()->getVectorElementType(); Type *NewTy = (NewNumElts == 1) ? EltTy : VectorType::get(EltTy, NewNumElts); @@ -1184,6 +1167,39 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, switch (I->getOpcode()) { default: break; + case Instruction::GetElementPtr: { + // The LangRef requires that struct geps have all constant indices. As + // such, we can't convert any operand to partial undef. + auto mayIndexStructType = [](GetElementPtrInst &GEP) { + for (auto I = gep_type_begin(GEP), E = gep_type_end(GEP); + I != E; I++) + if (I.isStruct()) + return true;; + return false; + }; + if (mayIndexStructType(cast<GetElementPtrInst>(*I))) + break; + + // Conservatively track the demanded elements back through any vector + // operands we may have. We know there must be at least one, or we + // wouldn't have a vector result to get here. Note that we intentionally + // merge the undef bits here since gepping with either an undef base or + // index results in undef. + for (unsigned i = 0; i < I->getNumOperands(); i++) { + if (isa<UndefValue>(I->getOperand(i))) { + // If the entire vector is undefined, just return this info. + UndefElts = EltMask; + return nullptr; + } + if (I->getOperand(i)->getType()->isVectorTy()) { + APInt UndefEltsOp(VWidth, 0); + simplifyAndSetOp(I, i, DemandedElts, UndefEltsOp); + UndefElts |= UndefEltsOp; + } + } + + break; + } case Instruction::InsertElement: { // If this is a variable index, we don't know which element it overwrites. // demand exactly the same input as we produce. @@ -1430,6 +1446,30 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, IntrinsicInst *II = dyn_cast<IntrinsicInst>(I); if (!II) break; switch (II->getIntrinsicID()) { + case Intrinsic::masked_gather: // fallthrough + case Intrinsic::masked_load: { + // Subtlety: If we load from a pointer, the pointer must be valid + // regardless of whether the element is demanded. Doing otherwise risks + // segfaults which didn't exist in the original program. + APInt DemandedPtrs(APInt::getAllOnesValue(VWidth)), + DemandedPassThrough(DemandedElts); + if (auto *CV = dyn_cast<ConstantVector>(II->getOperand(2))) + for (unsigned i = 0; i < VWidth; i++) { + Constant *CElt = CV->getAggregateElement(i); + if (CElt->isNullValue()) + DemandedPtrs.clearBit(i); + else if (CElt->isAllOnesValue()) + DemandedPassThrough.clearBit(i); + } + if (II->getIntrinsicID() == Intrinsic::masked_gather) + simplifyAndSetOp(II, 0, DemandedPtrs, UndefElts2); + simplifyAndSetOp(II, 3, DemandedPassThrough, UndefElts3); + + // Output elements are undefined if the element from both sources are. + // TODO: can strengthen via mask as well. + UndefElts = UndefElts2 & UndefElts3; + break; + } case Intrinsic::x86_xop_vfrcz_ss: case Intrinsic::x86_xop_vfrcz_sd: // The instructions for these intrinsics are speced to zero upper bits not @@ -1639,8 +1679,7 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, return simplifyAMDGCNMemoryIntrinsicDemanded(II, DemandedElts); default: { if (getAMDGPUImageDMaskIntrinsic(II->getIntrinsicID())) - return simplifyAMDGCNMemoryIntrinsicDemanded( - II, DemandedElts, 0, II->getNumArgOperands() - 2); + return simplifyAMDGCNMemoryIntrinsicDemanded(II, DemandedElts, 0); break; } @@ -1667,5 +1706,10 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, UndefElts &= UndefElts2; } + // If we've proven all of the lanes undef, return an undef value. + // TODO: Intersect w/demanded lanes + if (UndefElts.isAllOnesValue()) + return UndefValue::get(I->getType());; + return MadeChange ? I : nullptr; } diff --git a/lib/Transforms/InstCombine/InstCombineVectorOps.cpp b/lib/Transforms/InstCombine/InstCombineVectorOps.cpp index 0ad1fc0e791f1..dc9abdd7f47a4 100644 --- a/lib/Transforms/InstCombine/InstCombineVectorOps.cpp +++ b/lib/Transforms/InstCombine/InstCombineVectorOps.cpp @@ -1,9 +1,8 @@ //===- InstCombineVectorOps.cpp -------------------------------------------===// // -// 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 // //===----------------------------------------------------------------------===// // @@ -663,18 +662,17 @@ static bool isShuffleEquivalentToSelect(ShuffleVectorInst &Shuf) { return true; } -// Turn a chain of inserts that splats a value into a canonical insert + shuffle -// splat. That is: -// insertelt(insertelt(insertelt(insertelt X, %k, 0), %k, 1), %k, 2) ... -> -// shufflevector(insertelt(X, %k, 0), undef, zero) -static Instruction *foldInsSequenceIntoBroadcast(InsertElementInst &InsElt) { - // We are interested in the last insert in a chain. So, if this insert - // has a single user, and that user is an insert, bail. +/// Turn a chain of inserts that splats a value into an insert + shuffle: +/// insertelt(insertelt(insertelt(insertelt X, %k, 0), %k, 1), %k, 2) ... -> +/// shufflevector(insertelt(X, %k, 0), undef, zero) +static Instruction *foldInsSequenceIntoSplat(InsertElementInst &InsElt) { + // We are interested in the last insert in a chain. So if this insert has a + // single user and that user is an insert, bail. if (InsElt.hasOneUse() && isa<InsertElementInst>(InsElt.user_back())) return nullptr; - VectorType *VT = cast<VectorType>(InsElt.getType()); - int NumElements = VT->getNumElements(); + auto *VecTy = cast<VectorType>(InsElt.getType()); + unsigned NumElements = VecTy->getNumElements(); // Do not try to do this for a one-element vector, since that's a nop, // and will cause an inf-loop. @@ -706,24 +704,66 @@ static Instruction *foldInsSequenceIntoBroadcast(InsertElementInst &InsElt) { CurrIE = NextIE; } - // Make sure we've seen an insert into every element. - if (llvm::any_of(ElementPresent, [](bool Present) { return !Present; })) + // If this is just a single insertelement (not a sequence), we are done. + if (FirstIE == &InsElt) return nullptr; - // All right, create the insert + shuffle. - Instruction *InsertFirst; - if (cast<ConstantInt>(FirstIE->getOperand(2))->isZero()) - InsertFirst = FirstIE; - else - InsertFirst = InsertElementInst::Create( - UndefValue::get(VT), SplatVal, - ConstantInt::get(Type::getInt32Ty(InsElt.getContext()), 0), - "", &InsElt); + // If we are not inserting into an undef vector, make sure we've seen an + // insert into every element. + // TODO: If the base vector is not undef, it might be better to create a splat + // and then a select-shuffle (blend) with the base vector. + if (!isa<UndefValue>(FirstIE->getOperand(0))) + if (any_of(ElementPresent, [](bool Present) { return !Present; })) + return nullptr; + + // Create the insert + shuffle. + Type *Int32Ty = Type::getInt32Ty(InsElt.getContext()); + UndefValue *UndefVec = UndefValue::get(VecTy); + Constant *Zero = ConstantInt::get(Int32Ty, 0); + if (!cast<ConstantInt>(FirstIE->getOperand(2))->isZero()) + FirstIE = InsertElementInst::Create(UndefVec, SplatVal, Zero, "", &InsElt); + + // Splat from element 0, but replace absent elements with undef in the mask. + SmallVector<Constant *, 16> Mask(NumElements, Zero); + for (unsigned i = 0; i != NumElements; ++i) + if (!ElementPresent[i]) + Mask[i] = UndefValue::get(Int32Ty); + + return new ShuffleVectorInst(FirstIE, UndefVec, ConstantVector::get(Mask)); +} - Constant *ZeroMask = ConstantAggregateZero::get( - VectorType::get(Type::getInt32Ty(InsElt.getContext()), NumElements)); +/// Try to fold an insert element into an existing splat shuffle by changing +/// the shuffle's mask to include the index of this insert element. +static Instruction *foldInsEltIntoSplat(InsertElementInst &InsElt) { + // Check if the vector operand of this insert is a canonical splat shuffle. + auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0)); + if (!Shuf || !Shuf->isZeroEltSplat()) + return nullptr; + + // Check for a constant insertion index. + uint64_t IdxC; + if (!match(InsElt.getOperand(2), m_ConstantInt(IdxC))) + return nullptr; - return new ShuffleVectorInst(InsertFirst, UndefValue::get(VT), ZeroMask); + // Check if the splat shuffle's input is the same as this insert's scalar op. + Value *X = InsElt.getOperand(1); + Value *Op0 = Shuf->getOperand(0); + if (!match(Op0, m_InsertElement(m_Undef(), m_Specific(X), m_ZeroInt()))) + return nullptr; + + // Replace the shuffle mask element at the index of this insert with a zero. + // For example: + // inselt (shuf (inselt undef, X, 0), undef, <0,undef,0,undef>), X, 1 + // --> shuf (inselt undef, X, 0), undef, <0,0,0,undef> + unsigned NumMaskElts = Shuf->getType()->getVectorNumElements(); + SmallVector<Constant *, 16> NewMaskVec(NumMaskElts); + Type *I32Ty = IntegerType::getInt32Ty(Shuf->getContext()); + Constant *Zero = ConstantInt::getNullValue(I32Ty); + for (unsigned i = 0; i != NumMaskElts; ++i) + NewMaskVec[i] = i == IdxC ? Zero : Shuf->getMask()->getAggregateElement(i); + + Constant *NewMask = ConstantVector::get(NewMaskVec); + return new ShuffleVectorInst(Op0, UndefValue::get(Op0->getType()), NewMask); } /// If we have an insertelement instruction feeding into another insertelement @@ -864,30 +904,28 @@ Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) { VecOp, ScalarOp, IdxOp, SQ.getWithInstruction(&IE))) return replaceInstUsesWith(IE, V); - // Inserting an undef or into an undefined place, remove this. - if (isa<UndefValue>(ScalarOp) || isa<UndefValue>(IdxOp)) - replaceInstUsesWith(IE, VecOp); + // If the vector and scalar are both bitcast from the same element type, do + // the insert in that source type followed by bitcast. + Value *VecSrc, *ScalarSrc; + if (match(VecOp, m_BitCast(m_Value(VecSrc))) && + match(ScalarOp, m_BitCast(m_Value(ScalarSrc))) && + (VecOp->hasOneUse() || ScalarOp->hasOneUse()) && + VecSrc->getType()->isVectorTy() && !ScalarSrc->getType()->isVectorTy() && + VecSrc->getType()->getVectorElementType() == ScalarSrc->getType()) { + // inselt (bitcast VecSrc), (bitcast ScalarSrc), IdxOp --> + // bitcast (inselt VecSrc, ScalarSrc, IdxOp) + Value *NewInsElt = Builder.CreateInsertElement(VecSrc, ScalarSrc, IdxOp); + return new BitCastInst(NewInsElt, IE.getType()); + } // If the inserted element was extracted from some other vector and both - // indexes are constant, try to turn this into a shuffle. + // indexes are valid constants, try to turn this into a shuffle. uint64_t InsertedIdx, ExtractedIdx; Value *ExtVecOp; if (match(IdxOp, m_ConstantInt(InsertedIdx)) && match(ScalarOp, m_ExtractElement(m_Value(ExtVecOp), - m_ConstantInt(ExtractedIdx)))) { - unsigned NumInsertVectorElts = IE.getType()->getNumElements(); - unsigned NumExtractVectorElts = ExtVecOp->getType()->getVectorNumElements(); - if (ExtractedIdx >= NumExtractVectorElts) // Out of range extract. - return replaceInstUsesWith(IE, VecOp); - - if (InsertedIdx >= NumInsertVectorElts) // Out of range insert. - return replaceInstUsesWith(IE, UndefValue::get(IE.getType())); - - // If we are extracting a value from a vector, then inserting it right - // back into the same place, just use the input vector. - if (ExtVecOp == VecOp && ExtractedIdx == InsertedIdx) - return replaceInstUsesWith(IE, VecOp); - + m_ConstantInt(ExtractedIdx))) && + ExtractedIdx < ExtVecOp->getType()->getVectorNumElements()) { // TODO: Looking at the user(s) to determine if this insert is a // fold-to-shuffle opportunity does not match the usual instcombine // constraints. We should decide if the transform is worthy based only @@ -943,11 +981,12 @@ Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) { if (Instruction *NewInsElt = hoistInsEltConst(IE, Builder)) return NewInsElt; - // Turn a sequence of inserts that broadcasts a scalar into a single - // insert + shufflevector. - if (Instruction *Broadcast = foldInsSequenceIntoBroadcast(IE)) + if (Instruction *Broadcast = foldInsSequenceIntoSplat(IE)) return Broadcast; + if (Instruction *Splat = foldInsEltIntoSplat(IE)) + return Splat; + return nullptr; } @@ -1172,7 +1211,14 @@ static Value *evaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask) { SmallVector<Value*, 8> NewOps; bool NeedsRebuild = (Mask.size() != I->getType()->getVectorNumElements()); for (int i = 0, e = I->getNumOperands(); i != e; ++i) { - Value *V = evaluateInDifferentElementOrder(I->getOperand(i), Mask); + Value *V; + // Recursively call evaluateInDifferentElementOrder on vector arguments + // as well. E.g. GetElementPtr may have scalar operands even if the + // return value is a vector, so we need to examine the operand type. + if (I->getOperand(i)->getType()->isVectorTy()) + V = evaluateInDifferentElementOrder(I->getOperand(i), Mask); + else + V = I->getOperand(i); NewOps.push_back(V); NeedsRebuild |= (V != I->getOperand(i)); } @@ -1337,6 +1383,41 @@ static Instruction *foldSelectShuffleWith1Binop(ShuffleVectorInst &Shuf) { return NewBO; } +/// If we have an insert of a scalar to a non-zero element of an undefined +/// vector and then shuffle that value, that's the same as inserting to the zero +/// element and shuffling. Splatting from the zero element is recognized as the +/// canonical form of splat. +static Instruction *canonicalizeInsertSplat(ShuffleVectorInst &Shuf, + InstCombiner::BuilderTy &Builder) { + Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1); + Constant *Mask = Shuf.getMask(); + Value *X; + uint64_t IndexC; + + // Match a shuffle that is a splat to a non-zero element. + if (!match(Op0, m_OneUse(m_InsertElement(m_Undef(), m_Value(X), + m_ConstantInt(IndexC)))) || + !match(Op1, m_Undef()) || match(Mask, m_ZeroInt()) || IndexC == 0) + return nullptr; + + // Insert into element 0 of an undef vector. + UndefValue *UndefVec = UndefValue::get(Shuf.getType()); + Constant *Zero = Builder.getInt32(0); + Value *NewIns = Builder.CreateInsertElement(UndefVec, X, Zero); + + // Splat from element 0. Any mask element that is undefined remains undefined. + // For example: + // shuf (inselt undef, X, 2), undef, <2,2,undef> + // --> shuf (inselt undef, X, 0), undef, <0,0,undef> + unsigned NumMaskElts = Shuf.getType()->getVectorNumElements(); + SmallVector<Constant *, 16> NewMask(NumMaskElts, Zero); + for (unsigned i = 0; i != NumMaskElts; ++i) + if (isa<UndefValue>(Mask->getAggregateElement(i))) + NewMask[i] = Mask->getAggregateElement(i); + + return new ShuffleVectorInst(NewIns, UndefVec, ConstantVector::get(NewMask)); +} + /// Try to fold shuffles that are the equivalent of a vector select. static Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf, InstCombiner::BuilderTy &Builder, @@ -1344,6 +1425,15 @@ static Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf, if (!Shuf.isSelect()) return nullptr; + // Canonicalize to choose from operand 0 first. + unsigned NumElts = Shuf.getType()->getVectorNumElements(); + if (Shuf.getMaskValue(0) >= (int)NumElts) { + // TODO: Can we assert that both operands of a shuffle-select are not undef + // (otherwise, it would have been folded by instsimplify? + Shuf.commute(); + return &Shuf; + } + if (Instruction *I = foldSelectShuffleWith1Binop(Shuf)) return I; @@ -1499,6 +1589,11 @@ static Instruction *foldIdentityExtractShuffle(ShuffleVectorInst &Shuf) { if (!match(Op0, m_ShuffleVector(m_Value(X), m_Value(Y), m_Constant(Mask)))) return nullptr; + // Be conservative with shuffle transforms. If we can't kill the 1st shuffle, + // then combining may result in worse codegen. + if (!Op0->hasOneUse()) + return nullptr; + // We are extracting a subvector from a shuffle. Remove excess elements from // the 1st shuffle mask to eliminate the extract. // @@ -1588,6 +1683,72 @@ static Instruction *foldShuffleWithInsert(ShuffleVectorInst &Shuf) { return nullptr; } +static Instruction *foldIdentityPaddedShuffles(ShuffleVectorInst &Shuf) { + // Match the operands as identity with padding (also known as concatenation + // with undef) shuffles of the same source type. The backend is expected to + // recreate these concatenations from a shuffle of narrow operands. + auto *Shuffle0 = dyn_cast<ShuffleVectorInst>(Shuf.getOperand(0)); + auto *Shuffle1 = dyn_cast<ShuffleVectorInst>(Shuf.getOperand(1)); + if (!Shuffle0 || !Shuffle0->isIdentityWithPadding() || + !Shuffle1 || !Shuffle1->isIdentityWithPadding()) + return nullptr; + + // We limit this transform to power-of-2 types because we expect that the + // backend can convert the simplified IR patterns to identical nodes as the + // original IR. + // TODO: If we can verify the same behavior for arbitrary types, the + // power-of-2 checks can be removed. + Value *X = Shuffle0->getOperand(0); + Value *Y = Shuffle1->getOperand(0); + if (X->getType() != Y->getType() || + !isPowerOf2_32(Shuf.getType()->getVectorNumElements()) || + !isPowerOf2_32(Shuffle0->getType()->getVectorNumElements()) || + !isPowerOf2_32(X->getType()->getVectorNumElements()) || + isa<UndefValue>(X) || isa<UndefValue>(Y)) + return nullptr; + assert(isa<UndefValue>(Shuffle0->getOperand(1)) && + isa<UndefValue>(Shuffle1->getOperand(1)) && + "Unexpected operand for identity shuffle"); + + // This is a shuffle of 2 widening shuffles. We can shuffle the narrow source + // operands directly by adjusting the shuffle mask to account for the narrower + // types: + // shuf (widen X), (widen Y), Mask --> shuf X, Y, Mask' + int NarrowElts = X->getType()->getVectorNumElements(); + int WideElts = Shuffle0->getType()->getVectorNumElements(); + assert(WideElts > NarrowElts && "Unexpected types for identity with padding"); + + Type *I32Ty = IntegerType::getInt32Ty(Shuf.getContext()); + SmallVector<int, 16> Mask = Shuf.getShuffleMask(); + SmallVector<Constant *, 16> NewMask(Mask.size(), UndefValue::get(I32Ty)); + for (int i = 0, e = Mask.size(); i != e; ++i) { + if (Mask[i] == -1) + continue; + + // If this shuffle is choosing an undef element from 1 of the sources, that + // element is undef. + if (Mask[i] < WideElts) { + if (Shuffle0->getMaskValue(Mask[i]) == -1) + continue; + } else { + if (Shuffle1->getMaskValue(Mask[i] - WideElts) == -1) + continue; + } + + // If this shuffle is choosing from the 1st narrow op, the mask element is + // the same. If this shuffle is choosing from the 2nd narrow op, the mask + // element is offset down to adjust for the narrow vector widths. + if (Mask[i] < WideElts) { + assert(Mask[i] < NarrowElts && "Unexpected shuffle mask"); + NewMask[i] = ConstantInt::get(I32Ty, Mask[i]); + } else { + assert(Mask[i] < (WideElts + NarrowElts) && "Unexpected shuffle mask"); + NewMask[i] = ConstantInt::get(I32Ty, Mask[i] - (WideElts - NarrowElts)); + } + } + return new ShuffleVectorInst(X, Y, ConstantVector::get(NewMask)); +} + Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) { Value *LHS = SVI.getOperand(0); Value *RHS = SVI.getOperand(1); @@ -1595,36 +1756,12 @@ Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) { LHS, RHS, SVI.getMask(), SVI.getType(), SQ.getWithInstruction(&SVI))) return replaceInstUsesWith(SVI, V); - if (Instruction *I = foldSelectShuffle(SVI, Builder, DL)) - return I; - - if (Instruction *I = narrowVectorSelect(SVI, Builder)) - return I; - + // Canonicalize shuffle(x ,x,mask) -> shuffle(x, undef,mask') + // Canonicalize shuffle(undef,x,mask) -> shuffle(x, undef,mask'). unsigned VWidth = SVI.getType()->getVectorNumElements(); - APInt UndefElts(VWidth, 0); - APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth)); - if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) { - if (V != &SVI) - return replaceInstUsesWith(SVI, V); - return &SVI; - } - - if (Instruction *I = foldIdentityExtractShuffle(SVI)) - return I; - - // This transform has the potential to lose undef knowledge, so it is - // intentionally placed after SimplifyDemandedVectorElts(). - if (Instruction *I = foldShuffleWithInsert(SVI)) - return I; - + unsigned LHSWidth = LHS->getType()->getVectorNumElements(); SmallVector<int, 16> Mask = SVI.getShuffleMask(); Type *Int32Ty = Type::getInt32Ty(SVI.getContext()); - unsigned LHSWidth = LHS->getType()->getVectorNumElements(); - bool MadeChange = false; - - // Canonicalize shuffle(x ,x,mask) -> shuffle(x, undef,mask') - // Canonicalize shuffle(undef,x,mask) -> shuffle(x, undef,mask'). if (LHS == RHS || isa<UndefValue>(LHS)) { // Remap any references to RHS to use LHS. SmallVector<Constant*, 16> Elts; @@ -1646,11 +1783,36 @@ Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) { SVI.setOperand(0, SVI.getOperand(1)); SVI.setOperand(1, UndefValue::get(RHS->getType())); SVI.setOperand(2, ConstantVector::get(Elts)); - LHS = SVI.getOperand(0); - RHS = SVI.getOperand(1); - MadeChange = true; + return &SVI; + } + + if (Instruction *I = canonicalizeInsertSplat(SVI, Builder)) + return I; + + if (Instruction *I = foldSelectShuffle(SVI, Builder, DL)) + return I; + + if (Instruction *I = narrowVectorSelect(SVI, Builder)) + return I; + + APInt UndefElts(VWidth, 0); + APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth)); + if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) { + if (V != &SVI) + return replaceInstUsesWith(SVI, V); + return &SVI; } + if (Instruction *I = foldIdentityExtractShuffle(SVI)) + return I; + + // These transforms have the potential to lose undef knowledge, so they are + // intentionally placed after SimplifyDemandedVectorElts(). + if (Instruction *I = foldShuffleWithInsert(SVI)) + return I; + if (Instruction *I = foldIdentityPaddedShuffles(SVI)) + return I; + if (VWidth == LHSWidth) { // Analyze the shuffle, are the LHS or RHS and identity shuffles? bool isLHSID, isRHSID; @@ -1695,6 +1857,7 @@ Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) { // +-----------+-----------+-----------+-----------+ // Index range [6,10): ^-----------^ Needs an extra shuffle. // Target type i40: ^--------------^ Won't work, bail. + bool MadeChange = false; if (isShuffleExtractingFromLHS(SVI, Mask)) { Value *V = LHS; unsigned MaskElems = Mask.size(); diff --git a/lib/Transforms/InstCombine/InstructionCombining.cpp b/lib/Transforms/InstCombine/InstructionCombining.cpp index be7d43bbcf2c3..385f4926b845a 100644 --- a/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -1,9 +1,8 @@ //===- InstructionCombining.cpp - Combine multiple instructions -----------===// // -// 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 // //===----------------------------------------------------------------------===// // @@ -47,14 +46,17 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/BasicAliasAnalysis.h" +#include "llvm/Analysis/BlockFrequencyInfo.h" #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/EHPersonalities.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/LazyBlockFrequencyInfo.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" +#include "llvm/Analysis/ProfileSummaryInfo.h" #include "llvm/Analysis/TargetFolder.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueTracking.h" @@ -221,6 +223,11 @@ static bool MaintainNoSignedWrap(BinaryOperator &I, Value *B, Value *C) { return !Overflow; } +static bool hasNoUnsignedWrap(BinaryOperator &I) { + OverflowingBinaryOperator *OBO = dyn_cast<OverflowingBinaryOperator>(&I); + return OBO && OBO->hasNoUnsignedWrap(); +} + /// Conservatively clears subclassOptionalData after a reassociation or /// commutation. We preserve fast-math flags when applicable as they can be /// preserved. @@ -327,14 +334,19 @@ bool InstCombiner::SimplifyAssociativeOrCommutative(BinaryOperator &I) { I.setOperand(1, V); // Conservatively clear the optional flags, since they may not be // preserved by the reassociation. - if (MaintainNoSignedWrap(I, B, C) && + bool IsNUW = hasNoUnsignedWrap(I) && hasNoUnsignedWrap(*Op0); + bool IsNSW = MaintainNoSignedWrap(I, B, C); + + ClearSubclassDataAfterReassociation(I); + + if (IsNUW) + I.setHasNoUnsignedWrap(true); + + if (IsNSW && (!Op0 || (isa<BinaryOperator>(Op0) && Op0->hasNoSignedWrap()))) { // Note: this is only valid because SimplifyBinOp doesn't look at // the operands to Op0. - I.clearSubclassOptionalData(); I.setHasNoSignedWrap(true); - } else { - ClearSubclassDataAfterReassociation(I); } Changed = true; @@ -419,8 +431,14 @@ bool InstCombiner::SimplifyAssociativeOrCommutative(BinaryOperator &I) { Op0->getOpcode() == Opcode && Op1->getOpcode() == Opcode && match(Op0, m_OneUse(m_BinOp(m_Value(A), m_Constant(C1)))) && match(Op1, m_OneUse(m_BinOp(m_Value(B), m_Constant(C2))))) { - BinaryOperator *NewBO = BinaryOperator::Create(Opcode, A, B); - if (isa<FPMathOperator>(NewBO)) { + bool IsNUW = hasNoUnsignedWrap(I) && + hasNoUnsignedWrap(*Op0) && + hasNoUnsignedWrap(*Op1); + BinaryOperator *NewBO = (IsNUW && Opcode == Instruction::Add) ? + BinaryOperator::CreateNUW(Opcode, A, B) : + BinaryOperator::Create(Opcode, A, B); + + if (isa<FPMathOperator>(NewBO)) { FastMathFlags Flags = I.getFastMathFlags(); Flags &= Op0->getFastMathFlags(); Flags &= Op1->getFastMathFlags(); @@ -433,6 +451,8 @@ bool InstCombiner::SimplifyAssociativeOrCommutative(BinaryOperator &I) { // Conservatively clear the optional flags, since they may not be // preserved by the reassociation. ClearSubclassDataAfterReassociation(I); + if (IsNUW) + I.setHasNoUnsignedWrap(true); Changed = true; continue; @@ -570,32 +590,44 @@ Value *InstCombiner::tryFactorization(BinaryOperator &I, ++NumFactor; SimplifiedInst->takeName(&I); - // Check if we can add NSW flag to SimplifiedInst. If so, set NSW flag. - // TODO: Check for NUW. + // Check if we can add NSW/NUW flags to SimplifiedInst. If so, set them. if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SimplifiedInst)) { if (isa<OverflowingBinaryOperator>(SimplifiedInst)) { bool HasNSW = false; - if (isa<OverflowingBinaryOperator>(&I)) + bool HasNUW = false; + if (isa<OverflowingBinaryOperator>(&I)) { HasNSW = I.hasNoSignedWrap(); + HasNUW = I.hasNoUnsignedWrap(); + } - if (auto *LOBO = dyn_cast<OverflowingBinaryOperator>(LHS)) + if (auto *LOBO = dyn_cast<OverflowingBinaryOperator>(LHS)) { HasNSW &= LOBO->hasNoSignedWrap(); + HasNUW &= LOBO->hasNoUnsignedWrap(); + } - if (auto *ROBO = dyn_cast<OverflowingBinaryOperator>(RHS)) + if (auto *ROBO = dyn_cast<OverflowingBinaryOperator>(RHS)) { HasNSW &= ROBO->hasNoSignedWrap(); + HasNUW &= ROBO->hasNoUnsignedWrap(); + } - // We can propagate 'nsw' if we know that - // %Y = mul nsw i16 %X, C - // %Z = add nsw i16 %Y, %X - // => - // %Z = mul nsw i16 %X, C+1 - // - // iff C+1 isn't INT_MIN const APInt *CInt; if (TopLevelOpcode == Instruction::Add && - InnerOpcode == Instruction::Mul) - if (match(V, m_APInt(CInt)) && !CInt->isMinSignedValue()) - BO->setHasNoSignedWrap(HasNSW); + InnerOpcode == Instruction::Mul) { + // We can propagate 'nsw' if we know that + // %Y = mul nsw i16 %X, C + // %Z = add nsw i16 %Y, %X + // => + // %Z = mul nsw i16 %X, C+1 + // + // iff C+1 isn't INT_MIN + if (match(V, m_APInt(CInt))) { + if (!CInt->isMinSignedValue()) + BO->setHasNoSignedWrap(HasNSW); + } + + // nuw can be propagated with any constant or nuw value. + BO->setHasNoUnsignedWrap(HasNUW); + } } } } @@ -922,8 +954,8 @@ Instruction *InstCombiner::foldOpIntoPhi(Instruction &I, PHINode *PN) { // If the InVal is an invoke at the end of the pred block, then we can't // insert a computation after it without breaking the edge. - if (InvokeInst *II = dyn_cast<InvokeInst>(InVal)) - if (II->getParent() == NonConstBB) + if (isa<InvokeInst>(InVal)) + if (cast<Instruction>(InVal)->getParent() == NonConstBB) return nullptr; // If the incoming non-constant value is in I's block, we will remove one @@ -1376,7 +1408,8 @@ Instruction *InstCombiner::foldVectorBinop(BinaryOperator &Inst) { if (match(LHS, m_ShuffleVector(m_Value(L0), m_Value(L1), m_Constant(Mask))) && match(RHS, m_ShuffleVector(m_Value(R0), m_Value(R1), m_Specific(Mask))) && LHS->hasOneUse() && RHS->hasOneUse() && - cast<ShuffleVectorInst>(LHS)->isConcat()) { + cast<ShuffleVectorInst>(LHS)->isConcat() && + cast<ShuffleVectorInst>(RHS)->isConcat()) { // This transform does not have the speculative execution constraint as // below because the shuffle is a concatenation. The new binops are // operating on exactly the same elements as the existing binop. @@ -1415,6 +1448,30 @@ Instruction *InstCombiner::foldVectorBinop(BinaryOperator &Inst) { return createBinOpShuffle(V1, V2, Mask); } + // If both arguments of a commutative binop are select-shuffles that use the + // same mask with commuted operands, the shuffles are unnecessary. + if (Inst.isCommutative() && + match(LHS, m_ShuffleVector(m_Value(V1), m_Value(V2), m_Constant(Mask))) && + match(RHS, m_ShuffleVector(m_Specific(V2), m_Specific(V1), + m_Specific(Mask)))) { + auto *LShuf = cast<ShuffleVectorInst>(LHS); + auto *RShuf = cast<ShuffleVectorInst>(RHS); + // TODO: Allow shuffles that contain undefs in the mask? + // That is legal, but it reduces undef knowledge. + // TODO: Allow arbitrary shuffles by shuffling after binop? + // That might be legal, but we have to deal with poison. + if (LShuf->isSelect() && !LShuf->getMask()->containsUndefElement() && + RShuf->isSelect() && !RShuf->getMask()->containsUndefElement()) { + // Example: + // LHS = shuffle V1, V2, <0, 5, 6, 3> + // RHS = shuffle V2, V1, <0, 5, 6, 3> + // LHS + RHS --> (V10+V20, V21+V11, V22+V12, V13+V23) --> V1 + V2 + Instruction *NewBO = BinaryOperator::Create(Opcode, V1, V2); + NewBO->copyIRFlags(&Inst); + return NewBO; + } + } + // If one argument is a shuffle within one vector and the other is a constant, // try moving the shuffle after the binary operation. This canonicalization // intends to move shuffles closer to other shuffles and binops closer to @@ -1557,6 +1614,23 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { if (Value *V = SimplifyGEPInst(GEPEltType, Ops, SQ.getWithInstruction(&GEP))) return replaceInstUsesWith(GEP, V); + // For vector geps, use the generic demanded vector support. + if (GEP.getType()->isVectorTy()) { + auto VWidth = GEP.getType()->getVectorNumElements(); + APInt UndefElts(VWidth, 0); + APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth)); + if (Value *V = SimplifyDemandedVectorElts(&GEP, AllOnesEltMask, + UndefElts)) { + if (V != &GEP) + return replaceInstUsesWith(GEP, V); + return &GEP; + } + + // TODO: 1) Scalarize splat operands, 2) scalarize entire instruction if + // possible (decide on canonical form for pointer broadcast), 3) exploit + // undef elements to decrease demanded bits + } + Value *PtrOp = GEP.getOperand(0); // Eliminate unneeded casts for indices, and replace indices which displace @@ -1755,9 +1829,9 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { // put NewSrc at same location as %src Builder.SetInsertPoint(cast<Instruction>(PtrOp)); auto *NewSrc = cast<GetElementPtrInst>( - Builder.CreateGEP(SO0, GO1, Src->getName())); + Builder.CreateGEP(GEPEltType, SO0, GO1, Src->getName())); NewSrc->setIsInBounds(Src->isInBounds()); - auto *NewGEP = GetElementPtrInst::Create(nullptr, NewSrc, {SO1}); + auto *NewGEP = GetElementPtrInst::Create(GEPEltType, NewSrc, {SO1}); NewGEP->setIsInBounds(GEP.isInBounds()); return NewGEP; } @@ -1881,6 +1955,8 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { if (StrippedPtr != PtrOp) { bool HasZeroPointerIndex = false; + Type *StrippedPtrEltTy = StrippedPtrTy->getElementType(); + if (auto *C = dyn_cast<ConstantInt>(GEP.getOperand(1))) HasZeroPointerIndex = C->isZero(); @@ -1894,11 +1970,11 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { if (HasZeroPointerIndex) { if (auto *CATy = dyn_cast<ArrayType>(GEPEltType)) { // GEP (bitcast i8* X to [0 x i8]*), i32 0, ... ? - if (CATy->getElementType() == StrippedPtrTy->getElementType()) { + if (CATy->getElementType() == StrippedPtrEltTy) { // -> GEP i8* X, ... SmallVector<Value*, 8> Idx(GEP.idx_begin()+1, GEP.idx_end()); GetElementPtrInst *Res = GetElementPtrInst::Create( - StrippedPtrTy->getElementType(), StrippedPtr, Idx, GEP.getName()); + StrippedPtrEltTy, StrippedPtr, Idx, GEP.getName()); Res->setIsInBounds(GEP.isInBounds()); if (StrippedPtrTy->getAddressSpace() == GEP.getAddressSpace()) return Res; @@ -1911,7 +1987,7 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { return new AddrSpaceCastInst(Builder.Insert(Res), GEPType); } - if (auto *XATy = dyn_cast<ArrayType>(StrippedPtrTy->getElementType())) { + if (auto *XATy = dyn_cast<ArrayType>(StrippedPtrEltTy)) { // GEP (bitcast [10 x i8]* X to [0 x i8]*), i32 0, ... ? if (CATy->getElementType() == XATy->getElementType()) { // -> GEP [10 x i8]* X, i32 0, ... @@ -1934,11 +2010,12 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { // %0 = GEP [10 x i8] addrspace(1)* X, ... // addrspacecast i8 addrspace(1)* %0 to i8* SmallVector<Value*, 8> Idx(GEP.idx_begin(), GEP.idx_end()); - Value *NewGEP = GEP.isInBounds() - ? Builder.CreateInBoundsGEP( - nullptr, StrippedPtr, Idx, GEP.getName()) - : Builder.CreateGEP(nullptr, StrippedPtr, Idx, - GEP.getName()); + Value *NewGEP = + GEP.isInBounds() + ? Builder.CreateInBoundsGEP(StrippedPtrEltTy, StrippedPtr, + Idx, GEP.getName()) + : Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, Idx, + GEP.getName()); return new AddrSpaceCastInst(NewGEP, GEPType); } } @@ -1947,17 +2024,17 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { // Transform things like: // %t = getelementptr i32* bitcast ([2 x i32]* %str to i32*), i32 %V // into: %t1 = getelementptr [2 x i32]* %str, i32 0, i32 %V; bitcast - Type *SrcEltTy = StrippedPtrTy->getElementType(); - if (SrcEltTy->isArrayTy() && - DL.getTypeAllocSize(SrcEltTy->getArrayElementType()) == + if (StrippedPtrEltTy->isArrayTy() && + DL.getTypeAllocSize(StrippedPtrEltTy->getArrayElementType()) == DL.getTypeAllocSize(GEPEltType)) { Type *IdxType = DL.getIndexType(GEPType); Value *Idx[2] = { Constant::getNullValue(IdxType), GEP.getOperand(1) }; Value *NewGEP = GEP.isInBounds() - ? Builder.CreateInBoundsGEP(nullptr, StrippedPtr, Idx, + ? Builder.CreateInBoundsGEP(StrippedPtrEltTy, StrippedPtr, Idx, GEP.getName()) - : Builder.CreateGEP(nullptr, StrippedPtr, Idx, GEP.getName()); + : Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, Idx, + GEP.getName()); // V and GEP are both pointer types --> BitCast return CastInst::CreatePointerBitCastOrAddrSpaceCast(NewGEP, GEPType); @@ -1967,11 +2044,11 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { // %V = mul i64 %N, 4 // %t = getelementptr i8* bitcast (i32* %arr to i8*), i32 %V // into: %t1 = getelementptr i32* %arr, i32 %N; bitcast - if (GEPEltType->isSized() && SrcEltTy->isSized()) { + if (GEPEltType->isSized() && StrippedPtrEltTy->isSized()) { // Check that changing the type amounts to dividing the index by a scale // factor. uint64_t ResSize = DL.getTypeAllocSize(GEPEltType); - uint64_t SrcSize = DL.getTypeAllocSize(SrcEltTy); + uint64_t SrcSize = DL.getTypeAllocSize(StrippedPtrEltTy); if (ResSize && SrcSize % ResSize == 0) { Value *Idx = GEP.getOperand(1); unsigned BitWidth = Idx->getType()->getPrimitiveSizeInBits(); @@ -1990,9 +2067,9 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { // GEP may not be "inbounds". Value *NewGEP = GEP.isInBounds() && NSW - ? Builder.CreateInBoundsGEP(nullptr, StrippedPtr, NewIdx, - GEP.getName()) - : Builder.CreateGEP(nullptr, StrippedPtr, NewIdx, + ? Builder.CreateInBoundsGEP(StrippedPtrEltTy, StrippedPtr, + NewIdx, GEP.getName()) + : Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, NewIdx, GEP.getName()); // The NewGEP must be pointer typed, so must the old one -> BitCast @@ -2006,13 +2083,13 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { // getelementptr i8* bitcast ([100 x double]* X to i8*), i32 %tmp // (where tmp = 8*tmp2) into: // getelementptr [100 x double]* %arr, i32 0, i32 %tmp2; bitcast - if (GEPEltType->isSized() && SrcEltTy->isSized() && - SrcEltTy->isArrayTy()) { + if (GEPEltType->isSized() && StrippedPtrEltTy->isSized() && + StrippedPtrEltTy->isArrayTy()) { // Check that changing to the array element type amounts to dividing the // index by a scale factor. uint64_t ResSize = DL.getTypeAllocSize(GEPEltType); uint64_t ArrayEltSize = - DL.getTypeAllocSize(SrcEltTy->getArrayElementType()); + DL.getTypeAllocSize(StrippedPtrEltTy->getArrayElementType()); if (ResSize && ArrayEltSize % ResSize == 0) { Value *Idx = GEP.getOperand(1); unsigned BitWidth = Idx->getType()->getPrimitiveSizeInBits(); @@ -2032,11 +2109,12 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { Type *IndTy = DL.getIndexType(GEPType); Value *Off[2] = {Constant::getNullValue(IndTy), NewIdx}; - Value *NewGEP = GEP.isInBounds() && NSW - ? Builder.CreateInBoundsGEP( - SrcEltTy, StrippedPtr, Off, GEP.getName()) - : Builder.CreateGEP(SrcEltTy, StrippedPtr, Off, - GEP.getName()); + Value *NewGEP = + GEP.isInBounds() && NSW + ? Builder.CreateInBoundsGEP(StrippedPtrEltTy, StrippedPtr, + Off, GEP.getName()) + : Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, Off, + GEP.getName()); // The NewGEP must be pointer typed, so must the old one -> BitCast return CastInst::CreatePointerBitCastOrAddrSpaceCast(NewGEP, GEPType); @@ -2084,8 +2162,8 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { // constructing an AddrSpaceCastInst Value *NGEP = GEP.isInBounds() - ? Builder.CreateInBoundsGEP(nullptr, SrcOp, {Ops[1], Ops[2]}) - : Builder.CreateGEP(nullptr, SrcOp, {Ops[1], Ops[2]}); + ? Builder.CreateInBoundsGEP(SrcEltType, SrcOp, {Ops[1], Ops[2]}) + : Builder.CreateGEP(SrcEltType, SrcOp, {Ops[1], Ops[2]}); NGEP->takeName(&GEP); // Preserve GEP address space to satisfy users @@ -2132,8 +2210,8 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { if (FindElementAtOffset(SrcType, Offset.getSExtValue(), NewIndices)) { Value *NGEP = GEP.isInBounds() - ? Builder.CreateInBoundsGEP(nullptr, SrcOp, NewIndices) - : Builder.CreateGEP(nullptr, SrcOp, NewIndices); + ? Builder.CreateInBoundsGEP(SrcEltType, SrcOp, NewIndices) + : Builder.CreateGEP(SrcEltType, SrcOp, NewIndices); if (NGEP->getType() == GEPType) return replaceInstUsesWith(GEP, NGEP); @@ -2159,7 +2237,8 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { APInt AllocSize(IdxWidth, DL.getTypeAllocSize(AI->getAllocatedType())); if (BasePtrOffset.ule(AllocSize)) { return GetElementPtrInst::CreateInBounds( - PtrOp, makeArrayRef(Ops).slice(1), GEP.getName()); + GEP.getSourceElementType(), PtrOp, makeArrayRef(Ops).slice(1), + GEP.getName()); } } } @@ -2296,8 +2375,8 @@ Instruction *InstCombiner::visitAllocSite(Instruction &MI) { if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { if (II->getIntrinsicID() == Intrinsic::objectsize) { - ConstantInt *Result = lowerObjectSizeCall(II, DL, &TLI, - /*MustSucceed=*/true); + Value *Result = + lowerObjectSizeCall(II, DL, &TLI, /*MustSucceed=*/true); replaceInstUsesWith(*I, Result); eraseInstFromFunction(*I); Users[i] = nullptr; // Skip examining in the next loop. @@ -2426,9 +2505,8 @@ Instruction *InstCombiner::visitFree(CallInst &FI) { // free undef -> unreachable. if (isa<UndefValue>(Op)) { - // Insert a new store to null because we cannot modify the CFG here. - Builder.CreateStore(ConstantInt::getTrue(FI.getContext()), - UndefValue::get(Type::getInt1PtrTy(FI.getContext()))); + // Leave a marker since we can't modify the CFG here. + CreateNonTerminatorUnreachable(&FI); return eraseInstFromFunction(FI); } @@ -2618,53 +2696,28 @@ Instruction *InstCombiner::visitExtractValueInst(ExtractValueInst &EV) { return ExtractValueInst::Create(IV->getInsertedValueOperand(), makeArrayRef(exti, exte)); } - if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Agg)) { - // We're extracting from an intrinsic, see if we're the only user, which - // allows us to simplify multiple result intrinsics to simpler things that - // just get one value. - if (II->hasOneUse()) { - // Check if we're grabbing the overflow bit or the result of a 'with - // overflow' intrinsic. If it's the latter we can remove the intrinsic + if (WithOverflowInst *WO = dyn_cast<WithOverflowInst>(Agg)) { + // We're extracting from an overflow intrinsic, see if we're the only user, + // which allows us to simplify multiple result intrinsics to simpler + // things that just get one value. + if (WO->hasOneUse()) { + // Check if we're grabbing only the result of a 'with overflow' intrinsic // and replace it with a traditional binary instruction. - switch (II->getIntrinsicID()) { - case Intrinsic::uadd_with_overflow: - case Intrinsic::sadd_with_overflow: - if (*EV.idx_begin() == 0) { // Normal result. - Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1); - replaceInstUsesWith(*II, UndefValue::get(II->getType())); - eraseInstFromFunction(*II); - return BinaryOperator::CreateAdd(LHS, RHS); - } - - // If the normal result of the add is dead, and the RHS is a constant, - // we can transform this into a range comparison. - // overflow = uadd a, -4 --> overflow = icmp ugt a, 3 - if (II->getIntrinsicID() == Intrinsic::uadd_with_overflow) - if (ConstantInt *CI = dyn_cast<ConstantInt>(II->getArgOperand(1))) - return new ICmpInst(ICmpInst::ICMP_UGT, II->getArgOperand(0), - ConstantExpr::getNot(CI)); - break; - case Intrinsic::usub_with_overflow: - case Intrinsic::ssub_with_overflow: - if (*EV.idx_begin() == 0) { // Normal result. - Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1); - replaceInstUsesWith(*II, UndefValue::get(II->getType())); - eraseInstFromFunction(*II); - return BinaryOperator::CreateSub(LHS, RHS); - } - break; - case Intrinsic::umul_with_overflow: - case Intrinsic::smul_with_overflow: - if (*EV.idx_begin() == 0) { // Normal result. - Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1); - replaceInstUsesWith(*II, UndefValue::get(II->getType())); - eraseInstFromFunction(*II); - return BinaryOperator::CreateMul(LHS, RHS); - } - break; - default: - break; + if (*EV.idx_begin() == 0) { + Instruction::BinaryOps BinOp = WO->getBinaryOp(); + Value *LHS = WO->getLHS(), *RHS = WO->getRHS(); + replaceInstUsesWith(*WO, UndefValue::get(WO->getType())); + eraseInstFromFunction(*WO); + return BinaryOperator::Create(BinOp, LHS, RHS); } + + // If the normal result of the add is dead, and the RHS is a constant, + // we can transform this into a range comparison. + // overflow = uadd a, -4 --> overflow = icmp ugt a, 3 + if (WO->getIntrinsicID() == Intrinsic::uadd_with_overflow) + if (ConstantInt *CI = dyn_cast<ConstantInt>(WO->getRHS())) + return new ICmpInst(ICmpInst::ICMP_UGT, WO->getLHS(), + ConstantExpr::getNot(CI)); } } if (LoadInst *L = dyn_cast<LoadInst>(Agg)) @@ -2687,7 +2740,7 @@ Instruction *InstCombiner::visitExtractValueInst(ExtractValueInst &EV) { Builder.SetInsertPoint(L); Value *GEP = Builder.CreateInBoundsGEP(L->getType(), L->getPointerOperand(), Indices); - Instruction *NL = Builder.CreateLoad(GEP); + Instruction *NL = Builder.CreateLoad(EV.getType(), GEP); // Whatever aliasing information we had for the orignal load must also // hold for the smaller load, so propagate the annotations. AAMDNodes Nodes; @@ -3065,9 +3118,11 @@ static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) { I->isTerminator()) return false; - // Do not sink alloca instructions out of the entry block. - if (isa<AllocaInst>(I) && I->getParent() == - &DestBlock->getParent()->getEntryBlock()) + // Do not sink static or dynamic alloca instructions. Static allocas must + // remain in the entry block, and dynamic allocas must not be sunk in between + // a stacksave / stackrestore pair, which would incorrectly shorten its + // lifetime. + if (isa<AllocaInst>(I)) return false; // Do not sink into catchswitch blocks. @@ -3093,13 +3148,35 @@ static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) { ++NumSunkInst; // Also sink all related debug uses from the source basic block. Otherwise we - // get debug use before the def. - SmallVector<DbgVariableIntrinsic *, 1> DbgUsers; + // get debug use before the def. Attempt to salvage debug uses first, to + // maximise the range variables have location for. If we cannot salvage, then + // mark the location undef: we know it was supposed to receive a new location + // here, but that computation has been sunk. + SmallVector<DbgVariableIntrinsic *, 2> DbgUsers; findDbgUsers(DbgUsers, I); - for (auto *DII : DbgUsers) { + for (auto *DII : reverse(DbgUsers)) { if (DII->getParent() == SrcBlock) { - DII->moveBefore(&*InsertPos); - LLVM_DEBUG(dbgs() << "SINK: " << *DII << '\n'); + // dbg.value is in the same basic block as the sunk inst, see if we can + // salvage it. Clone a new copy of the instruction: on success we need + // both salvaged and unsalvaged copies. + SmallVector<DbgVariableIntrinsic *, 1> TmpUser{ + cast<DbgVariableIntrinsic>(DII->clone())}; + + if (!salvageDebugInfoForDbgValues(*I, TmpUser)) { + // We are unable to salvage: sink the cloned dbg.value, and mark the + // original as undef, terminating any earlier variable location. + LLVM_DEBUG(dbgs() << "SINK: " << *DII << '\n'); + TmpUser[0]->insertBefore(&*InsertPos); + Value *Undef = UndefValue::get(I->getType()); + DII->setOperand(0, MetadataAsValue::get(DII->getContext(), + ValueAsMetadata::get(Undef))); + } else { + // We successfully salvaged: place the salvaged dbg.value in the + // original location, and move the unmodified dbg.value to sink with + // the sunk inst. + TmpUser[0]->insertBefore(DII); + DII->moveBefore(&*InsertPos); + } } } return true; @@ -3294,7 +3371,8 @@ static bool AddReachableCodeToWorklist(BasicBlock *BB, const DataLayout &DL, if (isInstructionTriviallyDead(Inst, TLI)) { ++NumDeadInst; LLVM_DEBUG(dbgs() << "IC: DCE: " << *Inst << '\n'); - salvageDebugInfo(*Inst); + if (!salvageDebugInfo(*Inst)) + replaceDbgUsesWithUndef(Inst); Inst->eraseFromParent(); MadeIRChange = true; continue; @@ -3407,7 +3485,8 @@ static bool prepareICWorklistFromFunction(Function &F, const DataLayout &DL, static bool combineInstructionsOverFunction( Function &F, InstCombineWorklist &Worklist, AliasAnalysis *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT, - OptimizationRemarkEmitter &ORE, bool ExpensiveCombines = true, + OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, + ProfileSummaryInfo *PSI, bool ExpensiveCombines = true, LoopInfo *LI = nullptr) { auto &DL = F.getParent()->getDataLayout(); ExpensiveCombines |= EnableExpensiveCombines; @@ -3437,8 +3516,8 @@ static bool combineInstructionsOverFunction( MadeIRChange |= prepareICWorklistFromFunction(F, DL, &TLI, Worklist); - InstCombiner IC(Worklist, Builder, F.optForMinSize(), ExpensiveCombines, AA, - AC, TLI, DT, ORE, DL, LI); + InstCombiner IC(Worklist, Builder, F.hasMinSize(), ExpensiveCombines, AA, + AC, TLI, DT, ORE, BFI, PSI, DL, LI); IC.MaxArraySizeForCombine = MaxArraySize; if (!IC.run()) @@ -3458,8 +3537,15 @@ PreservedAnalyses InstCombinePass::run(Function &F, auto *LI = AM.getCachedResult<LoopAnalysis>(F); auto *AA = &AM.getResult<AAManager>(F); + const ModuleAnalysisManager &MAM = + AM.getResult<ModuleAnalysisManagerFunctionProxy>(F).getManager(); + ProfileSummaryInfo *PSI = + MAM.getCachedResult<ProfileSummaryAnalysis>(*F.getParent()); + auto *BFI = (PSI && PSI->hasProfileSummary()) ? + &AM.getResult<BlockFrequencyAnalysis>(F) : nullptr; + if (!combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, DT, ORE, - ExpensiveCombines, LI)) + BFI, PSI, ExpensiveCombines, LI)) // No changes, all analyses are preserved. return PreservedAnalyses::all(); @@ -3483,6 +3569,8 @@ void InstructionCombiningPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.addPreserved<AAResultsWrapperPass>(); AU.addPreserved<BasicAAWrapperPass>(); AU.addPreserved<GlobalsAAWrapperPass>(); + AU.addRequired<ProfileSummaryInfoWrapperPass>(); + LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU); } bool InstructionCombiningPass::runOnFunction(Function &F) { @@ -3499,9 +3587,15 @@ bool InstructionCombiningPass::runOnFunction(Function &F) { // Optional analyses. auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>(); auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; + ProfileSummaryInfo *PSI = + &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); + BlockFrequencyInfo *BFI = + (PSI && PSI->hasProfileSummary()) ? + &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI() : + nullptr; return combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, DT, ORE, - ExpensiveCombines, LI); + BFI, PSI, ExpensiveCombines, LI); } char InstructionCombiningPass::ID = 0; @@ -3514,6 +3608,8 @@ INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass) +INITIALIZE_PASS_DEPENDENCY(LazyBlockFrequencyInfoPass) +INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass) INITIALIZE_PASS_END(InstructionCombiningPass, "instcombine", "Combine redundant instructions", false, false) |
