diff options
| author | Dimitry Andric <dim@FreeBSD.org> | 2019-01-19 10:01:25 +0000 |
|---|---|---|
| committer | Dimitry Andric <dim@FreeBSD.org> | 2019-01-19 10:01:25 +0000 |
| commit | d8e91e46262bc44006913e6796843909f1ac7bcd (patch) | |
| tree | 7d0c143d9b38190e0fa0180805389da22cd834c5 /lib/Transforms/InstCombine | |
| parent | b7eb8e35e481a74962664b63dfb09483b200209a (diff) | |
Notes
Diffstat (limited to 'lib/Transforms/InstCombine')
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineAddSub.cpp | 321 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | 595 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineCalls.cpp | 532 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineCasts.cpp | 126 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineCompares.cpp | 663 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineInternal.h | 64 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp | 143 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineMulDivRem.cpp | 102 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombinePHI.cpp | 27 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineSelect.cpp | 323 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineShifts.cpp | 17 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp | 255 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineVectorOps.cpp | 526 | ||||
| -rw-r--r-- | lib/Transforms/InstCombine/InstructionCombining.cpp | 262 |
14 files changed, 2531 insertions, 1425 deletions
diff --git a/lib/Transforms/InstCombine/InstCombineAddSub.cpp b/lib/Transforms/InstCombine/InstCombineAddSub.cpp index 83054588a9aa..6e196bfdbd25 100644 --- a/lib/Transforms/InstCombine/InstCombineAddSub.cpp +++ b/lib/Transforms/InstCombine/InstCombineAddSub.cpp @@ -186,8 +186,6 @@ namespace { Value *simplifyFAdd(AddendVect& V, unsigned InstrQuota); - Value *performFactorization(Instruction *I); - /// Convert given addend to a Value Value *createAddendVal(const FAddend &A, bool& NeedNeg); @@ -197,7 +195,6 @@ namespace { Value *createFSub(Value *Opnd0, Value *Opnd1); Value *createFAdd(Value *Opnd0, Value *Opnd1); Value *createFMul(Value *Opnd0, Value *Opnd1); - Value *createFDiv(Value *Opnd0, Value *Opnd1); Value *createFNeg(Value *V); Value *createNaryFAdd(const AddendVect& Opnds, unsigned InstrQuota); void createInstPostProc(Instruction *NewInst, bool NoNumber = false); @@ -427,89 +424,6 @@ unsigned FAddend::drillAddendDownOneStep return BreakNum; } -// Try to perform following optimization on the input instruction I. Return the -// simplified expression if was successful; otherwise, return 0. -// -// Instruction "I" is Simplified into -// ------------------------------------------------------- -// (x * y) +/- (x * z) x * (y +/- z) -// (y / x) +/- (z / x) (y +/- z) / x -Value *FAddCombine::performFactorization(Instruction *I) { - assert((I->getOpcode() == Instruction::FAdd || - I->getOpcode() == Instruction::FSub) && "Expect add/sub"); - - Instruction *I0 = dyn_cast<Instruction>(I->getOperand(0)); - Instruction *I1 = dyn_cast<Instruction>(I->getOperand(1)); - - if (!I0 || !I1 || I0->getOpcode() != I1->getOpcode()) - return nullptr; - - bool isMpy = false; - if (I0->getOpcode() == Instruction::FMul) - isMpy = true; - else if (I0->getOpcode() != Instruction::FDiv) - return nullptr; - - Value *Opnd0_0 = I0->getOperand(0); - Value *Opnd0_1 = I0->getOperand(1); - Value *Opnd1_0 = I1->getOperand(0); - Value *Opnd1_1 = I1->getOperand(1); - - // Input Instr I Factor AddSub0 AddSub1 - // ---------------------------------------------- - // (x*y) +/- (x*z) x y z - // (y/x) +/- (z/x) x y z - Value *Factor = nullptr; - Value *AddSub0 = nullptr, *AddSub1 = nullptr; - - if (isMpy) { - if (Opnd0_0 == Opnd1_0 || Opnd0_0 == Opnd1_1) - Factor = Opnd0_0; - else if (Opnd0_1 == Opnd1_0 || Opnd0_1 == Opnd1_1) - Factor = Opnd0_1; - - if (Factor) { - AddSub0 = (Factor == Opnd0_0) ? Opnd0_1 : Opnd0_0; - AddSub1 = (Factor == Opnd1_0) ? Opnd1_1 : Opnd1_0; - } - } else if (Opnd0_1 == Opnd1_1) { - Factor = Opnd0_1; - AddSub0 = Opnd0_0; - AddSub1 = Opnd1_0; - } - - if (!Factor) - return nullptr; - - FastMathFlags Flags; - Flags.setFast(); - if (I0) Flags &= I->getFastMathFlags(); - if (I1) Flags &= I->getFastMathFlags(); - - // Create expression "NewAddSub = AddSub0 +/- AddsSub1" - Value *NewAddSub = (I->getOpcode() == Instruction::FAdd) ? - createFAdd(AddSub0, AddSub1) : - createFSub(AddSub0, AddSub1); - if (ConstantFP *CFP = dyn_cast<ConstantFP>(NewAddSub)) { - const APFloat &F = CFP->getValueAPF(); - if (!F.isNormal()) - return nullptr; - } else if (Instruction *II = dyn_cast<Instruction>(NewAddSub)) - II->setFastMathFlags(Flags); - - if (isMpy) { - Value *RI = createFMul(Factor, NewAddSub); - if (Instruction *II = dyn_cast<Instruction>(RI)) - II->setFastMathFlags(Flags); - return RI; - } - - Value *RI = createFDiv(NewAddSub, Factor); - if (Instruction *II = dyn_cast<Instruction>(RI)) - II->setFastMathFlags(Flags); - return RI; -} - Value *FAddCombine::simplify(Instruction *I) { assert(I->hasAllowReassoc() && I->hasNoSignedZeros() && "Expected 'reassoc'+'nsz' instruction"); @@ -594,8 +508,7 @@ Value *FAddCombine::simplify(Instruction *I) { return R; } - // step 6: Try factorization as the last resort, - return performFactorization(I); + return nullptr; } Value *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) { @@ -772,13 +685,6 @@ Value *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) { return V; } -Value *FAddCombine::createFDiv(Value *Opnd0, Value *Opnd1) { - Value *V = Builder.CreateFDiv(Opnd0, Opnd1); - if (Instruction *I = dyn_cast<Instruction>(V)) - createInstPostProc(I); - return V; -} - void FAddCombine::createInstPostProc(Instruction *NewInstr, bool NoNumber) { NewInstr->setDebugLoc(Instr->getDebugLoc()); @@ -1135,7 +1041,7 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) { if (SimplifyAssociativeOrCommutative(I)) return &I; - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; // (A*B)+(A*C) -> A*(B+C) etc @@ -1285,77 +1191,8 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) { } } - // Check for (add (sext x), y), see if we can merge this into an - // integer add followed by a sext. - if (SExtInst *LHSConv = dyn_cast<SExtInst>(LHS)) { - // (add (sext x), cst) --> (sext (add x, cst')) - if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) { - if (LHSConv->hasOneUse()) { - Constant *CI = - ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType()); - if (ConstantExpr::getSExt(CI, Ty) == RHSC && - willNotOverflowSignedAdd(LHSConv->getOperand(0), CI, I)) { - // Insert the new, smaller add. - Value *NewAdd = - Builder.CreateNSWAdd(LHSConv->getOperand(0), CI, "addconv"); - return new SExtInst(NewAdd, Ty); - } - } - } - - // (add (sext x), (sext y)) --> (sext (add int x, y)) - if (SExtInst *RHSConv = dyn_cast<SExtInst>(RHS)) { - // Only do this if x/y have the same type, if at least one of them has a - // single use (so we don't increase the number of sexts), and if the - // integer add will not overflow. - if (LHSConv->getOperand(0)->getType() == - RHSConv->getOperand(0)->getType() && - (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && - willNotOverflowSignedAdd(LHSConv->getOperand(0), - RHSConv->getOperand(0), I)) { - // Insert the new integer add. - Value *NewAdd = Builder.CreateNSWAdd(LHSConv->getOperand(0), - RHSConv->getOperand(0), "addconv"); - return new SExtInst(NewAdd, Ty); - } - } - } - - // Check for (add (zext x), y), see if we can merge this into an - // integer add followed by a zext. - if (auto *LHSConv = dyn_cast<ZExtInst>(LHS)) { - // (add (zext x), cst) --> (zext (add x, cst')) - if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) { - if (LHSConv->hasOneUse()) { - Constant *CI = - ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType()); - if (ConstantExpr::getZExt(CI, Ty) == RHSC && - willNotOverflowUnsignedAdd(LHSConv->getOperand(0), CI, I)) { - // Insert the new, smaller add. - Value *NewAdd = - Builder.CreateNUWAdd(LHSConv->getOperand(0), CI, "addconv"); - return new ZExtInst(NewAdd, Ty); - } - } - } - - // (add (zext x), (zext y)) --> (zext (add int x, y)) - if (auto *RHSConv = dyn_cast<ZExtInst>(RHS)) { - // Only do this if x/y have the same type, if at least one of them has a - // single use (so we don't increase the number of zexts), and if the - // integer add will not overflow. - if (LHSConv->getOperand(0)->getType() == - RHSConv->getOperand(0)->getType() && - (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && - willNotOverflowUnsignedAdd(LHSConv->getOperand(0), - RHSConv->getOperand(0), I)) { - // Insert the new integer add. - Value *NewAdd = Builder.CreateNUWAdd( - LHSConv->getOperand(0), RHSConv->getOperand(0), "addconv"); - return new ZExtInst(NewAdd, Ty); - } - } - } + if (Instruction *Ext = narrowMathIfNoOverflow(I)) + return Ext; // (add (xor A, B) (and A, B)) --> (or A, B) // (add (and A, B) (xor A, B)) --> (or A, B) @@ -1391,6 +1228,45 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) { return Changed ? &I : nullptr; } +/// Factor a common operand out of fadd/fsub of fmul/fdiv. +static Instruction *factorizeFAddFSub(BinaryOperator &I, + InstCombiner::BuilderTy &Builder) { + assert((I.getOpcode() == Instruction::FAdd || + I.getOpcode() == Instruction::FSub) && "Expecting fadd/fsub"); + assert(I.hasAllowReassoc() && I.hasNoSignedZeros() && + "FP factorization requires FMF"); + Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); + Value *X, *Y, *Z; + bool IsFMul; + if ((match(Op0, m_OneUse(m_FMul(m_Value(X), m_Value(Z)))) && + match(Op1, m_OneUse(m_c_FMul(m_Value(Y), m_Specific(Z))))) || + (match(Op0, m_OneUse(m_FMul(m_Value(Z), m_Value(X)))) && + match(Op1, m_OneUse(m_c_FMul(m_Value(Y), m_Specific(Z)))))) + IsFMul = true; + else if (match(Op0, m_OneUse(m_FDiv(m_Value(X), m_Value(Z)))) && + match(Op1, m_OneUse(m_FDiv(m_Value(Y), m_Specific(Z))))) + IsFMul = false; + else + return nullptr; + + // (X * Z) + (Y * Z) --> (X + Y) * Z + // (X * Z) - (Y * Z) --> (X - Y) * Z + // (X / Z) + (Y / Z) --> (X + Y) / Z + // (X / Z) - (Y / Z) --> (X - Y) / Z + bool IsFAdd = I.getOpcode() == Instruction::FAdd; + Value *XY = IsFAdd ? Builder.CreateFAddFMF(X, Y, &I) + : Builder.CreateFSubFMF(X, Y, &I); + + // Bail out if we just created a denormal constant. + // TODO: This is copied from a previous implementation. Is it necessary? + const APFloat *C; + if (match(XY, m_APFloat(C)) && !C->isNormal()) + return nullptr; + + return IsFMul ? BinaryOperator::CreateFMulFMF(XY, Z, &I) + : BinaryOperator::CreateFDivFMF(XY, Z, &I); +} + Instruction *InstCombiner::visitFAdd(BinaryOperator &I) { if (Value *V = SimplifyFAddInst(I.getOperand(0), I.getOperand(1), I.getFastMathFlags(), @@ -1400,7 +1276,7 @@ Instruction *InstCombiner::visitFAdd(BinaryOperator &I) { if (SimplifyAssociativeOrCommutative(I)) return &I; - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; if (Instruction *FoldedFAdd = foldBinOpIntoSelectOrPhi(I)) @@ -1478,6 +1354,8 @@ Instruction *InstCombiner::visitFAdd(BinaryOperator &I) { return replaceInstUsesWith(I, V); if (I.hasAllowReassoc() && I.hasNoSignedZeros()) { + if (Instruction *F = factorizeFAddFSub(I, Builder)) + return F; if (Value *V = FAddCombine(Builder).simplify(&I)) return replaceInstUsesWith(I, V); } @@ -1577,7 +1455,7 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) { SQ.getWithInstruction(&I))) return replaceInstUsesWith(I, V); - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; // (A*B)-(A*C) -> A*(B-C) etc @@ -1771,19 +1649,51 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) { // X - A*-B -> X + A*B // X - -A*B -> X + A*B Value *A, *B; - Constant *CI; if (match(Op1, m_c_Mul(m_Value(A), m_Neg(m_Value(B))))) return BinaryOperator::CreateAdd(Op0, Builder.CreateMul(A, B)); - // X - A*CI -> X + A*-CI + // X - A*C -> X + A*-C // No need to handle commuted multiply because multiply handling will // ensure constant will be move to the right hand side. - if (match(Op1, m_Mul(m_Value(A), m_Constant(CI)))) { - Value *NewMul = Builder.CreateMul(A, ConstantExpr::getNeg(CI)); + if (match(Op1, m_Mul(m_Value(A), m_Constant(C))) && !isa<ConstantExpr>(C)) { + Value *NewMul = Builder.CreateMul(A, ConstantExpr::getNeg(C)); return BinaryOperator::CreateAdd(Op0, NewMul); } } + { + // ~A - Min/Max(~A, O) -> Max/Min(A, ~O) - A + // ~A - Min/Max(O, ~A) -> Max/Min(A, ~O) - A + // Min/Max(~A, O) - ~A -> A - Max/Min(A, ~O) + // Min/Max(O, ~A) - ~A -> A - Max/Min(A, ~O) + // So long as O here is freely invertible, this will be neutral or a win. + Value *LHS, *RHS, *A; + Value *NotA = Op0, *MinMax = Op1; + SelectPatternFlavor SPF = matchSelectPattern(MinMax, LHS, RHS).Flavor; + if (!SelectPatternResult::isMinOrMax(SPF)) { + NotA = Op1; + MinMax = Op0; + SPF = matchSelectPattern(MinMax, LHS, RHS).Flavor; + } + if (SelectPatternResult::isMinOrMax(SPF) && + match(NotA, m_Not(m_Value(A))) && (NotA == LHS || NotA == RHS)) { + if (NotA == LHS) + std::swap(LHS, RHS); + // LHS is now O above and expected to have at least 2 uses (the min/max) + // NotA is epected to have 2 uses from the min/max and 1 from the sub. + if (IsFreeToInvert(LHS, !LHS->hasNUsesOrMore(3)) && + !NotA->hasNUsesOrMore(4)) { + // Note: We don't generate the inverse max/min, just create the not of + // it and let other folds do the rest. + Value *Not = Builder.CreateNot(MinMax); + if (NotA == Op0) + return BinaryOperator::CreateSub(Not, A); + else + return BinaryOperator::CreateSub(A, Not); + } + } + } + // Optimize pointer differences into the same array into a size. Consider: // &A[10] - &A[0]: we should compile this to "10". Value *LHSOp, *RHSOp; @@ -1819,6 +1729,9 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) { return SelectInst::Create(Cmp, Neg, A); } + if (Instruction *Ext = narrowMathIfNoOverflow(I)) + return Ext; + bool Changed = false; if (!I.hasNoSignedWrap() && willNotOverflowSignedSub(Op0, Op1, I)) { Changed = true; @@ -1838,7 +1751,7 @@ Instruction *InstCombiner::visitFSub(BinaryOperator &I) { SQ.getWithInstruction(&I))) return replaceInstUsesWith(I, V); - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; // Subtraction from -0.0 is the canonical form of fneg. @@ -1847,13 +1760,27 @@ Instruction *InstCombiner::visitFSub(BinaryOperator &I) { if (I.hasNoSignedZeros() && match(Op0, m_PosZeroFP())) return BinaryOperator::CreateFNegFMF(Op1, &I); + 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. // Note that if this fsub was really an fneg, the fadd with -0.0 will get // killed later. We still limit that particular transform with 'hasOneUse' // because an fneg is assumed better/cheaper than a generic fsub. - Value *X, *Y; if (I.hasNoSignedZeros() || CannotBeNegativeZero(Op0, SQ.TLI)) { if (match(Op1, m_OneUse(m_FSub(m_Value(X), m_Value(Y))))) { Value *NewSub = Builder.CreateFSubFMF(Y, X, &I); @@ -1869,7 +1796,6 @@ Instruction *InstCombiner::visitFSub(BinaryOperator &I) { // X - C --> X + (-C) // But don't transform constant expressions because there's an inverse fold // for X + (-Y) --> X - Y. - Constant *C; if (match(Op1, m_Constant(C)) && !isa<ConstantExpr>(Op1)) return BinaryOperator::CreateFAddFMF(Op0, ConstantExpr::getFNeg(C), &I); @@ -1879,21 +1805,46 @@ Instruction *InstCombiner::visitFSub(BinaryOperator &I) { // Similar to above, but look through a cast of the negated value: // X - (fptrunc(-Y)) --> X + fptrunc(Y) - if (match(Op1, m_OneUse(m_FPTrunc(m_FNeg(m_Value(Y)))))) { - Value *TruncY = Builder.CreateFPTrunc(Y, I.getType()); - return BinaryOperator::CreateFAddFMF(Op0, TruncY, &I); - } + Type *Ty = I.getType(); + if (match(Op1, m_OneUse(m_FPTrunc(m_FNeg(m_Value(Y)))))) + return BinaryOperator::CreateFAddFMF(Op0, Builder.CreateFPTrunc(Y, Ty), &I); + // X - (fpext(-Y)) --> X + fpext(Y) - if (match(Op1, m_OneUse(m_FPExt(m_FNeg(m_Value(Y)))))) { - Value *ExtY = Builder.CreateFPExt(Y, I.getType()); - return BinaryOperator::CreateFAddFMF(Op0, ExtY, &I); - } + if (match(Op1, m_OneUse(m_FPExt(m_FNeg(m_Value(Y)))))) + return BinaryOperator::CreateFAddFMF(Op0, Builder.CreateFPExt(Y, Ty), &I); - // Handle specials cases for FSub with selects feeding the operation + // Handle special cases for FSub with selects feeding the operation if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1)) return replaceInstUsesWith(I, V); if (I.hasAllowReassoc() && I.hasNoSignedZeros()) { + // (Y - X) - Y --> -X + if (match(Op0, m_FSub(m_Specific(Op1), m_Value(X)))) + return BinaryOperator::CreateFNegFMF(X, &I); + + // Y - (X + Y) --> -X + // Y - (Y + X) --> -X + if (match(Op1, m_c_FAdd(m_Specific(Op0), m_Value(X)))) + return BinaryOperator::CreateFNegFMF(X, &I); + + // (X * C) - X --> X * (C - 1.0) + if (match(Op0, m_FMul(m_Specific(Op1), m_Constant(C)))) { + Constant *CSubOne = ConstantExpr::getFSub(C, ConstantFP::get(Ty, 1.0)); + return BinaryOperator::CreateFMulFMF(Op1, CSubOne, &I); + } + // X - (X * C) --> X * (1.0 - C) + if (match(Op1, m_FMul(m_Specific(Op0), m_Constant(C)))) { + Constant *OneSubC = ConstantExpr::getFSub(ConstantFP::get(Ty, 1.0), C); + return BinaryOperator::CreateFMulFMF(Op0, OneSubC, &I); + } + + if (Instruction *F = factorizeFAddFSub(I, Builder)) + return F; + + // TODO: This performs reassociative folds for FP ops. Some fraction of the + // functionality has been subsumed by simple pattern matching here and in + // InstSimplify. We should let a dedicated reassociation pass handle more + // complex pattern matching and remove this from InstCombine. if (Value *V = FAddCombine(Builder).simplify(&I)) return replaceInstUsesWith(I, V); } diff --git a/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp index 3d758e2fe7c9..404c2ad7e6e7 100644 --- a/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ b/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -53,11 +53,11 @@ static unsigned getFCmpCode(FCmpInst::Predicate CC) { /// operands into either a constant true or false, or a brand new ICmp /// instruction. The sign is passed in to determine which kind of predicate to /// use in the new icmp instruction. -static Value *getNewICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, +static Value *getNewICmpValue(unsigned Code, bool Sign, Value *LHS, Value *RHS, InstCombiner::BuilderTy &Builder) { ICmpInst::Predicate NewPred; - if (Value *NewConstant = getICmpValue(Sign, Code, LHS, RHS, NewPred)) - return NewConstant; + if (Constant *TorF = getPredForICmpCode(Code, Sign, LHS->getType(), NewPred)) + return TorF; return Builder.CreateICmp(NewPred, LHS, RHS); } @@ -898,6 +898,130 @@ Value *InstCombiner::foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS, return nullptr; } +/// General pattern: +/// X & Y +/// +/// Where Y is checking that all the high bits (covered by a mask 4294967168) +/// are uniform, i.e. %arg & 4294967168 can be either 4294967168 or 0 +/// Pattern can be one of: +/// %t = add i32 %arg, 128 +/// %r = icmp ult i32 %t, 256 +/// Or +/// %t0 = shl i32 %arg, 24 +/// %t1 = ashr i32 %t0, 24 +/// %r = icmp eq i32 %t1, %arg +/// Or +/// %t0 = trunc i32 %arg to i8 +/// %t1 = sext i8 %t0 to i32 +/// %r = icmp eq i32 %t1, %arg +/// This pattern is a signed truncation check. +/// +/// And X is checking that some bit in that same mask is zero. +/// I.e. can be one of: +/// %r = icmp sgt i32 %arg, -1 +/// Or +/// %t = and i32 %arg, 2147483648 +/// %r = icmp eq i32 %t, 0 +/// +/// Since we are checking that all the bits in that mask are the same, +/// and a particular bit is zero, what we are really checking is that all the +/// masked bits are zero. +/// So this should be transformed to: +/// %r = icmp ult i32 %arg, 128 +static Value *foldSignedTruncationCheck(ICmpInst *ICmp0, ICmpInst *ICmp1, + Instruction &CxtI, + InstCombiner::BuilderTy &Builder) { + assert(CxtI.getOpcode() == Instruction::And); + + // Match icmp ult (add %arg, C01), C1 (C1 == C01 << 1; powers of two) + auto tryToMatchSignedTruncationCheck = [](ICmpInst *ICmp, Value *&X, + APInt &SignBitMask) -> bool { + CmpInst::Predicate Pred; + const APInt *I01, *I1; // powers of two; I1 == I01 << 1 + if (!(match(ICmp, + m_ICmp(Pred, m_Add(m_Value(X), m_Power2(I01)), m_Power2(I1))) && + Pred == ICmpInst::ICMP_ULT && I1->ugt(*I01) && I01->shl(1) == *I1)) + return false; + // Which bit is the new sign bit as per the 'signed truncation' pattern? + SignBitMask = *I01; + return true; + }; + + // One icmp needs to be 'signed truncation check'. + // We need to match this first, else we will mismatch commutative cases. + Value *X1; + APInt HighestBit; + ICmpInst *OtherICmp; + if (tryToMatchSignedTruncationCheck(ICmp1, X1, HighestBit)) + OtherICmp = ICmp0; + else if (tryToMatchSignedTruncationCheck(ICmp0, X1, HighestBit)) + OtherICmp = ICmp1; + else + return nullptr; + + assert(HighestBit.isPowerOf2() && "expected to be power of two (non-zero)"); + + // Try to match/decompose into: icmp eq (X & Mask), 0 + auto tryToDecompose = [](ICmpInst *ICmp, Value *&X, + APInt &UnsetBitsMask) -> bool { + CmpInst::Predicate Pred = ICmp->getPredicate(); + // Can it be decomposed into icmp eq (X & Mask), 0 ? + if (llvm::decomposeBitTestICmp(ICmp->getOperand(0), ICmp->getOperand(1), + Pred, X, UnsetBitsMask, + /*LookThruTrunc=*/false) && + Pred == ICmpInst::ICMP_EQ) + return true; + // Is it icmp eq (X & Mask), 0 already? + const APInt *Mask; + if (match(ICmp, m_ICmp(Pred, m_And(m_Value(X), m_APInt(Mask)), m_Zero())) && + Pred == ICmpInst::ICMP_EQ) { + UnsetBitsMask = *Mask; + return true; + } + return false; + }; + + // And the other icmp needs to be decomposable into a bit test. + Value *X0; + APInt UnsetBitsMask; + if (!tryToDecompose(OtherICmp, X0, UnsetBitsMask)) + return nullptr; + + assert(!UnsetBitsMask.isNullValue() && "empty mask makes no sense."); + + // Are they working on the same value? + Value *X; + if (X1 == X0) { + // Ok as is. + X = X1; + } else if (match(X0, m_Trunc(m_Specific(X1)))) { + UnsetBitsMask = UnsetBitsMask.zext(X1->getType()->getScalarSizeInBits()); + X = X1; + } else + return nullptr; + + // So which bits should be uniform as per the 'signed truncation check'? + // (all the bits starting with (i.e. including) HighestBit) + APInt SignBitsMask = ~(HighestBit - 1U); + + // UnsetBitsMask must have some common bits with SignBitsMask, + if (!UnsetBitsMask.intersects(SignBitsMask)) + return nullptr; + + // Does UnsetBitsMask contain any bits outside of SignBitsMask? + if (!UnsetBitsMask.isSubsetOf(SignBitsMask)) { + APInt OtherHighestBit = (~UnsetBitsMask) + 1U; + if (!OtherHighestBit.isPowerOf2()) + return nullptr; + HighestBit = APIntOps::umin(HighestBit, OtherHighestBit); + } + // Else, if it does not, then all is ok as-is. + + // %r = icmp ult %X, SignBit + return Builder.CreateICmpULT(X, ConstantInt::get(X->getType(), HighestBit), + CxtI.getName() + ".simplified"); +} + /// Fold (icmp)&(icmp) if possible. Value *InstCombiner::foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &CxtI) { @@ -909,7 +1033,7 @@ Value *InstCombiner::foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate(); // (icmp1 A, B) & (icmp2 A, B) --> (icmp3 A, B) - if (PredicatesFoldable(PredL, PredR)) { + if (predicatesFoldable(PredL, PredR)) { if (LHS->getOperand(0) == RHS->getOperand(1) && LHS->getOperand(1) == RHS->getOperand(0)) LHS->swapOperands(); @@ -917,8 +1041,8 @@ Value *InstCombiner::foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, LHS->getOperand(1) == RHS->getOperand(1)) { Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1); unsigned Code = getICmpCode(LHS) & getICmpCode(RHS); - bool isSigned = LHS->isSigned() || RHS->isSigned(); - return getNewICmpValue(isSigned, Code, Op0, Op1, Builder); + bool IsSigned = LHS->isSigned() || RHS->isSigned(); + return getNewICmpValue(Code, IsSigned, Op0, Op1, Builder); } } @@ -937,6 +1061,9 @@ Value *InstCombiner::foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, true, Builder)) return V; + if (Value *V = foldSignedTruncationCheck(LHS, RHS, CxtI, 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)); @@ -1004,7 +1131,7 @@ Value *InstCombiner::foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, return nullptr; // We can't fold (ugt x, C) & (sgt x, C2). - if (!PredicatesFoldable(PredL, PredR)) + if (!predicatesFoldable(PredL, PredR)) return nullptr; // Ensure that the larger constant is on the RHS. @@ -1408,7 +1535,7 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) { if (SimplifyAssociativeOrCommutative(I)) return &I; - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; // See if we can simplify any instructions used by the instruction whose sole @@ -1635,10 +1762,9 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) { return nullptr; } -/// Given an OR instruction, check to see if this is a bswap idiom. If so, -/// insert the new intrinsic and return it. -Instruction *InstCombiner::MatchBSwap(BinaryOperator &I) { - Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); +Instruction *InstCombiner::matchBSwap(BinaryOperator &Or) { + assert(Or.getOpcode() == Instruction::Or && "bswap requires an 'or'"); + Value *Op0 = Or.getOperand(0), *Op1 = Or.getOperand(1); // Look through zero extends. if (Instruction *Ext = dyn_cast<ZExtInst>(Op0)) @@ -1674,7 +1800,7 @@ Instruction *InstCombiner::MatchBSwap(BinaryOperator &I) { return nullptr; SmallVector<Instruction*, 4> Insts; - if (!recognizeBSwapOrBitReverseIdiom(&I, true, false, Insts)) + if (!recognizeBSwapOrBitReverseIdiom(&Or, true, false, Insts)) return nullptr; Instruction *LastInst = Insts.pop_back_val(); LastInst->removeFromParent(); @@ -1684,6 +1810,57 @@ Instruction *InstCombiner::MatchBSwap(BinaryOperator &I) { return LastInst; } +/// Transform UB-safe variants of bitwise rotate to the funnel shift intrinsic. +static Instruction *matchRotate(Instruction &Or) { + // TODO: Can we reduce the code duplication between this and the related + // rotate matching code under visitSelect and visitTrunc? + unsigned Width = Or.getType()->getScalarSizeInBits(); + if (!isPowerOf2_32(Width)) + return nullptr; + + // 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); + 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(); + if (ShiftOpcode0 == ShiftOpcode1) + return nullptr; + + // Match the shift amount operands for a rotate pattern. This always matches + // a subtraction on the R operand. + auto matchShiftAmount = [](Value *L, Value *R, unsigned Width) -> Value * { + // The shift amount may be masked with negation: + // (shl ShVal, (X & (Width - 1))) | (lshr ShVal, ((-X) & (Width - 1))) + Value *X; + unsigned Mask = Width - 1; + if (match(L, m_And(m_Value(X), m_SpecificInt(Mask))) && + match(R, m_And(m_Neg(m_Specific(X)), m_SpecificInt(Mask)))) + return X; + + return nullptr; + }; + + Value *ShAmt = matchShiftAmount(ShAmt0, ShAmt1, Width); + bool SubIsOnLHS = false; + if (!ShAmt) { + ShAmt = matchShiftAmount(ShAmt1, ShAmt0, Width); + SubIsOnLHS = true; + } + if (!ShAmt) + return nullptr; + + bool IsFshl = (!SubIsOnLHS && ShiftOpcode0 == BinaryOperator::Shl) || + (SubIsOnLHS && ShiftOpcode1 == BinaryOperator::Shl); + Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr; + Function *F = Intrinsic::getDeclaration(Or.getModule(), IID, Or.getType()); + return IntrinsicInst::Create(F, { ShVal, ShVal, ShAmt }); +} + /// If all elements of two constant vectors are 0/-1 and inverses, return true. static bool areInverseVectorBitmasks(Constant *C1, Constant *C2) { unsigned NumElts = C1->getType()->getVectorNumElements(); @@ -1704,14 +1881,33 @@ static bool areInverseVectorBitmasks(Constant *C1, Constant *C2) { /// We have an expression of the form (A & C) | (B & D). If A is a scalar or /// vector composed of all-zeros or all-ones values and is the bitwise 'not' of /// B, it can be used as the condition operand of a select instruction. -static Value *getSelectCondition(Value *A, Value *B, - InstCombiner::BuilderTy &Builder) { - // If these are scalars or vectors of i1, A can be used directly. +Value *InstCombiner::getSelectCondition(Value *A, Value *B) { + // Step 1: We may have peeked through bitcasts in the caller. + // Exit immediately if we don't have (vector) integer types. Type *Ty = A->getType(); - if (match(A, m_Not(m_Specific(B))) && Ty->isIntOrIntVectorTy(1)) - return A; + if (!Ty->isIntOrIntVectorTy() || !B->getType()->isIntOrIntVectorTy()) + return nullptr; + + // Step 2: We need 0 or all-1's bitmasks. + if (ComputeNumSignBits(A) != Ty->getScalarSizeInBits()) + return nullptr; + + // Step 3: If B is the 'not' value of A, we have our answer. + if (match(A, m_Not(m_Specific(B)))) { + // If these are scalars or vectors of i1, A can be used directly. + if (Ty->isIntOrIntVectorTy(1)) + return A; + return Builder.CreateTrunc(A, CmpInst::makeCmpResultType(Ty)); + } + + // If both operands are constants, see if the constants are inverse bitmasks. + Constant *AConst, *BConst; + if (match(A, m_Constant(AConst)) && match(B, m_Constant(BConst))) + if (AConst == ConstantExpr::getNot(BConst)) + return Builder.CreateZExtOrTrunc(A, CmpInst::makeCmpResultType(Ty)); - // If A and B are sign-extended, look through the sexts to find the booleans. + // Look for more complex patterns. The 'not' op may be hidden behind various + // casts. Look through sexts and bitcasts to find the booleans. Value *Cond; Value *NotB; if (match(A, m_SExt(m_Value(Cond))) && @@ -1727,36 +1923,29 @@ static Value *getSelectCondition(Value *A, Value *B, if (!Ty->isVectorTy()) return nullptr; - // If both operands are constants, see if the constants are inverse bitmasks. - Constant *AC, *BC; - if (match(A, m_Constant(AC)) && match(B, m_Constant(BC)) && - areInverseVectorBitmasks(AC, BC)) { - return Builder.CreateZExtOrTrunc(AC, CmpInst::makeCmpResultType(Ty)); - } - // If both operands are xor'd with constants using the same sexted boolean // operand, see if the constants are inverse bitmasks. - if (match(A, (m_Xor(m_SExt(m_Value(Cond)), m_Constant(AC)))) && - match(B, (m_Xor(m_SExt(m_Specific(Cond)), m_Constant(BC)))) && + // TODO: Use ConstantExpr::getNot()? + if (match(A, (m_Xor(m_SExt(m_Value(Cond)), m_Constant(AConst)))) && + match(B, (m_Xor(m_SExt(m_Specific(Cond)), m_Constant(BConst)))) && Cond->getType()->isIntOrIntVectorTy(1) && - areInverseVectorBitmasks(AC, BC)) { - AC = ConstantExpr::getTrunc(AC, CmpInst::makeCmpResultType(Ty)); - return Builder.CreateXor(Cond, AC); + areInverseVectorBitmasks(AConst, BConst)) { + AConst = ConstantExpr::getTrunc(AConst, CmpInst::makeCmpResultType(Ty)); + return Builder.CreateXor(Cond, AConst); } return nullptr; } /// We have an expression of the form (A & C) | (B & D). Try to simplify this /// to "A' ? C : D", where A' is a boolean or vector of booleans. -static Value *matchSelectFromAndOr(Value *A, Value *C, Value *B, Value *D, - InstCombiner::BuilderTy &Builder) { +Value *InstCombiner::matchSelectFromAndOr(Value *A, Value *C, Value *B, + Value *D) { // The potential condition of the select may be bitcasted. In that case, look // through its bitcast and the corresponding bitcast of the 'not' condition. Type *OrigType = A->getType(); A = peekThroughBitcast(A, true); B = peekThroughBitcast(B, true); - - if (Value *Cond = getSelectCondition(A, B, Builder)) { + if (Value *Cond = getSelectCondition(A, B)) { // ((bc Cond) & C) | ((bc ~Cond) & D) --> bc (select Cond, (bc C), (bc D)) // The bitcasts will either all exist or all not exist. The builder will // not create unnecessary casts if the types already match. @@ -1838,7 +2027,7 @@ Value *InstCombiner::foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, } // (icmp1 A, B) | (icmp2 A, B) --> (icmp3 A, B) - if (PredicatesFoldable(PredL, PredR)) { + if (predicatesFoldable(PredL, PredR)) { if (LHS->getOperand(0) == RHS->getOperand(1) && LHS->getOperand(1) == RHS->getOperand(0)) LHS->swapOperands(); @@ -1846,8 +2035,8 @@ Value *InstCombiner::foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, LHS->getOperand(1) == RHS->getOperand(1)) { Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1); unsigned Code = getICmpCode(LHS) | getICmpCode(RHS); - bool isSigned = LHS->isSigned() || RHS->isSigned(); - return getNewICmpValue(isSigned, Code, Op0, Op1, Builder); + bool IsSigned = LHS->isSigned() || RHS->isSigned(); + return getNewICmpValue(Code, IsSigned, Op0, Op1, Builder); } } @@ -1928,7 +2117,7 @@ Value *InstCombiner::foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, return nullptr; // We can't fold (ugt x, C) | (sgt x, C2). - if (!PredicatesFoldable(PredL, PredR)) + if (!predicatesFoldable(PredL, PredR)) return nullptr; // Ensure that the larger constant is on the RHS. @@ -2007,7 +2196,7 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { if (SimplifyAssociativeOrCommutative(I)) return &I; - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; // See if we can simplify any instructions used by the instruction whose sole @@ -2029,37 +2218,25 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I)) return FoldedLogic; - // Given an OR instruction, check to see if this is a bswap. - if (Instruction *BSwap = MatchBSwap(I)) + if (Instruction *BSwap = matchBSwap(I)) return BSwap; - Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); - { - Value *A; - const APInt *C; - // (X^C)|Y -> (X|Y)^C iff Y&C == 0 - if (match(Op0, m_OneUse(m_Xor(m_Value(A), m_APInt(C)))) && - MaskedValueIsZero(Op1, *C, 0, &I)) { - Value *NOr = Builder.CreateOr(A, Op1); - NOr->takeName(Op0); - return BinaryOperator::CreateXor(NOr, - ConstantInt::get(NOr->getType(), *C)); - } + if (Instruction *Rotate = matchRotate(I)) + return Rotate; - // Y|(X^C) -> (X|Y)^C iff Y&C == 0 - if (match(Op1, m_OneUse(m_Xor(m_Value(A), m_APInt(C)))) && - MaskedValueIsZero(Op0, *C, 0, &I)) { - Value *NOr = Builder.CreateOr(A, Op0); - NOr->takeName(Op0); - return BinaryOperator::CreateXor(NOr, - ConstantInt::get(NOr->getType(), *C)); - } + Value *X, *Y; + const APInt *CV; + if (match(&I, m_c_Or(m_OneUse(m_Xor(m_Value(X), m_APInt(CV))), m_Value(Y))) && + !CV->isAllOnesValue() && MaskedValueIsZero(Y, *CV, 0, &I)) { + // (X ^ C) | Y -> (X | Y) ^ C iff Y & C == 0 + // The check for a 'not' op is for efficiency (if Y is known zero --> ~X). + Value *Or = Builder.CreateOr(X, Y); + return BinaryOperator::CreateXor(Or, ConstantInt::get(I.getType(), *CV)); } - Value *A, *B; - // (A & C)|(B & D) - Value *C = nullptr, *D = nullptr; + Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); + Value *A, *B, *C, *D; if (match(Op0, m_And(m_Value(A), m_Value(C))) && match(Op1, m_And(m_Value(B), m_Value(D)))) { ConstantInt *C1 = dyn_cast<ConstantInt>(C); @@ -2122,21 +2299,21 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { // 'or' that it is replacing. if (Op0->hasOneUse() || Op1->hasOneUse()) { // (Cond & C) | (~Cond & D) -> Cond ? C : D, and commuted variants. - if (Value *V = matchSelectFromAndOr(A, C, B, D, Builder)) + if (Value *V = matchSelectFromAndOr(A, C, B, D)) return replaceInstUsesWith(I, V); - if (Value *V = matchSelectFromAndOr(A, C, D, B, Builder)) + if (Value *V = matchSelectFromAndOr(A, C, D, B)) return replaceInstUsesWith(I, V); - if (Value *V = matchSelectFromAndOr(C, A, B, D, Builder)) + if (Value *V = matchSelectFromAndOr(C, A, B, D)) return replaceInstUsesWith(I, V); - if (Value *V = matchSelectFromAndOr(C, A, D, B, Builder)) + if (Value *V = matchSelectFromAndOr(C, A, D, B)) return replaceInstUsesWith(I, V); - if (Value *V = matchSelectFromAndOr(B, D, A, C, Builder)) + if (Value *V = matchSelectFromAndOr(B, D, A, C)) return replaceInstUsesWith(I, V); - if (Value *V = matchSelectFromAndOr(B, D, C, A, Builder)) + if (Value *V = matchSelectFromAndOr(B, D, C, A)) return replaceInstUsesWith(I, V); - if (Value *V = matchSelectFromAndOr(D, B, A, C, Builder)) + if (Value *V = matchSelectFromAndOr(D, B, A, C)) return replaceInstUsesWith(I, V); - if (Value *V = matchSelectFromAndOr(D, B, C, A, Builder)) + if (Value *V = matchSelectFromAndOr(D, B, C, A)) return replaceInstUsesWith(I, V); } } @@ -2251,12 +2428,12 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { // be simplified by a later pass either, so we try swapping the inner/outer // ORs in the hopes that we'll be able to simplify it this way. // (X|C) | V --> (X|V) | C - ConstantInt *C1; + ConstantInt *CI; if (Op0->hasOneUse() && !isa<ConstantInt>(Op1) && - match(Op0, m_Or(m_Value(A), m_ConstantInt(C1)))) { + match(Op0, m_Or(m_Value(A), m_ConstantInt(CI)))) { Value *Inner = Builder.CreateOr(A, Op1); Inner->takeName(Op0); - return BinaryOperator::CreateOr(Inner, C1); + return BinaryOperator::CreateOr(Inner, CI); } // Change (or (bool?A:B),(bool?C:D)) --> (bool?(or A,C):(or B,D)) @@ -2339,7 +2516,7 @@ static Instruction *foldXorToXor(BinaryOperator &I, } Value *InstCombiner::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS) { - if (PredicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) { + if (predicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) { if (LHS->getOperand(0) == RHS->getOperand(1) && LHS->getOperand(1) == RHS->getOperand(0)) LHS->swapOperands(); @@ -2348,8 +2525,8 @@ Value *InstCombiner::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS) { // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B) Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1); unsigned Code = getICmpCode(LHS) ^ getICmpCode(RHS); - bool isSigned = LHS->isSigned() || RHS->isSigned(); - return getNewICmpValue(isSigned, Code, Op0, Op1, Builder); + bool IsSigned = LHS->isSigned() || RHS->isSigned(); + return getNewICmpValue(Code, IsSigned, Op0, Op1, Builder); } } @@ -2360,7 +2537,8 @@ Value *InstCombiner::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS) { Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1); Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1); if ((LHS->hasOneUse() || RHS->hasOneUse()) && - LHS0->getType() == RHS0->getType()) { + LHS0->getType() == RHS0->getType() && + LHS0->getType()->isIntOrIntVectorTy()) { // (X > -1) ^ (Y > -1) --> (X ^ Y) < 0 // (X < 0) ^ (Y < 0) --> (X ^ Y) < 0 if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_AllOnes()) && @@ -2452,6 +2630,32 @@ static Instruction *visitMaskedMerge(BinaryOperator &I, return nullptr; } +// Transform +// ~(x ^ y) +// into: +// (~x) ^ y +// or into +// x ^ (~y) +static Instruction *sinkNotIntoXor(BinaryOperator &I, + InstCombiner::BuilderTy &Builder) { + Value *X, *Y; + // FIXME: one-use check is not needed in general, but currently we are unable + // to fold 'not' into 'icmp', if that 'icmp' has multiple uses. (D35182) + if (!match(&I, m_Not(m_OneUse(m_Xor(m_Value(X), m_Value(Y)))))) + return nullptr; + + // We only want to do the transform if it is free to do. + if (IsFreeToInvert(X, X->hasOneUse())) { + // Ok, good. + } else if (IsFreeToInvert(Y, Y->hasOneUse())) { + std::swap(X, Y); + } else + return nullptr; + + Value *NotX = Builder.CreateNot(X, X->getName() + ".not"); + return BinaryOperator::CreateXor(NotX, Y, I.getName() + ".demorgan"); +} + // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches // here. We should standardize that construct where it is needed or choose some // other way to ensure that commutated variants of patterns are not missed. @@ -2463,7 +2667,7 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { if (SimplifyAssociativeOrCommutative(I)) return &I; - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; if (Instruction *NewXor = foldXorToXor(I, Builder)) @@ -2481,9 +2685,15 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { if (Value *V = SimplifyBSwap(I, Builder)) return replaceInstUsesWith(I, V); - // A^B --> A|B iff A and B have no bits set in common. Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); - if (haveNoCommonBitsSet(Op0, Op1, DL, &AC, &I, &DT)) + + // Fold (X & M) ^ (Y & ~M) -> (X & M) | (Y & ~M) + // This it a special case in haveNoCommonBitsSet, but the computeKnownBits + // calls in there are unnecessary as SimplifyDemandedInstructionBits should + // have already taken care of those cases. + Value *M; + if (match(&I, m_c_Xor(m_c_And(m_Not(m_Value(M)), m_Value()), + m_c_And(m_Deferred(M), m_Value())))) return BinaryOperator::CreateOr(Op0, Op1); // Apply DeMorgan's Law for 'nand' / 'nor' logic with an inverted operand. @@ -2528,8 +2738,9 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { } // ~(X - Y) --> ~X + Y - if (match(NotVal, m_OneUse(m_Sub(m_Value(X), m_Value(Y))))) - return BinaryOperator::CreateAdd(Builder.CreateNot(X), Y); + if (match(NotVal, m_Sub(m_Value(X), m_Value(Y)))) + if (isa<Constant>(X) || NotVal->hasOneUse()) + return BinaryOperator::CreateAdd(Builder.CreateNot(X), Y); // ~(~X >>s Y) --> (X >>s Y) if (match(NotVal, m_AShr(m_Not(m_Value(X)), m_Value(Y)))) @@ -2539,19 +2750,36 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { // the 'not' by inverting the constant and using the opposite shift type. // Canonicalization rules ensure that only a negative constant uses 'ashr', // but we must check that in case that transform has not fired yet. + + // ~(C >>s Y) --> ~C >>u Y (when inverting the replicated sign bits) Constant *C; if (match(NotVal, m_AShr(m_Constant(C), m_Value(Y))) && - match(C, m_Negative())) { - // ~(C >>s Y) --> ~C >>u Y (when inverting the replicated sign bits) - Constant *NotC = ConstantExpr::getNot(C); - return BinaryOperator::CreateLShr(NotC, Y); - } + match(C, m_Negative())) + return BinaryOperator::CreateLShr(ConstantExpr::getNot(C), Y); + // ~(C >>u Y) --> ~C >>s Y (when inverting the replicated sign bits) if (match(NotVal, m_LShr(m_Constant(C), m_Value(Y))) && - match(C, m_NonNegative())) { - // ~(C >>u Y) --> ~C >>s Y (when inverting the replicated sign bits) - Constant *NotC = ConstantExpr::getNot(C); - return BinaryOperator::CreateAShr(NotC, Y); + match(C, m_NonNegative())) + return BinaryOperator::CreateAShr(ConstantExpr::getNot(C), Y); + + // ~(X + C) --> -(C + 1) - X + if (match(Op0, m_Add(m_Value(X), m_Constant(C)))) + return BinaryOperator::CreateSub(ConstantExpr::getNeg(AddOne(C)), X); + } + + // Use DeMorgan and reassociation to eliminate a 'not' op. + Constant *C1; + if (match(Op1, m_Constant(C1))) { + Constant *C2; + if (match(Op0, m_OneUse(m_Or(m_Not(m_Value(X)), m_Constant(C2))))) { + // (~X | C2) ^ C1 --> ((X & ~C2) ^ -1) ^ C1 --> (X & ~C2) ^ ~C1 + Value *And = Builder.CreateAnd(X, ConstantExpr::getNot(C2)); + return BinaryOperator::CreateXor(And, ConstantExpr::getNot(C1)); + } + if (match(Op0, m_OneUse(m_And(m_Not(m_Value(X)), m_Constant(C2))))) { + // (~X & C2) ^ C1 --> ((X | ~C2) ^ -1) ^ C1 --> (X | ~C2) ^ ~C1 + Value *Or = Builder.CreateOr(X, ConstantExpr::getNot(C2)); + return BinaryOperator::CreateXor(Or, ConstantExpr::getNot(C1)); } } @@ -2567,28 +2795,15 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { if (match(Op1, m_APInt(RHSC))) { Value *X; const APInt *C; - if (match(Op0, m_Sub(m_APInt(C), m_Value(X)))) { - // ~(c-X) == X-c-1 == X+(-c-1) - if (RHSC->isAllOnesValue()) { - Constant *NewC = ConstantInt::get(I.getType(), -(*C) - 1); - return BinaryOperator::CreateAdd(X, NewC); - } - if (RHSC->isSignMask()) { - // (C - X) ^ signmask -> (C + signmask - X) - Constant *NewC = ConstantInt::get(I.getType(), *C + *RHSC); - return BinaryOperator::CreateSub(NewC, X); - } - } else if (match(Op0, m_Add(m_Value(X), m_APInt(C)))) { - // ~(X-c) --> (-c-1)-X - if (RHSC->isAllOnesValue()) { - Constant *NewC = ConstantInt::get(I.getType(), -(*C) - 1); - return BinaryOperator::CreateSub(NewC, X); - } - if (RHSC->isSignMask()) { - // (X + C) ^ signmask -> (X + C + signmask) - Constant *NewC = ConstantInt::get(I.getType(), *C + *RHSC); - return BinaryOperator::CreateAdd(X, NewC); - } + if (RHSC->isSignMask() && match(Op0, m_Sub(m_APInt(C), m_Value(X)))) { + // (C - X) ^ signmask -> (C + signmask - X) + Constant *NewC = ConstantInt::get(I.getType(), *C + *RHSC); + return BinaryOperator::CreateSub(NewC, X); + } + if (RHSC->isSignMask() && match(Op0, m_Add(m_Value(X), m_APInt(C)))) { + // (X + C) ^ signmask -> (X + C + signmask) + Constant *NewC = ConstantInt::get(I.getType(), *C + *RHSC); + return BinaryOperator::CreateAdd(X, NewC); } // (X|C1)^C2 -> X^(C1^C2) iff X&~C1 == 0 @@ -2635,82 +2850,52 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I)) return FoldedLogic; - { - Value *A, *B; - if (match(Op1, m_OneUse(m_Or(m_Value(A), m_Value(B))))) { - if (A == Op0) { // A^(A|B) == A^(B|A) - cast<BinaryOperator>(Op1)->swapOperands(); - std::swap(A, B); - } - if (B == Op0) { // A^(B|A) == (B|A)^A - I.swapOperands(); // Simplified below. - std::swap(Op0, Op1); - } - } else if (match(Op1, m_OneUse(m_And(m_Value(A), m_Value(B))))) { - if (A == Op0) { // A^(A&B) -> A^(B&A) - cast<BinaryOperator>(Op1)->swapOperands(); - std::swap(A, B); - } - if (B == Op0) { // A^(B&A) -> (B&A)^A - I.swapOperands(); // Simplified below. - std::swap(Op0, Op1); - } - } - } + // Y ^ (X | Y) --> X & ~Y + // Y ^ (Y | X) --> X & ~Y + if (match(Op1, m_OneUse(m_c_Or(m_Value(X), m_Specific(Op0))))) + return BinaryOperator::CreateAnd(X, Builder.CreateNot(Op0)); + // (X | Y) ^ Y --> X & ~Y + // (Y | X) ^ Y --> X & ~Y + if (match(Op0, m_OneUse(m_c_Or(m_Value(X), m_Specific(Op1))))) + return BinaryOperator::CreateAnd(X, Builder.CreateNot(Op1)); - { - Value *A, *B; - if (match(Op0, m_OneUse(m_Or(m_Value(A), m_Value(B))))) { - if (A == Op1) // (B|A)^B == (A|B)^B - std::swap(A, B); - if (B == Op1) // (A|B)^B == A & ~B - return BinaryOperator::CreateAnd(A, Builder.CreateNot(Op1)); - } else if (match(Op0, m_OneUse(m_And(m_Value(A), m_Value(B))))) { - if (A == Op1) // (A&B)^A -> (B&A)^A - std::swap(A, B); - const APInt *C; - if (B == Op1 && // (B&A)^A == ~B & A - !match(Op1, m_APInt(C))) { // Canonical form is (B&C)^C - return BinaryOperator::CreateAnd(Builder.CreateNot(A), Op1); - } - } - } + // Y ^ (X & Y) --> ~X & Y + // Y ^ (Y & X) --> ~X & Y + if (match(Op1, m_OneUse(m_c_And(m_Value(X), m_Specific(Op0))))) + return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(X)); + // (X & Y) ^ Y --> ~X & Y + // (Y & X) ^ Y --> ~X & Y + // Canonical form is (X & C) ^ C; don't touch that. + // TODO: A 'not' op is better for analysis and codegen, but demanded bits must + // be fixed to prefer that (otherwise we get infinite looping). + if (!match(Op1, m_Constant()) && + match(Op0, m_OneUse(m_c_And(m_Value(X), m_Specific(Op1))))) + return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(X)); - { - Value *A, *B, *C, *D; - // (A ^ C)^(A | B) -> ((~A) & B) ^ C - if (match(Op0, m_Xor(m_Value(D), m_Value(C))) && - match(Op1, m_Or(m_Value(A), m_Value(B)))) { - if (D == A) - return BinaryOperator::CreateXor( - Builder.CreateAnd(Builder.CreateNot(A), B), C); - if (D == B) - return BinaryOperator::CreateXor( - Builder.CreateAnd(Builder.CreateNot(B), A), C); - } - // (A | B)^(A ^ C) -> ((~A) & B) ^ C - if (match(Op0, m_Or(m_Value(A), m_Value(B))) && - match(Op1, m_Xor(m_Value(D), m_Value(C)))) { - if (D == A) - return BinaryOperator::CreateXor( - Builder.CreateAnd(Builder.CreateNot(A), B), C); - if (D == B) - return BinaryOperator::CreateXor( - Builder.CreateAnd(Builder.CreateNot(B), A), C); - } - // (A & B) ^ (A ^ B) -> (A | B) - if (match(Op0, m_And(m_Value(A), m_Value(B))) && - match(Op1, m_c_Xor(m_Specific(A), m_Specific(B)))) - return BinaryOperator::CreateOr(A, B); - // (A ^ B) ^ (A & B) -> (A | B) - if (match(Op0, m_Xor(m_Value(A), m_Value(B))) && - match(Op1, m_c_And(m_Specific(A), m_Specific(B)))) - return BinaryOperator::CreateOr(A, B); - } + Value *A, *B, *C; + // (A ^ B) ^ (A | C) --> (~A & C) ^ B -- There are 4 commuted variants. + if (match(&I, m_c_Xor(m_OneUse(m_Xor(m_Value(A), m_Value(B))), + m_OneUse(m_c_Or(m_Deferred(A), m_Value(C)))))) + return BinaryOperator::CreateXor( + Builder.CreateAnd(Builder.CreateNot(A), C), B); + + // (A ^ B) ^ (B | C) --> (~B & C) ^ A -- There are 4 commuted variants. + if (match(&I, m_c_Xor(m_OneUse(m_Xor(m_Value(A), m_Value(B))), + m_OneUse(m_c_Or(m_Deferred(B), m_Value(C)))))) + return BinaryOperator::CreateXor( + Builder.CreateAnd(Builder.CreateNot(B), C), A); + + // (A & B) ^ (A ^ B) -> (A | B) + if (match(Op0, m_And(m_Value(A), m_Value(B))) && + match(Op1, m_c_Xor(m_Specific(A), m_Specific(B)))) + return BinaryOperator::CreateOr(A, B); + // (A ^ B) ^ (A & B) -> (A | B) + if (match(Op0, m_Xor(m_Value(A), m_Value(B))) && + match(Op1, m_c_And(m_Specific(A), m_Specific(B)))) + return BinaryOperator::CreateOr(A, B); // (A & ~B) ^ ~A -> ~(A & B) // (~B & A) ^ ~A -> ~(A & B) - Value *A, *B; if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) && match(Op1, m_Not(m_Specific(A)))) return BinaryOperator::CreateNot(Builder.CreateAnd(A, B)); @@ -2759,23 +2944,41 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { // %res = select i1 %cmp2, i32 %x, i32 %noty // // Same is applicable for smin/umax/umin. - { + if (match(Op1, m_AllOnes()) && Op0->hasOneUse()) { Value *LHS, *RHS; SelectPatternFlavor SPF = matchSelectPattern(Op0, LHS, RHS).Flavor; - if (Op0->hasOneUse() && SelectPatternResult::isMinOrMax(SPF) && - match(Op1, m_AllOnes())) { - - Value *X; - if (match(RHS, m_Not(m_Value(X)))) - std::swap(RHS, LHS); - - if (match(LHS, m_Not(m_Value(X)))) { + if (SelectPatternResult::isMinOrMax(SPF)) { + // It's possible we get here before the not has been simplified, so make + // sure the input to the not isn't freely invertible. + if (match(LHS, m_Not(m_Value(X))) && !IsFreeToInvert(X, X->hasOneUse())) { Value *NotY = Builder.CreateNot(RHS); return SelectInst::Create( Builder.CreateICmp(getInverseMinMaxPred(SPF), X, NotY), X, NotY); } + + // It's possible we get here before the not has been simplified, so make + // sure the input to the not isn't freely invertible. + if (match(RHS, m_Not(m_Value(Y))) && !IsFreeToInvert(Y, Y->hasOneUse())) { + Value *NotX = Builder.CreateNot(LHS); + return SelectInst::Create( + Builder.CreateICmp(getInverseMinMaxPred(SPF), NotX, Y), NotX, Y); + } + + // If both sides are freely invertible, then we can get rid of the xor + // completely. + if (IsFreeToInvert(LHS, !LHS->hasNUsesOrMore(3)) && + IsFreeToInvert(RHS, !RHS->hasNUsesOrMore(3))) { + Value *NotLHS = Builder.CreateNot(LHS); + Value *NotRHS = Builder.CreateNot(RHS); + return SelectInst::Create( + Builder.CreateICmp(getInverseMinMaxPred(SPF), NotLHS, NotRHS), + NotLHS, NotRHS); + } } } + if (Instruction *NewXor = sinkNotIntoXor(I, Builder)) + return NewXor; + return nullptr; } diff --git a/lib/Transforms/InstCombine/InstCombineCalls.cpp b/lib/Transforms/InstCombine/InstCombineCalls.cpp index cbfbd8a53993..aeb25d530d71 100644 --- a/lib/Transforms/InstCombine/InstCombineCalls.cpp +++ b/lib/Transforms/InstCombine/InstCombineCalls.cpp @@ -136,6 +136,14 @@ Instruction *InstCombiner::SimplifyAnyMemTransfer(AnyMemTransferInst *MI) { if (Size > 8 || (Size&(Size-1))) return nullptr; // If not 1/2/4/8 bytes, exit. + // If it is an atomic and alignment is less than the size then we will + // introduce the unaligned memory access which will be later transformed + // into libcall in CodeGen. This is not evident performance gain so disable + // it now. + if (isa<AtomicMemTransferInst>(MI)) + if (CopyDstAlign < Size || CopySrcAlign < Size) + return nullptr; + // Use an integer load+store unless we can find something better. unsigned SrcAddrSp = cast<PointerType>(MI->getArgOperand(1)->getType())->getAddressSpace(); @@ -174,6 +182,9 @@ Instruction *InstCombiner::SimplifyAnyMemTransfer(AnyMemTransferInst *MI) { MI->getMetadata(LLVMContext::MD_mem_parallel_loop_access); if (LoopMemParallelMD) L->setMetadata(LLVMContext::MD_mem_parallel_loop_access, LoopMemParallelMD); + MDNode *AccessGroupMD = MI->getMetadata(LLVMContext::MD_access_group); + if (AccessGroupMD) + L->setMetadata(LLVMContext::MD_access_group, AccessGroupMD); StoreInst *S = Builder.CreateStore(L, Dest); // Alignment from the mem intrinsic will be better, so use it. @@ -182,6 +193,8 @@ Instruction *InstCombiner::SimplifyAnyMemTransfer(AnyMemTransferInst *MI) { S->setMetadata(LLVMContext::MD_tbaa, CopyMD); if (LoopMemParallelMD) S->setMetadata(LLVMContext::MD_mem_parallel_loop_access, LoopMemParallelMD); + if (AccessGroupMD) + S->setMetadata(LLVMContext::MD_access_group, AccessGroupMD); if (auto *MT = dyn_cast<MemTransferInst>(MI)) { // non-atomics can be volatile @@ -215,6 +228,18 @@ Instruction *InstCombiner::SimplifyAnyMemSet(AnyMemSetInst *MI) { Alignment = MI->getDestAlignment(); assert(Len && "0-sized memory setting should be removed already."); + // Alignment 0 is identity for alignment 1 for memset, but not store. + if (Alignment == 0) + Alignment = 1; + + // If it is an atomic and alignment is less than the size then we will + // introduce the unaligned memory access which will be later transformed + // into libcall in CodeGen. This is not evident performance gain so disable + // it now. + if (isa<AtomicMemSetInst>(MI)) + if (Alignment < Len) + return nullptr; + // memset(s,c,n) -> store s, c (for n=1,2,4,8) if (Len <= 8 && isPowerOf2_32((uint32_t)Len)) { Type *ITy = IntegerType::get(MI->getContext(), Len*8); // n=1 -> i8. @@ -224,9 +249,6 @@ Instruction *InstCombiner::SimplifyAnyMemSet(AnyMemSetInst *MI) { Type *NewDstPtrTy = PointerType::get(ITy, DstAddrSp); Dest = Builder.CreateBitCast(Dest, NewDstPtrTy); - // Alignment 0 is identity for alignment 1 for memset, but not store. - if (Alignment == 0) Alignment = 1; - // Extract the fill value and store. uint64_t Fill = FillC->getZExtValue()*0x0101010101010101ULL; StoreInst *S = Builder.CreateStore(ConstantInt::get(ITy, Fill), Dest, @@ -648,7 +670,7 @@ static Value *simplifyX86round(IntrinsicInst &II, } Intrinsic::ID ID = (RoundControl == 2) ? Intrinsic::ceil : Intrinsic::floor; - Value *Res = Builder.CreateIntrinsic(ID, {Src}, &II); + Value *Res = Builder.CreateUnaryIntrinsic(ID, Src, &II); if (!IsScalar) { if (auto *C = dyn_cast<Constant>(Mask)) if (C->isAllOnesValue()) @@ -675,7 +697,8 @@ static Value *simplifyX86round(IntrinsicInst &II, return Builder.CreateInsertElement(Dst, Res, (uint64_t)0); } -static Value *simplifyX86movmsk(const IntrinsicInst &II) { +static Value *simplifyX86movmsk(const IntrinsicInst &II, + InstCombiner::BuilderTy &Builder) { Value *Arg = II.getArgOperand(0); Type *ResTy = II.getType(); Type *ArgTy = Arg->getType(); @@ -688,29 +711,46 @@ static Value *simplifyX86movmsk(const IntrinsicInst &II) { if (!ArgTy->isVectorTy()) return nullptr; - auto *C = dyn_cast<Constant>(Arg); - if (!C) - 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; - // 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; + auto *CInt = dyn_cast<ConstantInt>(COp); + auto *CFp = dyn_cast<ConstantFP>(COp); + if (!CInt && !CFp) + return nullptr; - auto *CInt = dyn_cast<ConstantInt>(COp); - auto *CFp = dyn_cast<ConstantFP>(COp); - if (!CInt && !CFp) - return nullptr; + if ((CInt && CInt->isNegative()) || (CFp && CFp->isNegative())) + Result.setBit(I); + } + return Constant::getIntegerValue(ResTy, Result); + } - if ((CInt && CInt->isNegative()) || (CFp && CFp->isNegative())) - Result.setBit(I); + // 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); } - return Constant::getIntegerValue(ResTy, Result); + return nullptr; } static Value *simplifyX86insertps(const IntrinsicInst &II, @@ -1133,82 +1173,6 @@ static Value *simplifyX86vpcom(const IntrinsicInst &II, return nullptr; } -static Value *simplifyMinnumMaxnum(const IntrinsicInst &II) { - Value *Arg0 = II.getArgOperand(0); - Value *Arg1 = II.getArgOperand(1); - - // fmin(x, x) -> x - if (Arg0 == Arg1) - return Arg0; - - const auto *C1 = dyn_cast<ConstantFP>(Arg1); - - // fmin(x, nan) -> x - if (C1 && C1->isNaN()) - return Arg0; - - // This is the value because if undef were NaN, we would return the other - // value and cannot return a NaN unless both operands are. - // - // fmin(undef, x) -> x - if (isa<UndefValue>(Arg0)) - return Arg1; - - // fmin(x, undef) -> x - if (isa<UndefValue>(Arg1)) - return Arg0; - - Value *X = nullptr; - Value *Y = nullptr; - if (II.getIntrinsicID() == Intrinsic::minnum) { - // fmin(x, fmin(x, y)) -> fmin(x, y) - // fmin(y, fmin(x, y)) -> fmin(x, y) - if (match(Arg1, m_FMin(m_Value(X), m_Value(Y)))) { - if (Arg0 == X || Arg0 == Y) - return Arg1; - } - - // fmin(fmin(x, y), x) -> fmin(x, y) - // fmin(fmin(x, y), y) -> fmin(x, y) - if (match(Arg0, m_FMin(m_Value(X), m_Value(Y)))) { - if (Arg1 == X || Arg1 == Y) - return Arg0; - } - - // TODO: fmin(nnan x, inf) -> x - // TODO: fmin(nnan ninf x, flt_max) -> x - if (C1 && C1->isInfinity()) { - // fmin(x, -inf) -> -inf - if (C1->isNegative()) - return Arg1; - } - } else { - assert(II.getIntrinsicID() == Intrinsic::maxnum); - // fmax(x, fmax(x, y)) -> fmax(x, y) - // fmax(y, fmax(x, y)) -> fmax(x, y) - if (match(Arg1, m_FMax(m_Value(X), m_Value(Y)))) { - if (Arg0 == X || Arg0 == Y) - return Arg1; - } - - // fmax(fmax(x, y), x) -> fmax(x, y) - // fmax(fmax(x, y), y) -> fmax(x, y) - if (match(Arg0, m_FMax(m_Value(X), m_Value(Y)))) { - if (Arg1 == X || Arg1 == Y) - return Arg0; - } - - // TODO: fmax(nnan x, -inf) -> x - // TODO: fmax(nnan ninf x, -flt_max) -> x - if (C1 && C1->isInfinity()) { - // fmax(x, inf) -> inf - if (!C1->isNegative()) - return Arg1; - } - } - return nullptr; -} - static bool maskIsAllOneOrUndef(Value *Mask) { auto *ConstMask = dyn_cast<Constant>(Mask); if (!ConstMask) @@ -1852,6 +1816,17 @@ Instruction *InstCombiner::visitVACopyInst(VACopyInst &I) { return nullptr; } +static Instruction *canonicalizeConstantArg0ToArg1(CallInst &Call) { + assert(Call.getNumArgOperands() > 1 && "Need at least 2 args to swap"); + Value *Arg0 = Call.getArgOperand(0), *Arg1 = Call.getArgOperand(1); + if (isa<Constant>(Arg0) && !isa<Constant>(Arg1)) { + Call.setArgOperand(0, Arg1); + Call.setArgOperand(1, Arg0); + return &Call; + } + return nullptr; +} + /// CallInst simplification. This mostly only handles folding of intrinsic /// instructions. For normal calls, it allows visitCallSite to do the heavy /// lifting. @@ -2005,18 +1980,49 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { return I; break; + 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; + + // 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_Zero()) || match(Op0, m_Undef())) + return BinaryOperator::CreateLShr( + Op1, ConstantInt::get(II->getType(), BitWidth - ShiftAmt)); + } + + // 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)); + KnownBits Op2Known(BitWidth); + if (SimplifyDemandedBits(II, 2, Op2Demanded, Op2Known)) + return &CI; + break; + } case Intrinsic::uadd_with_overflow: case Intrinsic::sadd_with_overflow: case Intrinsic::umul_with_overflow: case Intrinsic::smul_with_overflow: - if (isa<Constant>(II->getArgOperand(0)) && - !isa<Constant>(II->getArgOperand(1))) { - // Canonicalize constants into the RHS. - Value *LHS = II->getArgOperand(0); - II->setArgOperand(0, II->getArgOperand(1)); - II->setArgOperand(1, LHS); - return II; - } + if (Instruction *I = canonicalizeConstantArg0ToArg1(CI)) + return I; LLVM_FALLTHROUGH; case Intrinsic::usub_with_overflow: @@ -2034,34 +2040,164 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { break; } - case Intrinsic::minnum: - case Intrinsic::maxnum: { + case Intrinsic::uadd_sat: + case Intrinsic::sadd_sat: + if (Instruction *I = canonicalizeConstantArg0ToArg1(CI)) + return I; + LLVM_FALLTHROUGH; + case Intrinsic::usub_sat: + case Intrinsic::ssub_sat: { Value *Arg0 = II->getArgOperand(0); Value *Arg1 = II->getArgOperand(1); - // Canonicalize constants to the RHS. - if (isa<ConstantFP>(Arg0) && !isa<ConstantFP>(Arg1)) { - II->setArgOperand(0, Arg1); - II->setArgOperand(1, Arg0); - return II; + Intrinsic::ID IID = II->getIntrinsicID(); + + // 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; } - // FIXME: Simplifications should be in instsimplify. - if (Value *V = simplifyMinnumMaxnum(*II)) - return replaceInstUsesWith(*II, V); + // ssub.sat(X, C) -> sadd.sat(X, -C) if C != MIN + Constant *C; + if (IID == Intrinsic::ssub_sat && match(Arg1, m_Constant(C)) && + C->isNotMinSignedValue()) { + Value *NegVal = ConstantExpr::getNeg(C); + return replaceInstUsesWith( + *II, Builder.CreateBinaryIntrinsic( + Intrinsic::sadd_sat, Arg0, NegVal)); + } + + // sat(sat(X + Val2) + Val) -> sat(X + (Val+Val2)) + // sat(sat(X - Val2) - Val) -> sat(X - (Val+Val2)) + // if Val and Val2 have the same sign + if (auto *Other = dyn_cast<IntrinsicInst>(Arg0)) { + Value *X; + const APInt *Val, *Val2; + APInt NewVal; + bool IsUnsigned = + IID == Intrinsic::uadd_sat || IID == Intrinsic::usub_sat; + if (Other->getIntrinsicID() == II->getIntrinsicID() && + match(Arg1, m_APInt(Val)) && + match(Other->getArgOperand(0), m_Value(X)) && + match(Other->getArgOperand(1), m_APInt(Val2))) { + if (IsUnsigned) + NewVal = Val->uadd_sat(*Val2); + else if (Val->isNonNegative() == Val2->isNonNegative()) { + bool Overflow; + NewVal = Val->sadd_ov(*Val2, Overflow); + if (Overflow) { + // Both adds together may add more than SignedMaxValue + // without saturating the final result. + break; + } + } else { + // Cannot fold saturated addition with different signs. + break; + } + return replaceInstUsesWith( + *II, Builder.CreateBinaryIntrinsic( + IID, X, ConstantInt::get(II->getType(), NewVal))); + } + } + break; + } + + case Intrinsic::minnum: + case Intrinsic::maxnum: + case Intrinsic::minimum: + case Intrinsic::maximum: { + if (Instruction *I = canonicalizeConstantArg0ToArg1(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())) { // If both operands are negated, invert the call and negate the result: - // minnum(-X, -Y) --> -(maxnum(X, Y)) - // maxnum(-X, -Y) --> -(minnum(X, Y)) - Intrinsic::ID NewIID = II->getIntrinsicID() == Intrinsic::maxnum ? - Intrinsic::minnum : Intrinsic::maxnum; - Value *NewCall = Builder.CreateIntrinsic(NewIID, { X, Y }, II); + // min(-X, -Y) --> -(max(X, Y)) + // max(-X, -Y) --> -(min(X, Y)) + Intrinsic::ID NewIID; + switch (IID) { + case Intrinsic::maxnum: + NewIID = Intrinsic::minnum; + break; + case Intrinsic::minnum: + NewIID = Intrinsic::maxnum; + break; + case Intrinsic::maximum: + NewIID = Intrinsic::minimum; + break; + case Intrinsic::minimum: + NewIID = Intrinsic::maximum; + break; + default: + llvm_unreachable("unexpected intrinsic ID"); + } + Value *NewCall = Builder.CreateBinaryIntrinsic(NewIID, X, Y, II); Instruction *FNeg = BinaryOperator::CreateFNeg(NewCall); FNeg->copyIRFlags(II); return FNeg; } + + // m(m(X, C2), C1) -> m(X, C) + const APFloat *C1, *C2; + if (auto *M = dyn_cast<IntrinsicInst>(Arg0)) { + if (M->getIntrinsicID() == IID && match(Arg1, m_APFloat(C1)) && + ((match(M->getArgOperand(0), m_Value(X)) && + match(M->getArgOperand(1), m_APFloat(C2))) || + (match(M->getArgOperand(1), m_Value(X)) && + match(M->getArgOperand(0), m_APFloat(C2))))) { + APFloat Res(0.0); + switch (IID) { + case Intrinsic::maxnum: + Res = maxnum(*C1, *C2); + break; + case Intrinsic::minnum: + Res = minnum(*C1, *C2); + break; + case Intrinsic::maximum: + Res = maximum(*C1, *C2); + break; + case Intrinsic::minimum: + Res = minimum(*C1, *C2); + break; + default: + llvm_unreachable("unexpected intrinsic ID"); + } + Instruction *NewCall = Builder.CreateBinaryIntrinsic( + IID, X, ConstantFP::get(Arg0->getType(), Res)); + NewCall->copyIRFlags(II); + return replaceInstUsesWith(*II, NewCall); + } + } + break; } case Intrinsic::fmuladd: { @@ -2079,17 +2215,12 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { LLVM_FALLTHROUGH; } case Intrinsic::fma: { - Value *Src0 = II->getArgOperand(0); - Value *Src1 = II->getArgOperand(1); - - // Canonicalize constant multiply operand to Src1. - if (isa<Constant>(Src0) && !isa<Constant>(Src1)) { - II->setArgOperand(0, Src1); - II->setArgOperand(1, Src0); - std::swap(Src0, Src1); - } + if (Instruction *I = canonicalizeConstantArg0ToArg1(CI)) + return I; // fma fneg(x), fneg(y), z -> fma x, y, z + Value *Src0 = II->getArgOperand(0); + Value *Src1 = II->getArgOperand(1); Value *X, *Y; if (match(Src0, m_FNeg(m_Value(X))) && match(Src1, m_FNeg(m_Value(Y)))) { II->setArgOperand(0, X); @@ -2135,24 +2266,33 @@ 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.CreateIntrinsic(II->getIntrinsicID(), - { ExtSrc }, II); + Value *NarrowII = + Builder.CreateUnaryIntrinsic(II->getIntrinsicID(), ExtSrc, II); return new FPExtInst(NarrowII, II->getType()); } break; } case Intrinsic::cos: case Intrinsic::amdgcn_cos: { - Value *SrcSrc; + Value *X; Value *Src = II->getArgOperand(0); - if (match(Src, m_FNeg(m_Value(SrcSrc))) || - match(Src, m_FAbs(m_Value(SrcSrc)))) { + if (match(Src, m_FNeg(m_Value(X))) || match(Src, m_FAbs(m_Value(X)))) { // cos(-x) -> cos(x) // cos(fabs(x)) -> cos(x) - II->setArgOperand(0, SrcSrc); + II->setArgOperand(0, X); return II; } - + break; + } + case Intrinsic::sin: { + Value *X; + if (match(II->getArgOperand(0), m_OneUse(m_FNeg(m_Value(X))))) { + // sin(-x) --> -sin(x) + Value *NewSin = Builder.CreateUnaryIntrinsic(Intrinsic::sin, X, II); + Instruction *FNeg = BinaryOperator::CreateFNeg(NewSin); + FNeg->copyFastMathFlags(II); + return FNeg; + } break; } case Intrinsic::ppc_altivec_lvx: @@ -2382,7 +2522,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { case Intrinsic::x86_avx_movmsk_pd_256: case Intrinsic::x86_avx_movmsk_ps_256: case Intrinsic::x86_avx2_pmovmskb: - if (Value *V = simplifyX86movmsk(*II)) + if (Value *V = simplifyX86movmsk(*II, Builder)) return replaceInstUsesWith(*II, V); break; @@ -2922,16 +3062,10 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { case Intrinsic::x86_avx_blendv_ps_256: case Intrinsic::x86_avx_blendv_pd_256: case Intrinsic::x86_avx2_pblendvb: { - // Convert blendv* to vector selects if the mask is constant. - // This optimization is convoluted because the intrinsic is defined as - // getting a vector of floats or doubles for the ps and pd versions. - // FIXME: That should be changed. - + // fold (blend A, A, Mask) -> A Value *Op0 = II->getArgOperand(0); Value *Op1 = II->getArgOperand(1); Value *Mask = II->getArgOperand(2); - - // fold (blend A, A, Mask) -> A if (Op0 == Op1) return replaceInstUsesWith(CI, Op0); @@ -2944,6 +3078,33 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { Constant *NewSelector = getNegativeIsTrueBoolVec(ConstantMask); return SelectInst::Create(NewSelector, Op1, Op0, "blendv"); } + + // Convert to a vector select if we can bypass casts and find a boolean + // vector condition value. + Value *BoolVec; + Mask = peekThroughBitcast(Mask); + if (match(Mask, m_SExt(m_Value(BoolVec))) && + BoolVec->getType()->isVectorTy() && + BoolVec->getType()->getScalarSizeInBits() == 1) { + assert(Mask->getType()->getPrimitiveSizeInBits() == + II->getType()->getPrimitiveSizeInBits() && + "Not expecting mask and operands with different sizes"); + + unsigned NumMaskElts = Mask->getType()->getVectorNumElements(); + unsigned NumOperandElts = II->getType()->getVectorNumElements(); + if (NumMaskElts == NumOperandElts) + return SelectInst::Create(BoolVec, Op1, Op0); + + // If the mask has less elements than the operands, each mask bit maps to + // multiple elements of the operands. Bitcast back and forth. + if (NumMaskElts < NumOperandElts) { + Value *CastOp0 = Builder.CreateBitCast(Op0, Mask->getType()); + Value *CastOp1 = Builder.CreateBitCast(Op1, Mask->getType()); + Value *Sel = Builder.CreateSelect(BoolVec, CastOp1, CastOp0); + return new BitCastInst(Sel, II->getType()); + } + } + break; } @@ -3275,6 +3436,22 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { return replaceInstUsesWith(*II, FCmp); } + if (Mask == (N_ZERO | P_ZERO)) { + // Equivalent of == 0. + Value *FCmp = Builder.CreateFCmpOEQ( + Src0, ConstantFP::get(Src0->getType(), 0.0)); + + FCmp->takeName(II); + return replaceInstUsesWith(*II, FCmp); + } + + // fp_class (nnan x), qnan|snan|other -> fp_class (nnan x), other + if (((Mask & S_NAN) || (Mask & Q_NAN)) && isKnownNeverNaN(Src0, &TLI)) { + II->setArgOperand(1, ConstantInt::get(Src1->getType(), + Mask & ~(S_NAN | Q_NAN))); + return II; + } + const ConstantFP *CVal = dyn_cast<ConstantFP>(Src0); if (!CVal) { if (isa<UndefValue>(Src0)) @@ -3384,22 +3561,14 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { bool Signed = II->getIntrinsicID() == Intrinsic::amdgcn_sbfe; - // TODO: Also emit sub if only width is constant. - if (!CWidth && COffset && Offset == 0) { - Constant *KSize = ConstantInt::get(COffset->getType(), IntSize); - Value *ShiftVal = Builder.CreateSub(KSize, II->getArgOperand(2)); - ShiftVal = Builder.CreateZExt(ShiftVal, II->getType()); - - Value *Shl = Builder.CreateShl(Src, ShiftVal); - Value *RightShift = Signed ? Builder.CreateAShr(Shl, ShiftVal) - : Builder.CreateLShr(Shl, ShiftVal); - RightShift->takeName(II); - return replaceInstUsesWith(*II, RightShift); - } - if (!CWidth || !COffset) break; + // The case of Width == 0 is handled above, which makes this tranformation + // safe. If Width == 0, then the ashr and lshr instructions become poison + // value since the shift amount would be equal to the bit size. + assert(Width != 0); + // TODO: This allows folding to undef when the hardware has specific // behavior? if (Offset + Width < IntSize) { @@ -3603,6 +3772,38 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { Intrinsic::ID NewIID = CmpInst::isFPPredicate(SrcPred) ? Intrinsic::amdgcn_fcmp : Intrinsic::amdgcn_icmp; + Type *Ty = SrcLHS->getType(); + if (auto *CmpType = dyn_cast<IntegerType>(Ty)) { + // Promote to next legal integer type. + unsigned Width = CmpType->getBitWidth(); + unsigned NewWidth = Width; + + // Don't do anything for i1 comparisons. + if (Width == 1) + break; + + if (Width <= 16) + NewWidth = 16; + else if (Width <= 32) + NewWidth = 32; + else if (Width <= 64) + NewWidth = 64; + else if (Width > 64) + break; // Can't handle this. + + if (Width != NewWidth) { + IntegerType *CmpTy = Builder.getIntNTy(NewWidth); + if (CmpInst::isSigned(SrcPred)) { + SrcLHS = Builder.CreateSExt(SrcLHS, CmpTy); + SrcRHS = Builder.CreateSExt(SrcRHS, CmpTy); + } else { + SrcLHS = Builder.CreateZExt(SrcLHS, CmpTy); + SrcRHS = Builder.CreateZExt(SrcRHS, CmpTy); + } + } + } else if (!Ty->isFloatTy() && !Ty->isDoubleTy() && !Ty->isHalfTy()) + break; + Value *NewF = Intrinsic::getDeclaration(II->getModule(), NewIID, SrcLHS->getType()); Value *Args[] = { SrcLHS, SrcRHS, @@ -3661,7 +3862,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { // Scan down this block to see if there is another stack restore in the // same block without an intervening call/alloca. BasicBlock::iterator BI(II); - TerminatorInst *TI = II->getParent()->getTerminator(); + Instruction *TI = II->getParent()->getTerminator(); bool CannotRemove = false; for (++BI; &*BI != TI; ++BI) { if (isa<AllocaInst>(BI)) { @@ -3788,8 +3989,11 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { return replaceInstUsesWith(*II, ConstantPointerNull::get(PT)); // isKnownNonNull -> nonnull attribute - if (isKnownNonZero(DerivedPtr, DL, 0, &AC, II, &DT)) + if (!II->hasRetAttr(Attribute::NonNull) && + isKnownNonZero(DerivedPtr, DL, 0, &AC, II, &DT)) { II->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull); + return II; + } } // TODO: bitcast(relocate(p)) -> relocate(bitcast(p)) @@ -3889,7 +4093,11 @@ Instruction *InstCombiner::tryOptimizeCall(CallInst *CI) { auto InstCombineRAUW = [this](Instruction *From, Value *With) { replaceInstUsesWith(*From, With); }; - LibCallSimplifier Simplifier(DL, &TLI, ORE, InstCombineRAUW); + auto InstCombineErase = [this](Instruction *I) { + eraseInstFromFunction(*I); + }; + LibCallSimplifier Simplifier(DL, &TLI, ORE, InstCombineRAUW, + InstCombineErase); if (Value *With = Simplifier.optimizeCall(CI)) { ++NumSimplified; return CI->use_empty() ? CI : replaceInstUsesWith(*CI, With); diff --git a/lib/Transforms/InstCombine/InstCombineCasts.cpp b/lib/Transforms/InstCombine/InstCombineCasts.cpp index fd59c3a7c0c3..1201ac196ec0 100644 --- a/lib/Transforms/InstCombine/InstCombineCasts.cpp +++ b/lib/Transforms/InstCombine/InstCombineCasts.cpp @@ -492,12 +492,19 @@ static Instruction *foldVecTruncToExtElt(TruncInst &Trunc, InstCombiner &IC) { } /// Rotate left/right may occur in a wider type than necessary because of type -/// promotion rules. Try to narrow all of the component instructions. +/// promotion rules. Try to narrow the inputs and convert to funnel shift. Instruction *InstCombiner::narrowRotate(TruncInst &Trunc) { assert((isa<VectorType>(Trunc.getSrcTy()) || shouldChangeType(Trunc.getSrcTy(), Trunc.getType())) && "Don't narrow to an illegal scalar type"); + // Bail out on strange types. It is possible to handle some of these patterns + // even with non-power-of-2 sizes, but it is not a likely scenario. + Type *DestTy = Trunc.getType(); + unsigned NarrowWidth = DestTy->getScalarSizeInBits(); + if (!isPowerOf2_32(NarrowWidth)) + return nullptr; + // First, find an or'd pair of opposite shifts with the same shifted operand: // trunc (or (lshr ShVal, ShAmt0), (shl ShVal, ShAmt1)) Value *Or0, *Or1; @@ -514,22 +521,38 @@ Instruction *InstCombiner::narrowRotate(TruncInst &Trunc) { if (ShiftOpcode0 == ShiftOpcode1) return nullptr; - // The shift amounts must add up to the narrow bit width. - Value *ShAmt; - bool SubIsOnLHS; - Type *DestTy = Trunc.getType(); - unsigned NarrowWidth = DestTy->getScalarSizeInBits(); - if (match(ShAmt0, - m_OneUse(m_Sub(m_SpecificInt(NarrowWidth), m_Specific(ShAmt1))))) { - ShAmt = ShAmt1; - SubIsOnLHS = true; - } else if (match(ShAmt1, m_OneUse(m_Sub(m_SpecificInt(NarrowWidth), - m_Specific(ShAmt0))))) { - ShAmt = ShAmt0; - SubIsOnLHS = false; - } else { + // Match the shift amount operands for a rotate pattern. This always matches + // a subtraction on the R operand. + auto matchShiftAmount = [](Value *L, Value *R, unsigned Width) -> Value * { + // The shift amounts may add up to the narrow bit width: + // (shl ShVal, L) | (lshr ShVal, Width - L) + if (match(R, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(L))))) + return L; + + // The shift amount may be masked with negation: + // (shl ShVal, (X & (Width - 1))) | (lshr ShVal, ((-X) & (Width - 1))) + Value *X; + unsigned Mask = Width - 1; + if (match(L, m_And(m_Value(X), m_SpecificInt(Mask))) && + match(R, m_And(m_Neg(m_Specific(X)), m_SpecificInt(Mask)))) + return X; + + // Same as above, but the shift amount may be extended after masking: + if (match(L, m_ZExt(m_And(m_Value(X), m_SpecificInt(Mask)))) && + match(R, m_ZExt(m_And(m_Neg(m_Specific(X)), m_SpecificInt(Mask))))) + return X; + return nullptr; + }; + + Value *ShAmt = matchShiftAmount(ShAmt0, ShAmt1, NarrowWidth); + bool SubIsOnLHS = false; + if (!ShAmt) { + ShAmt = matchShiftAmount(ShAmt1, ShAmt0, NarrowWidth); + SubIsOnLHS = true; } + if (!ShAmt) + return nullptr; // The shifted value must have high zeros in the wide type. Typically, this // will be a zext, but it could also be the result of an 'and' or 'shift'. @@ -540,23 +563,15 @@ Instruction *InstCombiner::narrowRotate(TruncInst &Trunc) { // We have an unnecessarily wide rotate! // trunc (or (lshr ShVal, ShAmt), (shl ShVal, BitWidth - ShAmt)) - // Narrow it down to eliminate the zext/trunc: - // or (lshr trunc(ShVal), ShAmt0'), (shl trunc(ShVal), ShAmt1') + // Narrow the inputs and convert to funnel shift intrinsic: + // llvm.fshl.i8(trunc(ShVal), trunc(ShVal), trunc(ShAmt)) Value *NarrowShAmt = Builder.CreateTrunc(ShAmt, DestTy); - Value *NegShAmt = Builder.CreateNeg(NarrowShAmt); - - // Mask both shift amounts to ensure there's no UB from oversized shifts. - Constant *MaskC = ConstantInt::get(DestTy, NarrowWidth - 1); - Value *MaskedShAmt = Builder.CreateAnd(NarrowShAmt, MaskC); - Value *MaskedNegShAmt = Builder.CreateAnd(NegShAmt, MaskC); - - // Truncate the original value and use narrow ops. Value *X = Builder.CreateTrunc(ShVal, DestTy); - Value *NarrowShAmt0 = SubIsOnLHS ? MaskedNegShAmt : MaskedShAmt; - Value *NarrowShAmt1 = SubIsOnLHS ? MaskedShAmt : MaskedNegShAmt; - Value *NarrowSh0 = Builder.CreateBinOp(ShiftOpcode0, X, NarrowShAmt0); - Value *NarrowSh1 = Builder.CreateBinOp(ShiftOpcode1, X, NarrowShAmt1); - return BinaryOperator::CreateOr(NarrowSh0, NarrowSh1); + bool IsFshl = (!SubIsOnLHS && ShiftOpcode0 == BinaryOperator::Shl) || + (SubIsOnLHS && ShiftOpcode1 == BinaryOperator::Shl); + Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr; + Function *F = Intrinsic::getDeclaration(Trunc.getModule(), IID, DestTy); + return IntrinsicInst::Create(F, { X, X, NarrowShAmt }); } /// Try to narrow the width of math or bitwise logic instructions by pulling a @@ -706,12 +721,35 @@ Instruction *InstCombiner::visitTrunc(TruncInst &CI) { if (SimplifyDemandedInstructionBits(CI)) return &CI; - // Canonicalize trunc x to i1 -> (icmp ne (and x, 1), 0), likewise for vector. if (DestTy->getScalarSizeInBits() == 1) { - Constant *One = ConstantInt::get(SrcTy, 1); - Src = Builder.CreateAnd(Src, One); Value *Zero = Constant::getNullValue(Src->getType()); - return new ICmpInst(ICmpInst::ICMP_NE, Src, Zero); + if (DestTy->isIntegerTy()) { + // Canonicalize trunc x to i1 -> icmp ne (and x, 1), 0 (scalar only). + // TODO: We canonicalize to more instructions here because we are probably + // lacking equivalent analysis for trunc relative to icmp. There may also + // be codegen concerns. If those trunc limitations were removed, we could + // remove this transform. + Value *And = Builder.CreateAnd(Src, ConstantInt::get(SrcTy, 1)); + return new ICmpInst(ICmpInst::ICMP_NE, And, Zero); + } + + // For vectors, we do not canonicalize all truncs to icmp, so optimize + // patterns that would be covered within visitICmpInst. + Value *X; + const APInt *C; + if (match(Src, m_OneUse(m_LShr(m_Value(X), m_APInt(C))))) { + // trunc (lshr X, C) to i1 --> icmp ne (and X, C'), 0 + APInt MaskC = APInt(SrcTy->getScalarSizeInBits(), 1).shl(*C); + Value *And = Builder.CreateAnd(X, ConstantInt::get(SrcTy, MaskC)); + return new ICmpInst(ICmpInst::ICMP_NE, And, Zero); + } + if (match(Src, m_OneUse(m_c_Or(m_LShr(m_Value(X), m_APInt(C)), + m_Deferred(X))))) { + // trunc (or (lshr X, C), X) to i1 --> icmp ne (and X, C'), 0 + APInt MaskC = APInt(SrcTy->getScalarSizeInBits(), 1).shl(*C) | 1; + Value *And = Builder.CreateAnd(X, ConstantInt::get(SrcTy, MaskC)); + return new ICmpInst(ICmpInst::ICMP_NE, And, Zero); + } } // FIXME: Maybe combine the next two transforms to handle the no cast case @@ -1061,12 +1099,9 @@ Instruction *InstCombiner::visitZExt(ZExtInst &CI) { Value *Src = CI.getOperand(0); Type *SrcTy = Src->getType(), *DestTy = CI.getType(); - // Attempt to extend the entire input expression tree to the destination - // type. Only do this if the dest type is a simple type, don't convert the - // expression tree to something weird like i93 unless the source is also - // strange. + // Try to extend the entire expression tree to the wide destination type. unsigned BitsToClear; - if ((DestTy->isVectorTy() || shouldChangeType(SrcTy, DestTy)) && + if (shouldChangeType(SrcTy, DestTy) && canEvaluateZExtd(Src, DestTy, BitsToClear, *this, &CI)) { assert(BitsToClear <= SrcTy->getScalarSizeInBits() && "Can't clear more bits than in SrcTy"); @@ -1343,12 +1378,8 @@ Instruction *InstCombiner::visitSExt(SExtInst &CI) { return replaceInstUsesWith(CI, ZExt); } - // Attempt to extend the entire input expression tree to the destination - // type. Only do this if the dest type is a simple type, don't convert the - // expression tree to something weird like i93 unless the source is also - // strange. - if ((DestTy->isVectorTy() || shouldChangeType(SrcTy, DestTy)) && - canEvaluateSExtd(Src, DestTy)) { + // Try to extend the entire expression tree to the wide destination type. + if (shouldChangeType(SrcTy, DestTy) && canEvaluateSExtd(Src, DestTy)) { // Okay, we can transform this! Insert the new expression now. LLVM_DEBUG( dbgs() << "ICE: EvaluateInDifferentType converting expression type" @@ -1589,8 +1620,9 @@ Instruction *InstCombiner::visitFPTrunc(FPTruncInst &FPT) { } // (fptrunc (fneg x)) -> (fneg (fptrunc x)) - if (BinaryOperator::isFNeg(OpI)) { - Value *InnerTrunc = Builder.CreateFPTrunc(OpI->getOperand(1), Ty); + Value *X; + if (match(OpI, m_FNeg(m_Value(X)))) { + Value *InnerTrunc = Builder.CreateFPTrunc(X, Ty); return BinaryOperator::CreateFNegFMF(InnerTrunc, OpI); } } diff --git a/lib/Transforms/InstCombine/InstCombineCompares.cpp b/lib/Transforms/InstCombine/InstCombineCompares.cpp index 6de92a4842ab..b5bbb09935e2 100644 --- a/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ b/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -522,11 +522,9 @@ static Value *evaluateGEPOffsetExpression(User *GEP, InstCombiner &IC, } // Otherwise, there is an index. The computation we will do will be modulo - // the pointer size, so get it. - uint64_t PtrSizeMask = ~0ULL >> (64-IntPtrWidth); - - Offset &= PtrSizeMask; - VariableScale &= PtrSizeMask; + // the pointer size. + Offset = SignExtend64(Offset, IntPtrWidth); + VariableScale = SignExtend64(VariableScale, IntPtrWidth); // To do this transformation, any constant index must be a multiple of the // variable scale factor. For example, we can evaluate "12 + 4*i" as "3 + i", @@ -909,7 +907,8 @@ Instruction *InstCombiner::foldGEPICmp(GEPOperator *GEPLHS, Value *RHS, } // If all indices are the same, just compare the base pointers. - if (IndicesTheSame) + Type *BaseType = GEPLHS->getOperand(0)->getType(); + if (IndicesTheSame && CmpInst::makeCmpResultType(BaseType) == I.getType()) return new ICmpInst(Cond, GEPLHS->getOperand(0), GEPRHS->getOperand(0)); // If we're comparing GEPs with two base pointers that only differ in type @@ -976,7 +975,7 @@ Instruction *InstCombiner::foldGEPICmp(GEPOperator *GEPLHS, Value *RHS, if (NumDifferences == 0) // SAME GEP? return replaceInstUsesWith(I, // No comparison is needed here. - Builder.getInt1(ICmpInst::isTrueWhenEqual(Cond))); + ConstantInt::get(I.getType(), ICmpInst::isTrueWhenEqual(Cond))); else if (NumDifferences == 1 && GEPsInBounds) { Value *LHSV = GEPLHS->getOperand(DiffOperand); @@ -1079,19 +1078,20 @@ Instruction *InstCombiner::foldAllocaCmp(ICmpInst &ICI, ConstantInt::get(CmpTy, !CmpInst::isTrueWhenEqual(ICI.getPredicate()))); } -/// Fold "icmp pred (X+CI), X". -Instruction *InstCombiner::foldICmpAddOpConst(Value *X, ConstantInt *CI, +/// Fold "icmp pred (X+C), X". +Instruction *InstCombiner::foldICmpAddOpConst(Value *X, const APInt &C, ICmpInst::Predicate Pred) { // From this point on, we know that (X+C <= X) --> (X+C < X) because C != 0, // so the values can never be equal. Similarly for all other "or equals" // operators. + assert(!!C && "C should not be zero!"); // (X+1) <u X --> X >u (MAXUINT-1) --> X == 255 // (X+2) <u X --> X >u (MAXUINT-2) --> X > 253 // (X+MAXUINT) <u X --> X >u (MAXUINT-MAXUINT) --> X != 0 if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE) { - Value *R = - ConstantExpr::getSub(ConstantInt::getAllOnesValue(CI->getType()), CI); + Constant *R = ConstantInt::get(X->getType(), + APInt::getMaxValue(C.getBitWidth()) - C); return new ICmpInst(ICmpInst::ICMP_UGT, X, R); } @@ -1099,11 +1099,10 @@ Instruction *InstCombiner::foldICmpAddOpConst(Value *X, ConstantInt *CI, // (X+2) >u X --> X <u (0-2) --> X <u 254 // (X+MAXUINT) >u X --> X <u (0-MAXUINT) --> X <u 1 --> X == 0 if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE) - return new ICmpInst(ICmpInst::ICMP_ULT, X, ConstantExpr::getNeg(CI)); + return new ICmpInst(ICmpInst::ICMP_ULT, X, + ConstantInt::get(X->getType(), -C)); - unsigned BitWidth = CI->getType()->getPrimitiveSizeInBits(); - ConstantInt *SMax = ConstantInt::get(X->getContext(), - APInt::getSignedMaxValue(BitWidth)); + APInt SMax = APInt::getSignedMaxValue(C.getBitWidth()); // (X+ 1) <s X --> X >s (MAXSINT-1) --> X == 127 // (X+ 2) <s X --> X >s (MAXSINT-2) --> X >s 125 @@ -1112,7 +1111,8 @@ Instruction *InstCombiner::foldICmpAddOpConst(Value *X, ConstantInt *CI, // (X+ -2) <s X --> X >s (MAXSINT- -2) --> X >s 126 // (X+ -1) <s X --> X >s (MAXSINT- -1) --> X != 127 if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE) - return new ICmpInst(ICmpInst::ICMP_SGT, X, ConstantExpr::getSub(SMax, CI)); + return new ICmpInst(ICmpInst::ICMP_SGT, X, + ConstantInt::get(X->getType(), SMax - C)); // (X+ 1) >s X --> X <s (MAXSINT-(1-1)) --> X != 127 // (X+ 2) >s X --> X <s (MAXSINT-(2-1)) --> X <s 126 @@ -1122,8 +1122,8 @@ Instruction *InstCombiner::foldICmpAddOpConst(Value *X, ConstantInt *CI, // (X+ -1) >s X --> X <s (MAXSINT-(-1-1)) --> X == -128 assert(Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE); - Constant *C = Builder.getInt(CI->getValue() - 1); - return new ICmpInst(ICmpInst::ICMP_SLT, X, ConstantExpr::getSub(SMax, C)); + return new ICmpInst(ICmpInst::ICMP_SLT, X, + ConstantInt::get(X->getType(), SMax - (C - 1))); } /// Handle "(icmp eq/ne (ashr/lshr AP2, A), AP1)" -> @@ -1333,17 +1333,12 @@ Instruction *InstCombiner::foldICmpWithZero(ICmpInst &Cmp) { return nullptr; } -// Fold icmp Pred X, C. +/// Fold icmp Pred X, C. +/// TODO: This code structure does not make sense. The saturating add fold +/// should be moved to some other helper and extended as noted below (it is also +/// possible that code has been made unnecessary - do we canonicalize IR to +/// overflow/saturating intrinsics or not?). Instruction *InstCombiner::foldICmpWithConstant(ICmpInst &Cmp) { - CmpInst::Predicate Pred = Cmp.getPredicate(); - Value *X = Cmp.getOperand(0); - - const APInt *C; - if (!match(Cmp.getOperand(1), m_APInt(C))) - return nullptr; - - Value *A = nullptr, *B = nullptr; - // Match the following pattern, which is a common idiom when writing // overflow-safe integer arithmetic functions. The source performs an addition // in wider type and explicitly checks for overflow using comparisons against @@ -1355,37 +1350,62 @@ Instruction *InstCombiner::foldICmpWithConstant(ICmpInst &Cmp) { // // sum = a + b // if (sum+128 >u 255) ... -> llvm.sadd.with.overflow.i8 - { - ConstantInt *CI2; // I = icmp ugt (add (add A, B), CI2), CI - if (Pred == ICmpInst::ICMP_UGT && - match(X, m_Add(m_Add(m_Value(A), m_Value(B)), m_ConstantInt(CI2)))) - if (Instruction *Res = processUGT_ADDCST_ADD( - Cmp, A, B, CI2, cast<ConstantInt>(Cmp.getOperand(1)), *this)) - return Res; - } + CmpInst::Predicate Pred = Cmp.getPredicate(); + Value *Op0 = Cmp.getOperand(0), *Op1 = Cmp.getOperand(1); + Value *A, *B; + ConstantInt *CI, *CI2; // I = icmp ugt (add (add A, B), CI2), CI + if (Pred == ICmpInst::ICMP_UGT && match(Op1, m_ConstantInt(CI)) && + match(Op0, m_Add(m_Add(m_Value(A), m_Value(B)), m_ConstantInt(CI2)))) + if (Instruction *Res = processUGT_ADDCST_ADD(Cmp, A, B, CI2, CI, *this)) + return Res; + + return nullptr; +} - // FIXME: Use m_APInt to allow folds for splat constants. - ConstantInt *CI = dyn_cast<ConstantInt>(Cmp.getOperand(1)); - if (!CI) +/// Canonicalize icmp instructions based on dominating conditions. +Instruction *InstCombiner::foldICmpWithDominatingICmp(ICmpInst &Cmp) { + // This is a cheap/incomplete check for dominance - just match a single + // predecessor with a conditional branch. + BasicBlock *CmpBB = Cmp.getParent(); + BasicBlock *DomBB = CmpBB->getSinglePredecessor(); + if (!DomBB) return nullptr; - // Canonicalize icmp instructions based on dominating conditions. - BasicBlock *Parent = Cmp.getParent(); - BasicBlock *Dom = Parent->getSinglePredecessor(); - auto *BI = Dom ? dyn_cast<BranchInst>(Dom->getTerminator()) : nullptr; - ICmpInst::Predicate Pred2; + Value *DomCond; BasicBlock *TrueBB, *FalseBB; - ConstantInt *CI2; - if (BI && match(BI, m_Br(m_ICmp(Pred2, m_Specific(X), m_ConstantInt(CI2)), - TrueBB, FalseBB)) && - TrueBB != FalseBB) { - ConstantRange CR = - ConstantRange::makeAllowedICmpRegion(Pred, CI->getValue()); + if (!match(DomBB->getTerminator(), m_Br(m_Value(DomCond), TrueBB, FalseBB))) + return nullptr; + + assert((TrueBB == CmpBB || FalseBB == CmpBB) && + "Predecessor block does not point to successor?"); + + // The branch should get simplified. Don't bother simplifying this condition. + if (TrueBB == FalseBB) + return nullptr; + + // Try to simplify this compare to T/F based on the dominating condition. + Optional<bool> Imp = isImpliedCondition(DomCond, &Cmp, DL, TrueBB == CmpBB); + if (Imp) + return replaceInstUsesWith(Cmp, ConstantInt::get(Cmp.getType(), *Imp)); + + CmpInst::Predicate Pred = Cmp.getPredicate(); + Value *X = Cmp.getOperand(0), *Y = Cmp.getOperand(1); + ICmpInst::Predicate DomPred; + const APInt *C, *DomC; + if (match(DomCond, m_ICmp(DomPred, m_Specific(X), m_APInt(DomC))) && + match(Y, m_APInt(C))) { + // We have 2 compares of a variable with constants. Calculate the constant + // ranges of those compares to see if we can transform the 2nd compare: + // DomBB: + // DomCond = icmp DomPred X, DomC + // br DomCond, CmpBB, FalseBB + // CmpBB: + // Cmp = icmp Pred X, C + ConstantRange CR = ConstantRange::makeAllowedICmpRegion(Pred, *C); ConstantRange DominatingCR = - (Parent == TrueBB) - ? ConstantRange::makeExactICmpRegion(Pred2, CI2->getValue()) - : ConstantRange::makeExactICmpRegion( - CmpInst::getInversePredicate(Pred2), CI2->getValue()); + (CmpBB == TrueBB) ? ConstantRange::makeExactICmpRegion(DomPred, *DomC) + : ConstantRange::makeExactICmpRegion( + CmpInst::getInversePredicate(DomPred), *DomC); ConstantRange Intersection = DominatingCR.intersectWith(CR); ConstantRange Difference = DominatingCR.difference(CR); if (Intersection.isEmptySet()) @@ -1393,23 +1413,20 @@ Instruction *InstCombiner::foldICmpWithConstant(ICmpInst &Cmp) { if (Difference.isEmptySet()) return replaceInstUsesWith(Cmp, Builder.getTrue()); - // If this is a normal comparison, it demands all bits. If it is a sign - // bit comparison, it only demands the sign bit. - bool UnusedBit; - bool IsSignBit = isSignBitCheck(Pred, CI->getValue(), UnusedBit); - // Canonicalizing a sign bit comparison that gets used in a branch, // pessimizes codegen by generating branch on zero instruction instead // of a test and branch. So we avoid canonicalizing in such situations // because test and branch instruction has better branch displacement // than compare and branch instruction. + bool UnusedBit; + bool IsSignBit = isSignBitCheck(Pred, *C, UnusedBit); if (Cmp.isEquality() || (IsSignBit && hasBranchUse(Cmp))) return nullptr; - if (auto *AI = Intersection.getSingleElement()) - return new ICmpInst(ICmpInst::ICMP_EQ, X, Builder.getInt(*AI)); - if (auto *AD = Difference.getSingleElement()) - return new ICmpInst(ICmpInst::ICMP_NE, X, Builder.getInt(*AD)); + if (const APInt *EqC = Intersection.getSingleElement()) + return new ICmpInst(ICmpInst::ICMP_EQ, X, Builder.getInt(*EqC)); + if (const APInt *NeC = Difference.getSingleElement()) + return new ICmpInst(ICmpInst::ICMP_NE, X, Builder.getInt(*NeC)); } return nullptr; @@ -1498,16 +1515,25 @@ Instruction *InstCombiner::foldICmpXorConstant(ICmpInst &Cmp, } } - // (icmp ugt (xor X, C), ~C) -> (icmp ult X, C) - // iff -C is a power of 2 - if (Pred == ICmpInst::ICMP_UGT && *XorC == ~C && (C + 1).isPowerOf2()) - return new ICmpInst(ICmpInst::ICMP_ULT, X, Y); - - // (icmp ult (xor X, C), -C) -> (icmp uge X, C) - // iff -C is a power of 2 - if (Pred == ICmpInst::ICMP_ULT && *XorC == -C && C.isPowerOf2()) - return new ICmpInst(ICmpInst::ICMP_UGE, X, Y); - + // Mask constant magic can eliminate an 'xor' with unsigned compares. + if (Pred == ICmpInst::ICMP_UGT) { + // (xor X, ~C) >u C --> X <u ~C (when C+1 is a power of 2) + if (*XorC == ~C && (C + 1).isPowerOf2()) + return new ICmpInst(ICmpInst::ICMP_ULT, X, Y); + // (xor X, C) >u C --> X >u C (when C+1 is a power of 2) + if (*XorC == C && (C + 1).isPowerOf2()) + return new ICmpInst(ICmpInst::ICMP_UGT, X, Y); + } + if (Pred == ICmpInst::ICMP_ULT) { + // (xor X, -C) <u C --> X >u ~C (when C is a power of 2) + if (*XorC == -C && C.isPowerOf2()) + return new ICmpInst(ICmpInst::ICMP_UGT, X, + ConstantInt::get(X->getType(), ~C)); + // (xor X, C) <u C --> X >u ~C (when -C is a power of 2) + if (*XorC == C && (-C).isPowerOf2()) + return new ICmpInst(ICmpInst::ICMP_UGT, X, + ConstantInt::get(X->getType(), ~C)); + } return nullptr; } @@ -1598,6 +1624,13 @@ Instruction *InstCombiner::foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And, Instruction *InstCombiner::foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And, const APInt &C1) { + // 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())) + return new TruncInst(And->getOperand(0), Cmp.getType()); + const APInt *C2; if (!match(And->getOperand(1), m_APInt(C2))) return nullptr; @@ -2336,13 +2369,19 @@ Instruction *InstCombiner::foldICmpAddConstant(ICmpInst &Cmp, Type *Ty = Add->getType(); CmpInst::Predicate Pred = Cmp.getPredicate(); + if (!Add->hasOneUse()) + return nullptr; + // If the add does not wrap, we can always adjust the compare by subtracting - // the constants. Equality comparisons are handled elsewhere. SGE/SLE are - // canonicalized to SGT/SLT. - if (Add->hasNoSignedWrap() && - (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLT)) { + // the constants. Equality comparisons are handled elsewhere. SGE/SLE/UGE/ULE + // are canonicalized to SGT/SLT/UGT/ULT. + if ((Add->hasNoSignedWrap() && + (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLT)) || + (Add->hasNoUnsignedWrap() && + (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_ULT))) { bool Overflow; - APInt NewC = C.ssub_ov(*C2, Overflow); + APInt NewC = + Cmp.isSigned() ? C.ssub_ov(*C2, Overflow) : C.usub_ov(*C2, Overflow); // If there is overflow, the result must be true or false. // TODO: Can we assert there is no overflow because InstSimplify always // handles those cases? @@ -2366,9 +2405,6 @@ Instruction *InstCombiner::foldICmpAddConstant(ICmpInst &Cmp, return new ICmpInst(ICmpInst::ICMP_UGE, X, ConstantInt::get(Ty, Lower)); } - if (!Add->hasOneUse()) - return nullptr; - // X+C <u C2 -> (X & -C2) == C // iff C & (C2-1) == 0 // C2 is a power of 2 @@ -2729,6 +2765,7 @@ Instruction *InstCombiner::foldICmpIntrinsicWithConstant(ICmpInst &Cmp, // Handle icmp {eq|ne} <intrinsic>, Constant. Type *Ty = II->getType(); + unsigned BitWidth = C.getBitWidth(); switch (II->getIntrinsicID()) { case Intrinsic::bswap: Worklist.Add(II); @@ -2737,21 +2774,39 @@ Instruction *InstCombiner::foldICmpIntrinsicWithConstant(ICmpInst &Cmp, return &Cmp; case Intrinsic::ctlz: - case Intrinsic::cttz: + case Intrinsic::cttz: { // ctz(A) == bitwidth(A) -> A == 0 and likewise for != - if (C == C.getBitWidth()) { + if (C == BitWidth) { Worklist.Add(II); Cmp.setOperand(0, II->getArgOperand(0)); Cmp.setOperand(1, ConstantInt::getNullValue(Ty)); return &Cmp; } + + // ctz(A) == C -> A & Mask1 == Mask2, where Mask2 only has bit C set + // and Mask1 has bits 0..C+1 set. Similar for ctl, but for high bits. + // Limit to one use to ensure we don't increase instruction count. + unsigned Num = C.getLimitedValue(BitWidth); + if (Num != BitWidth && II->hasOneUse()) { + bool IsTrailing = II->getIntrinsicID() == Intrinsic::cttz; + APInt Mask1 = IsTrailing ? APInt::getLowBitsSet(BitWidth, Num + 1) + : APInt::getHighBitsSet(BitWidth, Num + 1); + APInt Mask2 = IsTrailing + ? APInt::getOneBitSet(BitWidth, Num) + : APInt::getOneBitSet(BitWidth, BitWidth - Num - 1); + Cmp.setOperand(0, Builder.CreateAnd(II->getArgOperand(0), Mask1)); + Cmp.setOperand(1, ConstantInt::get(Ty, Mask2)); + Worklist.Add(II); + return &Cmp; + } break; + } case Intrinsic::ctpop: { // popcount(A) == 0 -> A == 0 and likewise for != // popcount(A) == bitwidth(A) -> A == -1 and likewise for != bool IsZero = C.isNullValue(); - if (IsZero || C == C.getBitWidth()) { + if (IsZero || C == BitWidth) { Worklist.Add(II); Cmp.setOperand(0, II->getArgOperand(0)); auto *NewOp = @@ -2870,15 +2925,25 @@ Instruction *InstCombiner::foldICmpInstWithConstantNotInt(ICmpInst &I) { /// In this case, we are looking for comparisons that look like /// a check for a lossy truncation. /// Folds: -/// x & (-1 >> y) SrcPred x to x DstPred (-1 >> y) +/// icmp SrcPred (x & Mask), x to icmp DstPred x, Mask +/// Where Mask is some pattern that produces all-ones in low bits: +/// (-1 >> y) +/// ((-1 << y) >> y) <- non-canonical, has extra uses +/// ~(-1 << y) +/// ((1 << y) + (-1)) <- non-canonical, has extra uses /// The Mask can be a constant, too. /// For some predicates, the operands are commutative. /// For others, x can only be on a specific side. static Value *foldICmpWithLowBitMaskedVal(ICmpInst &I, InstCombiner::BuilderTy &Builder) { ICmpInst::Predicate SrcPred; - Value *X, *M; - auto m_Mask = m_CombineOr(m_LShr(m_AllOnes(), m_Value()), m_LowBitMask()); + Value *X, *M, *Y; + auto m_VariableMask = m_CombineOr( + m_CombineOr(m_Not(m_Shl(m_AllOnes(), m_Value())), + m_Add(m_Shl(m_One(), m_Value()), m_AllOnes())), + m_CombineOr(m_LShr(m_AllOnes(), m_Value()), + m_LShr(m_Shl(m_AllOnes(), m_Value(Y)), m_Deferred(Y)))); + auto m_Mask = m_CombineOr(m_VariableMask, m_LowBitMask()); if (!match(&I, m_c_ICmp(SrcPred, m_c_And(m_CombineAnd(m_Mask, m_Value(M)), m_Value(X)), m_Deferred(X)))) @@ -2924,12 +2989,20 @@ static Value *foldICmpWithLowBitMaskedVal(ICmpInst &I, // x & (-1 >> y) s>= x -> x s<= (-1 >> y) if (X != I.getOperand(1)) // X must be on RHS 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; case ICmpInst::Predicate::ICMP_SLT: // x & (-1 >> y) s< x -> x s> (-1 >> y) if (X != I.getOperand(1)) // X must be on RHS 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_SLE: @@ -3034,6 +3107,18 @@ Instruction *InstCombiner::foldICmpBinOp(ICmpInst &I) { return nullptr; const CmpInst::Predicate Pred = I.getPredicate(); + Value *X; + + // Convert add-with-unsigned-overflow comparisons into a 'not' with compare. + // (Op1 + X) <u Op1 --> ~Op1 <u X + // Op0 >u (Op0 + X) --> X >u ~Op0 + if (match(Op0, m_OneUse(m_c_Add(m_Specific(Op1), m_Value(X)))) && + Pred == ICmpInst::ICMP_ULT) + return new ICmpInst(Pred, Builder.CreateNot(Op1), X); + if (match(Op1, m_OneUse(m_c_Add(m_Specific(Op0), m_Value(X)))) && + Pred == ICmpInst::ICMP_UGT) + return new ICmpInst(Pred, X, Builder.CreateNot(Op0)); + bool NoOp0WrapProblem = false, NoOp1WrapProblem = false; if (BO0 && isa<OverflowingBinaryOperator>(BO0)) NoOp0WrapProblem = @@ -4598,6 +4683,83 @@ static Instruction *canonicalizeICmpBool(ICmpInst &I, } } +// Transform pattern like: +// (1 << Y) u<= X or ~(-1 << Y) u< X or ((1 << Y)+(-1)) u< X +// (1 << Y) u> X or ~(-1 << Y) u>= X or ((1 << Y)+(-1)) u>= X +// Into: +// (X l>> Y) != 0 +// (X l>> Y) == 0 +static Instruction *foldICmpWithHighBitMask(ICmpInst &Cmp, + InstCombiner::BuilderTy &Builder) { + ICmpInst::Predicate Pred, NewPred; + Value *X, *Y; + if (match(&Cmp, + m_c_ICmp(Pred, m_OneUse(m_Shl(m_One(), m_Value(Y))), m_Value(X)))) { + // We want X to be the icmp's second operand, so swap predicate if it isn't. + if (Cmp.getOperand(0) == X) + Pred = Cmp.getSwappedPredicate(); + + switch (Pred) { + case ICmpInst::ICMP_ULE: + NewPred = ICmpInst::ICMP_NE; + break; + case ICmpInst::ICMP_UGT: + NewPred = ICmpInst::ICMP_EQ; + break; + default: + return nullptr; + } + } else if (match(&Cmp, m_c_ICmp(Pred, + m_OneUse(m_CombineOr( + m_Not(m_Shl(m_AllOnes(), m_Value(Y))), + m_Add(m_Shl(m_One(), m_Value(Y)), + m_AllOnes()))), + m_Value(X)))) { + // The variant with 'add' is not canonical, (the variant with 'not' is) + // we only get it because it has extra uses, and can't be canonicalized, + + // We want X to be the icmp's second operand, so swap predicate if it isn't. + if (Cmp.getOperand(0) == X) + Pred = Cmp.getSwappedPredicate(); + + switch (Pred) { + case ICmpInst::ICMP_ULT: + NewPred = ICmpInst::ICMP_NE; + break; + case ICmpInst::ICMP_UGE: + NewPred = ICmpInst::ICMP_EQ; + break; + default: + return nullptr; + } + } else + return nullptr; + + Value *NewX = Builder.CreateLShr(X, Y, X->getName() + ".highbits"); + Constant *Zero = Constant::getNullValue(NewX->getType()); + return CmpInst::Create(Instruction::ICmp, NewPred, NewX, Zero); +} + +static Instruction *foldVectorCmp(CmpInst &Cmp, + InstCombiner::BuilderTy &Builder) { + // If both arguments of the cmp are shuffles that use the same mask and + // shuffle within a single vector, move the shuffle after the cmp. + Value *LHS = Cmp.getOperand(0), *RHS = Cmp.getOperand(1); + Value *V1, *V2; + Constant *M; + if (match(LHS, m_ShuffleVector(m_Value(V1), m_Undef(), m_Constant(M))) && + match(RHS, m_ShuffleVector(m_Value(V2), m_Undef(), m_Specific(M))) && + V1->getType() == V2->getType() && + (LHS->hasOneUse() || RHS->hasOneUse())) { + // cmp (shuffle V1, M), (shuffle V2, M) --> shuffle (cmp V1, V2), M + CmpInst::Predicate P = Cmp.getPredicate(); + Value *NewCmp = isa<ICmpInst>(Cmp) ? Builder.CreateICmp(P, V1, V2) + : Builder.CreateFCmp(P, V1, V2); + return new ShuffleVectorInst(NewCmp, UndefValue::get(NewCmp->getType()), M); + } + return nullptr; +} + Instruction *InstCombiner::visitICmpInst(ICmpInst &I) { bool Changed = false; Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); @@ -4645,6 +4807,9 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) { if (Instruction *Res = foldICmpWithConstant(I)) return Res; + if (Instruction *Res = foldICmpWithDominatingICmp(I)) + return Res; + if (Instruction *Res = foldICmpUsingKnownBits(I)) return Res; @@ -4857,16 +5022,24 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) { return ExtractValueInst::Create(ACXI, 1); { - Value *X; ConstantInt *Cst; + Value *X; + const APInt *C; // icmp X+Cst, X - if (match(Op0, m_Add(m_Value(X), m_ConstantInt(Cst))) && Op1 == X) - return foldICmpAddOpConst(X, Cst, I.getPredicate()); + if (match(Op0, m_Add(m_Value(X), m_APInt(C))) && Op1 == X) + return foldICmpAddOpConst(X, *C, I.getPredicate()); // icmp X, X+Cst - if (match(Op1, m_Add(m_Value(X), m_ConstantInt(Cst))) && Op0 == X) - return foldICmpAddOpConst(X, Cst, I.getSwappedPredicate()); + if (match(Op1, m_Add(m_Value(X), m_APInt(C))) && Op0 == X) + return foldICmpAddOpConst(X, *C, I.getSwappedPredicate()); } + if (Instruction *Res = foldICmpWithHighBitMask(I, Builder)) + return Res; + + if (I.getType()->isVectorTy()) + if (Instruction *Res = foldVectorCmp(I, Builder)) + return Res; + return Changed ? &I : nullptr; } @@ -5109,6 +5282,117 @@ Instruction *InstCombiner::foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI, return new ICmpInst(Pred, LHSI->getOperand(0), RHSInt); } +/// Fold (C / X) < 0.0 --> X < 0.0 if possible. Swap predicate if necessary. +static Instruction *foldFCmpReciprocalAndZero(FCmpInst &I, Instruction *LHSI, + Constant *RHSC) { + // When C is not 0.0 and infinities are not allowed: + // (C / X) < 0.0 is a sign-bit test of X + // (C / X) < 0.0 --> X < 0.0 (if C is positive) + // (C / X) < 0.0 --> X > 0.0 (if C is negative, swap the predicate) + // + // Proof: + // Multiply (C / X) < 0.0 by X * X / C. + // - X is non zero, if it is the flag 'ninf' is violated. + // - C defines the sign of X * X * C. Thus it also defines whether to swap + // the predicate. C is also non zero by definition. + // + // Thus X * X / C is non zero and the transformation is valid. [qed] + + FCmpInst::Predicate Pred = I.getPredicate(); + + // Check that predicates are valid. + if ((Pred != FCmpInst::FCMP_OGT) && (Pred != FCmpInst::FCMP_OLT) && + (Pred != FCmpInst::FCMP_OGE) && (Pred != FCmpInst::FCMP_OLE)) + return nullptr; + + // Check that RHS operand is zero. + if (!match(RHSC, m_AnyZeroFP())) + return nullptr; + + // Check fastmath flags ('ninf'). + if (!LHSI->hasNoInfs() || !I.hasNoInfs()) + return nullptr; + + // Check the properties of the dividend. It must not be zero to avoid a + // division by zero (see Proof). + const APFloat *C; + if (!match(LHSI->getOperand(0), m_APFloat(C))) + return nullptr; + + if (C->isZero()) + return nullptr; + + // Get swapped predicate if necessary. + if (C->isNegative()) + Pred = I.getSwappedPredicate(); + + return new FCmpInst(Pred, LHSI->getOperand(1), RHSC, "", &I); +} + +/// Optimize fabs(X) compared with zero. +static Instruction *foldFabsWithFcmpZero(FCmpInst &I) { + Value *X; + if (!match(I.getOperand(0), m_Intrinsic<Intrinsic::fabs>(m_Value(X))) || + !match(I.getOperand(1), m_PosZeroFP())) + return nullptr; + + auto replacePredAndOp0 = [](FCmpInst *I, FCmpInst::Predicate P, Value *X) { + I->setPredicate(P); + I->setOperand(0, X); + return I; + }; + + switch (I.getPredicate()) { + case FCmpInst::FCMP_UGE: + case FCmpInst::FCMP_OLT: + // fabs(X) >= 0.0 --> true + // fabs(X) < 0.0 --> false + llvm_unreachable("fcmp should have simplified"); + + case FCmpInst::FCMP_OGT: + // fabs(X) > 0.0 --> X != 0.0 + return replacePredAndOp0(&I, FCmpInst::FCMP_ONE, X); + + case FCmpInst::FCMP_UGT: + // fabs(X) u> 0.0 --> X u!= 0.0 + return replacePredAndOp0(&I, FCmpInst::FCMP_UNE, X); + + case FCmpInst::FCMP_OLE: + // fabs(X) <= 0.0 --> X == 0.0 + return replacePredAndOp0(&I, FCmpInst::FCMP_OEQ, X); + + case FCmpInst::FCMP_ULE: + // fabs(X) u<= 0.0 --> X u== 0.0 + return replacePredAndOp0(&I, FCmpInst::FCMP_UEQ, X); + + case FCmpInst::FCMP_OGE: + // fabs(X) >= 0.0 --> !isnan(X) + assert(!I.hasNoNaNs() && "fcmp should have simplified"); + return replacePredAndOp0(&I, FCmpInst::FCMP_ORD, X); + + case FCmpInst::FCMP_ULT: + // fabs(X) u< 0.0 --> isnan(X) + assert(!I.hasNoNaNs() && "fcmp should have simplified"); + return replacePredAndOp0(&I, FCmpInst::FCMP_UNO, X); + + case FCmpInst::FCMP_OEQ: + case FCmpInst::FCMP_UEQ: + case FCmpInst::FCMP_ONE: + case FCmpInst::FCMP_UNE: + case FCmpInst::FCMP_ORD: + case FCmpInst::FCMP_UNO: + // Look through the fabs() because it doesn't change anything but the sign. + // fabs(X) == 0.0 --> X == 0.0, + // fabs(X) != 0.0 --> X != 0.0 + // isnan(fabs(X)) --> isnan(X) + // !isnan(fabs(X) --> !isnan(X) + return replacePredAndOp0(&I, I.getPredicate(), X); + + default: + return nullptr; + } +} + Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) { bool Changed = false; @@ -5153,11 +5437,11 @@ Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) { // If we're just checking for a NaN (ORD/UNO) and have a non-NaN operand, // then canonicalize the operand to 0.0. if (Pred == CmpInst::FCMP_ORD || Pred == CmpInst::FCMP_UNO) { - if (!match(Op0, m_PosZeroFP()) && isKnownNeverNaN(Op0)) { + if (!match(Op0, m_PosZeroFP()) && isKnownNeverNaN(Op0, &TLI)) { I.setOperand(0, ConstantFP::getNullValue(Op0->getType())); return &I; } - if (!match(Op1, m_PosZeroFP()) && isKnownNeverNaN(Op1)) { + if (!match(Op1, m_PosZeroFP()) && isKnownNeverNaN(Op1, &TLI)) { I.setOperand(1, ConstantFP::getNullValue(Op0->getType())); return &I; } @@ -5178,128 +5462,93 @@ Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) { return nullptr; } - // Handle fcmp with constant RHS - if (Constant *RHSC = dyn_cast<Constant>(Op1)) { - if (Instruction *LHSI = dyn_cast<Instruction>(Op0)) - switch (LHSI->getOpcode()) { - case Instruction::FPExt: { - // fcmp (fpext x), C -> fcmp x, (fptrunc C) if fptrunc is lossless - FPExtInst *LHSExt = cast<FPExtInst>(LHSI); - ConstantFP *RHSF = dyn_cast<ConstantFP>(RHSC); - if (!RHSF) - break; + // 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())); + return &I; + } - const fltSemantics *Sem; - // FIXME: This shouldn't be here. - if (LHSExt->getSrcTy()->isHalfTy()) - Sem = &APFloat::IEEEhalf(); - else if (LHSExt->getSrcTy()->isFloatTy()) - Sem = &APFloat::IEEEsingle(); - else if (LHSExt->getSrcTy()->isDoubleTy()) - Sem = &APFloat::IEEEdouble(); - else if (LHSExt->getSrcTy()->isFP128Ty()) - Sem = &APFloat::IEEEquad(); - else if (LHSExt->getSrcTy()->isX86_FP80Ty()) - Sem = &APFloat::x87DoubleExtended(); - else if (LHSExt->getSrcTy()->isPPC_FP128Ty()) - Sem = &APFloat::PPCDoubleDouble(); - else - break; + // Handle fcmp with instruction LHS and constant RHS. + Instruction *LHSI; + Constant *RHSC; + if (match(Op0, m_Instruction(LHSI)) && match(Op1, m_Constant(RHSC))) { + switch (LHSI->getOpcode()) { + case Instruction::PHI: + // Only fold fcmp into the PHI if the phi and fcmp are in the same + // block. If in the same block, we're encouraging jump threading. If + // not, we are just pessimizing the code by making an i1 phi. + if (LHSI->getParent() == I.getParent()) + if (Instruction *NV = foldOpIntoPhi(I, cast<PHINode>(LHSI))) + return NV; + break; + case Instruction::SIToFP: + case Instruction::UIToFP: + if (Instruction *NV = foldFCmpIntToFPConst(I, LHSI, RHSC)) + return NV; + break; + case Instruction::FDiv: + if (Instruction *NV = foldFCmpReciprocalAndZero(I, LHSI, RHSC)) + return NV; + break; + case Instruction::Load: + if (auto *GEP = dyn_cast<GetElementPtrInst>(LHSI->getOperand(0))) + if (auto *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0))) + if (GV->isConstant() && GV->hasDefinitiveInitializer() && + !cast<LoadInst>(LHSI)->isVolatile()) + if (Instruction *Res = foldCmpLoadFromIndexedGlobal(GEP, GV, I)) + return Res; + break; + } + } - bool Lossy; - APFloat F = RHSF->getValueAPF(); - F.convert(*Sem, APFloat::rmNearestTiesToEven, &Lossy); + if (Instruction *R = foldFabsWithFcmpZero(I)) + return R; - // Avoid lossy conversions and denormals. Zero is a special case - // that's OK to convert. - APFloat Fabs = F; - Fabs.clearSign(); - if (!Lossy && - ((Fabs.compare(APFloat::getSmallestNormalized(*Sem)) != - APFloat::cmpLessThan) || Fabs.isZero())) + 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); - return new FCmpInst(Pred, LHSExt->getOperand(0), - ConstantFP::get(RHSC->getContext(), F)); - break; - } - case Instruction::PHI: - // Only fold fcmp into the PHI if the phi and fcmp are in the same - // block. If in the same block, we're encouraging jump threading. If - // not, we are just pessimizing the code by making an i1 phi. - if (LHSI->getParent() == I.getParent()) - if (Instruction *NV = foldOpIntoPhi(I, cast<PHINode>(LHSI))) - return NV; - break; - case Instruction::SIToFP: - case Instruction::UIToFP: - if (Instruction *NV = foldFCmpIntToFPConst(I, LHSI, RHSC)) - return NV; - break; - case Instruction::FSub: { - // fcmp pred (fneg x), C -> fcmp swap(pred) x, -C - Value *Op; - if (match(LHSI, m_FNeg(m_Value(Op)))) - return new FCmpInst(I.getSwappedPredicate(), Op, - ConstantExpr::getFNeg(RHSC)); - break; - } - case Instruction::Load: - if (GetElementPtrInst *GEP = - dyn_cast<GetElementPtrInst>(LHSI->getOperand(0))) { - if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0))) - if (GV->isConstant() && GV->hasDefinitiveInitializer() && - !cast<LoadInst>(LHSI)->isVolatile()) - if (Instruction *Res = foldCmpLoadFromIndexedGlobal(GEP, GV, I)) - return Res; - } - break; - case Instruction::Call: { - if (!RHSC->isNullValue()) - break; + // fcmp pred (fneg X), C --> fcmp swap(pred) X, -C + Constant *C; + if (match(Op1, m_Constant(C))) { + Constant *NegC = ConstantExpr::getFNeg(C); + return new FCmpInst(I.getSwappedPredicate(), X, NegC, "", &I); + } + } - CallInst *CI = cast<CallInst>(LHSI); - Intrinsic::ID IID = getIntrinsicForCallSite(CI, &TLI); - if (IID != Intrinsic::fabs) - break; + if (match(Op0, m_FPExt(m_Value(X)))) { + // fcmp (fpext X), (fpext Y) -> fcmp X, Y + if (match(Op1, m_FPExt(m_Value(Y))) && X->getType() == Y->getType()) + return new FCmpInst(Pred, X, Y, "", &I); - // Various optimization for fabs compared with zero. - switch (Pred) { - default: - break; - // fabs(x) < 0 --> false - case FCmpInst::FCMP_OLT: - llvm_unreachable("handled by SimplifyFCmpInst"); - // fabs(x) > 0 --> x != 0 - case FCmpInst::FCMP_OGT: - return new FCmpInst(FCmpInst::FCMP_ONE, CI->getArgOperand(0), RHSC); - // fabs(x) <= 0 --> x == 0 - case FCmpInst::FCMP_OLE: - return new FCmpInst(FCmpInst::FCMP_OEQ, CI->getArgOperand(0), RHSC); - // fabs(x) >= 0 --> !isnan(x) - case FCmpInst::FCMP_OGE: - return new FCmpInst(FCmpInst::FCMP_ORD, CI->getArgOperand(0), RHSC); - // fabs(x) == 0 --> x == 0 - // fabs(x) != 0 --> x != 0 - case FCmpInst::FCMP_OEQ: - case FCmpInst::FCMP_UEQ: - case FCmpInst::FCMP_ONE: - case FCmpInst::FCMP_UNE: - return new FCmpInst(Pred, CI->getArgOperand(0), RHSC); - } - } + // fcmp (fpext X), C -> fcmp X, (fptrunc C) if fptrunc is lossless + const APFloat *C; + if (match(Op1, m_APFloat(C))) { + const fltSemantics &FPSem = + X->getType()->getScalarType()->getFltSemantics(); + bool Lossy; + APFloat TruncC = *C; + TruncC.convert(FPSem, APFloat::rmNearestTiesToEven, &Lossy); + + // Avoid lossy conversions and denormals. + // Zero is a special case that's OK to convert. + APFloat Fabs = TruncC; + Fabs.clearSign(); + if (!Lossy && + ((Fabs.compare(APFloat::getSmallestNormalized(FPSem)) != + APFloat::cmpLessThan) || Fabs.isZero())) { + Constant *NewC = ConstantFP::get(X->getType(), TruncC); + return new FCmpInst(Pred, X, NewC, "", &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); - - // fcmp (fpext x), (fpext y) -> fcmp x, y - if (FPExtInst *LHSExt = dyn_cast<FPExtInst>(Op0)) - if (FPExtInst *RHSExt = dyn_cast<FPExtInst>(Op1)) - if (LHSExt->getSrcTy() == RHSExt->getSrcTy()) - return new FCmpInst(Pred, LHSExt->getOperand(0), RHSExt->getOperand(0)); + if (I.getType()->isVectorTy()) + if (Instruction *Res = foldVectorCmp(I, Builder)) + return Res; return Changed ? &I : nullptr; } diff --git a/lib/Transforms/InstCombine/InstCombineInternal.h b/lib/Transforms/InstCombine/InstCombineInternal.h index 58ef3d41415c..2de41bd5bef5 100644 --- a/lib/Transforms/InstCombine/InstCombineInternal.h +++ b/lib/Transforms/InstCombine/InstCombineInternal.h @@ -20,7 +20,6 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/TargetFolder.h" -#include "llvm/Transforms/Utils/Local.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Argument.h" #include "llvm/IR/BasicBlock.h" @@ -33,6 +32,7 @@ #include "llvm/IR/Instruction.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Intrinsics.h" +#include "llvm/IR/PatternMatch.h" #include "llvm/IR/Use.h" #include "llvm/IR/Value.h" #include "llvm/Support/Casting.h" @@ -41,11 +41,14 @@ #include "llvm/Support/KnownBits.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/InstCombine/InstCombineWorklist.h" +#include "llvm/Transforms/Utils/Local.h" #include <cassert> #include <cstdint> #define DEBUG_TYPE "instcombine" +using namespace llvm::PatternMatch; + namespace llvm { class APInt; @@ -79,8 +82,8 @@ class User; /// 5 -> Other instructions static inline unsigned getComplexity(Value *V) { if (isa<Instruction>(V)) { - if (isa<CastInst>(V) || BinaryOperator::isNeg(V) || - BinaryOperator::isFNeg(V) || BinaryOperator::isNot(V)) + if (isa<CastInst>(V) || match(V, m_Neg(m_Value())) || + match(V, m_Not(m_Value())) || match(V, m_FNeg(m_Value()))) return 4; return 5; } @@ -138,7 +141,7 @@ static inline Constant *SubOne(Constant *C) { /// uses of V and only keep uses of ~V. static inline bool IsFreeToInvert(Value *V, bool WillInvertAllUses) { // ~(~(X)) -> X. - if (BinaryOperator::isNot(V)) + if (match(V, m_Not(m_Value()))) return true; // Constants can be considered to be not'ed values. @@ -175,6 +178,10 @@ static inline bool IsFreeToInvert(Value *V, bool WillInvertAllUses) { if (isa<Constant>(BO->getOperand(0)) || isa<Constant>(BO->getOperand(1))) return WillInvertAllUses; + // Selects with invertible operands are freely invertible + if (match(V, m_Select(m_Value(), m_Not(m_Value()), m_Not(m_Value())))) + return WillInvertAllUses; + return false; } @@ -496,6 +503,12 @@ private: OverflowResult::NeverOverflows; } + bool willNotOverflowAdd(const Value *LHS, const Value *RHS, + const Instruction &CxtI, bool IsSigned) const { + return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI) + : willNotOverflowUnsignedAdd(LHS, RHS, CxtI); + } + bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS, const Instruction &CxtI) const { return computeOverflowForSignedSub(LHS, RHS, &CxtI) == @@ -508,6 +521,12 @@ private: OverflowResult::NeverOverflows; } + bool willNotOverflowSub(const Value *LHS, const Value *RHS, + const Instruction &CxtI, bool IsSigned) const { + return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI) + : willNotOverflowUnsignedSub(LHS, RHS, CxtI); + } + bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS, const Instruction &CxtI) const { return computeOverflowForSignedMul(LHS, RHS, &CxtI) == @@ -520,12 +539,29 @@ private: OverflowResult::NeverOverflows; } + bool willNotOverflowMul(const Value *LHS, const Value *RHS, + const Instruction &CxtI, bool IsSigned) const { + return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI) + : willNotOverflowUnsignedMul(LHS, RHS, CxtI); + } + + bool willNotOverflow(BinaryOperator::BinaryOps Opcode, const Value *LHS, + const Value *RHS, const Instruction &CxtI, + bool IsSigned) const { + switch (Opcode) { + case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned); + case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned); + case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned); + default: llvm_unreachable("Unexpected opcode for overflow query"); + } + } + Value *EmitGEPOffset(User *GEP); Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN); - Value *EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask); Instruction *foldCastedBitwiseLogic(BinaryOperator &I); Instruction *narrowBinOp(TruncInst &Trunc); Instruction *narrowMaskedBinOp(BinaryOperator &And); + Instruction *narrowMathIfNoOverflow(BinaryOperator &I); Instruction *narrowRotate(TruncInst &Trunc); Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN); @@ -553,6 +589,9 @@ private: Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS, bool JoinedByAnd, Instruction &CxtI); + Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D); + Value *getSelectCondition(Value *A, Value *B); + public: /// Inserts an instruction \p New before instruction \p Old /// @@ -763,13 +802,14 @@ private: Value *simplifyAMDGCNMemoryIntrinsicDemanded(IntrinsicInst *II, APInt DemandedElts, - int DmaskIdx = -1); + int DmaskIdx = -1, + int TFCIdx = -1); Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts, unsigned Depth = 0); /// Canonicalize the position of binops relative to shufflevector. - Instruction *foldShuffledBinop(BinaryOperator &Inst); + Instruction *foldVectorBinop(BinaryOperator &Inst); /// Given a binary operator, cast instruction, or select which has a PHI node /// as operand #0, see if we can fold the instruction into the PHI (which is @@ -813,11 +853,12 @@ private: ConstantInt *AndCst = nullptr); Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI, Constant *RHSC); - Instruction *foldICmpAddOpConst(Value *X, ConstantInt *CI, + Instruction *foldICmpAddOpConst(Value *X, const APInt &C, ICmpInst::Predicate Pred); Instruction *foldICmpWithCastAndCast(ICmpInst &ICI); Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp); + Instruction *foldICmpWithDominatingICmp(ICmpInst &Cmp); Instruction *foldICmpWithConstant(ICmpInst &Cmp); Instruction *foldICmpInstWithConstant(ICmpInst &Cmp); Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp); @@ -880,8 +921,11 @@ private: Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi, bool isSigned, bool Inside); Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI); - Instruction *MatchBSwap(BinaryOperator &I); - bool SimplifyStoreAtEndOfBlock(StoreInst &SI); + bool mergeStoreIntoSuccessor(StoreInst &SI); + + /// Given an 'or' instruction, check to see if it is part of a bswap idiom. + /// If so, return the equivalent bswap intrinsic. + Instruction *matchBSwap(BinaryOperator &Or); Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI); Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI); diff --git a/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp b/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp index 62769f077b47..76ab614090fa 100644 --- a/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp +++ b/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp @@ -19,6 +19,7 @@ #include "llvm/Transforms/Utils/Local.h" #include "llvm/IR/ConstantRange.h" #include "llvm/IR/DataLayout.h" +#include "llvm/IR/DebugInfoMetadata.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/MDBuilder.h" @@ -115,13 +116,10 @@ isOnlyCopiedFromConstantGlobal(Value *V, MemTransferInst *&TheCopy, } // Lifetime intrinsics can be handled by the caller. - if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { - if (II->getIntrinsicID() == Intrinsic::lifetime_start || - II->getIntrinsicID() == Intrinsic::lifetime_end) { - assert(II->use_empty() && "Lifetime markers have no result to use!"); - ToDelete.push_back(II); - continue; - } + if (I->isLifetimeStartOrEnd()) { + assert(I->use_empty() && "Lifetime markers have no result to use!"); + ToDelete.push_back(I); + continue; } // If this is isn't our memcpy/memmove, reject it as something we can't @@ -197,30 +195,32 @@ static Instruction *simplifyAllocaArraySize(InstCombiner &IC, AllocaInst &AI) { // Convert: alloca Ty, C - where C is a constant != 1 into: alloca [C x Ty], 1 if (const ConstantInt *C = dyn_cast<ConstantInt>(AI.getArraySize())) { - Type *NewTy = ArrayType::get(AI.getAllocatedType(), C->getZExtValue()); - AllocaInst *New = IC.Builder.CreateAlloca(NewTy, nullptr, AI.getName()); - New->setAlignment(AI.getAlignment()); + if (C->getValue().getActiveBits() <= 64) { + Type *NewTy = ArrayType::get(AI.getAllocatedType(), C->getZExtValue()); + AllocaInst *New = IC.Builder.CreateAlloca(NewTy, nullptr, AI.getName()); + New->setAlignment(AI.getAlignment()); - // Scan to the end of the allocation instructions, to skip over a block of - // allocas if possible...also skip interleaved debug info - // - BasicBlock::iterator It(New); - while (isa<AllocaInst>(*It) || isa<DbgInfoIntrinsic>(*It)) - ++It; + // Scan to the end of the allocation instructions, to skip over a block of + // allocas if possible...also skip interleaved debug info + // + BasicBlock::iterator It(New); + while (isa<AllocaInst>(*It) || isa<DbgInfoIntrinsic>(*It)) + ++It; - // Now that I is pointing to the first non-allocation-inst in the block, - // insert our getelementptr instruction... - // - 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"); - IC.InsertNewInstBefore(GEP, *It); + // Now that I is pointing to the first non-allocation-inst in the block, + // insert our getelementptr instruction... + // + 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"); + IC.InsertNewInstBefore(GEP, *It); - // Now make everything use the getelementptr instead of the original - // allocation. - return IC.replaceInstUsesWith(AI, GEP); + // Now make everything use the getelementptr instead of the original + // allocation. + return IC.replaceInstUsesWith(AI, GEP); + } } if (isa<UndefValue>(AI.getArraySize())) @@ -490,6 +490,7 @@ static LoadInst *combineLoadToNewType(InstCombiner &IC, LoadInst &LI, Type *NewT case LLVMContext::MD_noalias: case LLVMContext::MD_nontemporal: case LLVMContext::MD_mem_parallel_loop_access: + case LLVMContext::MD_access_group: // All of these directly apply. NewLoad->setMetadata(ID, N); break; @@ -549,10 +550,10 @@ static StoreInst *combineStoreToNewValue(InstCombiner &IC, StoreInst &SI, Value case LLVMContext::MD_noalias: case LLVMContext::MD_nontemporal: case LLVMContext::MD_mem_parallel_loop_access: + case LLVMContext::MD_access_group: // All of these directly apply. NewStore->setMetadata(ID, N); break; - case LLVMContext::MD_invariant_load: case LLVMContext::MD_nonnull: case LLVMContext::MD_range: @@ -1024,7 +1025,7 @@ Instruction *InstCombiner::visitLoadInst(LoadInst &LI) { if (Value *AvailableVal = FindAvailableLoadedValue( &LI, LI.getParent(), BBI, DefMaxInstsToScan, AA, &IsLoadCSE)) { if (IsLoadCSE) - combineMetadataForCSE(cast<LoadInst>(AvailableVal), &LI); + combineMetadataForCSE(cast<LoadInst>(AvailableVal), &LI, false); return replaceInstUsesWith( LI, Builder.CreateBitOrPointerCast(AvailableVal, LI.getType(), @@ -1496,64 +1497,45 @@ Instruction *InstCombiner::visitStoreInst(StoreInst &SI) { if (isa<UndefValue>(Val)) return eraseInstFromFunction(SI); - // If this store is the last instruction in the basic block (possibly - // excepting debug info instructions), and if the block ends with an - // unconditional branch, try to move it to the successor block. + // If this store is the second-to-last instruction in the basic block + // (excluding debug info and bitcasts of pointers) and if the block ends with + // an unconditional branch, try to move the store to the successor block. BBI = SI.getIterator(); do { ++BBI; } while (isa<DbgInfoIntrinsic>(BBI) || (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy())); + if (BranchInst *BI = dyn_cast<BranchInst>(BBI)) if (BI->isUnconditional()) - if (SimplifyStoreAtEndOfBlock(SI)) - return nullptr; // xform done! + mergeStoreIntoSuccessor(SI); return nullptr; } -/// SimplifyStoreAtEndOfBlock - Turn things like: +/// Try to transform: /// if () { *P = v1; } else { *P = v2 } -/// into a phi node with a store in the successor. -/// -/// Simplify things like: +/// or: /// *P = v1; if () { *P = v2; } /// into a phi node with a store in the successor. -/// -bool InstCombiner::SimplifyStoreAtEndOfBlock(StoreInst &SI) { +bool InstCombiner::mergeStoreIntoSuccessor(StoreInst &SI) { assert(SI.isUnordered() && - "this code has not been auditted for volatile or ordered store case"); + "This code has not been audited for volatile or ordered store case."); + // Check if the successor block has exactly 2 incoming edges. BasicBlock *StoreBB = SI.getParent(); - - // Check to see if the successor block has exactly two incoming edges. If - // so, see if the other predecessor contains a store to the same location. - // if so, insert a PHI node (if needed) and move the stores down. BasicBlock *DestBB = StoreBB->getTerminator()->getSuccessor(0); - - // Determine whether Dest has exactly two predecessors and, if so, compute - // the other predecessor. - pred_iterator PI = pred_begin(DestBB); - BasicBlock *P = *PI; - BasicBlock *OtherBB = nullptr; - - if (P != StoreBB) - OtherBB = P; - - if (++PI == pred_end(DestBB)) + if (!DestBB->hasNPredecessors(2)) return false; - P = *PI; - if (P != StoreBB) { - if (OtherBB) - return false; - OtherBB = P; - } - if (++PI != pred_end(DestBB)) - return false; + // Capture the other block (the block that doesn't contain our store). + pred_iterator PredIter = pred_begin(DestBB); + if (*PredIter == StoreBB) + ++PredIter; + BasicBlock *OtherBB = *PredIter; - // Bail out if all the relevant blocks aren't distinct (this can happen, - // for example, if SI is in an infinite loop) + // Bail out if all of the relevant blocks aren't distinct. This can happen, + // for example, if SI is in an infinite loop. if (StoreBB == DestBB || OtherBB == DestBB) return false; @@ -1564,7 +1546,7 @@ bool InstCombiner::SimplifyStoreAtEndOfBlock(StoreInst &SI) { return false; // If the other block ends in an unconditional branch, check for the 'if then - // else' case. there is an instruction before the branch. + // else' case. There is an instruction before the branch. StoreInst *OtherStore = nullptr; if (OtherBr->isUnconditional()) { --BBI; @@ -1589,7 +1571,7 @@ bool InstCombiner::SimplifyStoreAtEndOfBlock(StoreInst &SI) { return false; // Okay, we know that OtherBr now goes to Dest and StoreBB, so this is an - // if/then triangle. See if there is a store to the same ptr as SI that + // if/then triangle. See if there is a store to the same ptr as SI that // lives in OtherBB. for (;; --BBI) { // Check to see if we find the matching store. @@ -1600,15 +1582,14 @@ bool InstCombiner::SimplifyStoreAtEndOfBlock(StoreInst &SI) { break; } // If we find something that may be using or overwriting the stored - // value, or if we run out of instructions, we can't do the xform. + // value, or if we run out of instructions, we can't do the transform. if (BBI->mayReadFromMemory() || BBI->mayThrow() || BBI->mayWriteToMemory() || BBI == OtherBB->begin()) return false; } - // In order to eliminate the store in OtherBr, we have to - // make sure nothing reads or overwrites the stored value in - // StoreBB. + // In order to eliminate the store in OtherBr, we have to make sure nothing + // reads or overwrites the stored value in StoreBB. for (BasicBlock::iterator I = StoreBB->begin(); &*I != &SI; ++I) { // FIXME: This should really be AA driven. if (I->mayReadFromMemory() || I->mayThrow() || I->mayWriteToMemory()) @@ -1618,24 +1599,24 @@ bool InstCombiner::SimplifyStoreAtEndOfBlock(StoreInst &SI) { // Insert a PHI node now if we need it. Value *MergedVal = OtherStore->getOperand(0); + // The debug locations of the original instructions might differ. Merge them. + DebugLoc MergedLoc = DILocation::getMergedLocation(SI.getDebugLoc(), + OtherStore->getDebugLoc()); if (MergedVal != SI.getOperand(0)) { PHINode *PN = PHINode::Create(MergedVal->getType(), 2, "storemerge"); PN->addIncoming(SI.getOperand(0), SI.getParent()); PN->addIncoming(OtherStore->getOperand(0), OtherBB); MergedVal = InsertNewInstBefore(PN, DestBB->front()); + PN->setDebugLoc(MergedLoc); } - // Advance to a place where it is safe to insert the new store and - // insert it. + // Advance to a place where it is safe to insert the new store and insert it. BBI = DestBB->getFirstInsertionPt(); StoreInst *NewSI = new StoreInst(MergedVal, SI.getOperand(1), - SI.isVolatile(), - SI.getAlignment(), - SI.getOrdering(), - SI.getSyncScopeID()); + SI.isVolatile(), SI.getAlignment(), + SI.getOrdering(), SI.getSyncScopeID()); InsertNewInstBefore(NewSI, *BBI); - // The debug locations of the original instructions might differ; merge them. - NewSI->applyMergedLocation(SI.getDebugLoc(), OtherStore->getDebugLoc()); + NewSI->setDebugLoc(MergedLoc); // If the two stores had AA tags, merge them. AAMDNodes AATags; diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index 63761d427235..7e99f3e4e500 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -133,7 +133,7 @@ Instruction *InstCombiner::visitMul(BinaryOperator &I) { if (SimplifyAssociativeOrCommutative(I)) return &I; - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; if (Value *V = SimplifyUsingDistributiveLaws(I)) @@ -171,14 +171,13 @@ Instruction *InstCombiner::visitMul(BinaryOperator &I) { if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) { // Replace X*(2^C) with X << C, where C is either a scalar or a vector. if (Constant *NewCst = getLogBase2(NewOp->getType(), C1)) { - unsigned Width = NewCst->getType()->getPrimitiveSizeInBits(); BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst); if (I.hasNoUnsignedWrap()) Shl->setHasNoUnsignedWrap(); if (I.hasNoSignedWrap()) { const APInt *V; - if (match(NewCst, m_APInt(V)) && *V != Width - 1) + if (match(NewCst, m_APInt(V)) && *V != V->getBitWidth() - 1) Shl->setHasNoSignedWrap(); } @@ -245,6 +244,11 @@ Instruction *InstCombiner::visitMul(BinaryOperator &I) { return NewMul; } + // -X * Y --> -(X * Y) + // X * -Y --> -(X * Y) + if (match(&I, m_c_Mul(m_OneUse(m_Neg(m_Value(X))), m_Value(Y)))) + return BinaryOperator::CreateNeg(Builder.CreateMul(X, Y)); + // (X / Y) * Y = X - (X % Y) // (X / Y) * -Y = (X % Y) - X { @@ -323,77 +327,8 @@ Instruction *InstCombiner::visitMul(BinaryOperator &I) { if (match(Op1, m_LShr(m_Value(X), m_APInt(C))) && *C == C->getBitWidth() - 1) return BinaryOperator::CreateAnd(Builder.CreateAShr(X, *C), Op0); - // Check for (mul (sext x), y), see if we can merge this into an - // integer mul followed by a sext. - if (SExtInst *Op0Conv = dyn_cast<SExtInst>(Op0)) { - // (mul (sext x), cst) --> (sext (mul x, cst')) - if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { - if (Op0Conv->hasOneUse()) { - Constant *CI = - ConstantExpr::getTrunc(Op1C, Op0Conv->getOperand(0)->getType()); - if (ConstantExpr::getSExt(CI, I.getType()) == Op1C && - willNotOverflowSignedMul(Op0Conv->getOperand(0), CI, I)) { - // Insert the new, smaller mul. - Value *NewMul = - Builder.CreateNSWMul(Op0Conv->getOperand(0), CI, "mulconv"); - return new SExtInst(NewMul, I.getType()); - } - } - } - - // (mul (sext x), (sext y)) --> (sext (mul int x, y)) - if (SExtInst *Op1Conv = dyn_cast<SExtInst>(Op1)) { - // Only do this if x/y have the same type, if at last one of them has a - // single use (so we don't increase the number of sexts), and if the - // integer mul will not overflow. - if (Op0Conv->getOperand(0)->getType() == - Op1Conv->getOperand(0)->getType() && - (Op0Conv->hasOneUse() || Op1Conv->hasOneUse()) && - willNotOverflowSignedMul(Op0Conv->getOperand(0), - Op1Conv->getOperand(0), I)) { - // Insert the new integer mul. - Value *NewMul = Builder.CreateNSWMul( - Op0Conv->getOperand(0), Op1Conv->getOperand(0), "mulconv"); - return new SExtInst(NewMul, I.getType()); - } - } - } - - // Check for (mul (zext x), y), see if we can merge this into an - // integer mul followed by a zext. - if (auto *Op0Conv = dyn_cast<ZExtInst>(Op0)) { - // (mul (zext x), cst) --> (zext (mul x, cst')) - if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { - if (Op0Conv->hasOneUse()) { - Constant *CI = - ConstantExpr::getTrunc(Op1C, Op0Conv->getOperand(0)->getType()); - if (ConstantExpr::getZExt(CI, I.getType()) == Op1C && - willNotOverflowUnsignedMul(Op0Conv->getOperand(0), CI, I)) { - // Insert the new, smaller mul. - Value *NewMul = - Builder.CreateNUWMul(Op0Conv->getOperand(0), CI, "mulconv"); - return new ZExtInst(NewMul, I.getType()); - } - } - } - - // (mul (zext x), (zext y)) --> (zext (mul int x, y)) - if (auto *Op1Conv = dyn_cast<ZExtInst>(Op1)) { - // Only do this if x/y have the same type, if at last one of them has a - // single use (so we don't increase the number of zexts), and if the - // integer mul will not overflow. - if (Op0Conv->getOperand(0)->getType() == - Op1Conv->getOperand(0)->getType() && - (Op0Conv->hasOneUse() || Op1Conv->hasOneUse()) && - willNotOverflowUnsignedMul(Op0Conv->getOperand(0), - Op1Conv->getOperand(0), I)) { - // Insert the new integer mul. - Value *NewMul = Builder.CreateNUWMul( - Op0Conv->getOperand(0), Op1Conv->getOperand(0), "mulconv"); - return new ZExtInst(NewMul, I.getType()); - } - } - } + if (Instruction *Ext = narrowMathIfNoOverflow(I)) + return Ext; bool Changed = false; if (!I.hasNoSignedWrap() && willNotOverflowSignedMul(Op0, Op1, I)) { @@ -418,7 +353,7 @@ Instruction *InstCombiner::visitFMul(BinaryOperator &I) { if (SimplifyAssociativeOrCommutative(I)) return &I; - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I)) @@ -503,7 +438,7 @@ Instruction *InstCombiner::visitFMul(BinaryOperator &I) { match(Op0, m_OneUse(m_Intrinsic<Intrinsic::sqrt>(m_Value(X)))) && match(Op1, m_OneUse(m_Intrinsic<Intrinsic::sqrt>(m_Value(Y))))) { Value *XY = Builder.CreateFMulFMF(X, Y, &I); - Value *Sqrt = Builder.CreateIntrinsic(Intrinsic::sqrt, { XY }, &I); + Value *Sqrt = Builder.CreateUnaryIntrinsic(Intrinsic::sqrt, XY, &I); return replaceInstUsesWith(I, Sqrt); } @@ -933,7 +868,7 @@ Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { SQ.getWithInstruction(&I))) return replaceInstUsesWith(I, V); - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; // Handle the integer div common cases @@ -1027,7 +962,7 @@ Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { SQ.getWithInstruction(&I))) return replaceInstUsesWith(I, V); - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; // Handle the integer div common cases @@ -1175,7 +1110,7 @@ Instruction *InstCombiner::visitFDiv(BinaryOperator &I) { SQ.getWithInstruction(&I))) return replaceInstUsesWith(I, V); - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; if (Instruction *R = foldFDivConstantDivisor(I)) @@ -1227,7 +1162,8 @@ Instruction *InstCombiner::visitFDiv(BinaryOperator &I) { IRBuilder<>::FastMathFlagGuard FMFGuard(B); B.setFastMathFlags(I.getFastMathFlags()); AttributeList Attrs = CallSite(Op0).getCalledFunction()->getAttributes(); - Value *Res = emitUnaryFloatFnCall(X, TLI.getName(LibFunc_tan), B, Attrs); + Value *Res = emitUnaryFloatFnCall(X, &TLI, LibFunc_tan, LibFunc_tanf, + LibFunc_tanl, B, Attrs); if (IsCot) Res = B.CreateFDiv(ConstantFP::get(I.getType(), 1.0), Res); return replaceInstUsesWith(I, Res); @@ -1304,7 +1240,7 @@ Instruction *InstCombiner::visitURem(BinaryOperator &I) { SQ.getWithInstruction(&I))) return replaceInstUsesWith(I, V); - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; if (Instruction *common = commonIRemTransforms(I)) @@ -1351,7 +1287,7 @@ Instruction *InstCombiner::visitSRem(BinaryOperator &I) { SQ.getWithInstruction(&I))) return replaceInstUsesWith(I, V); - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; // Handle the integer rem common cases @@ -1425,7 +1361,7 @@ Instruction *InstCombiner::visitFRem(BinaryOperator &I) { SQ.getWithInstruction(&I))) return replaceInstUsesWith(I, V); - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; return nullptr; diff --git a/lib/Transforms/InstCombine/InstCombinePHI.cpp b/lib/Transforms/InstCombine/InstCombinePHI.cpp index e54a1dd05a24..7603cf4d7958 100644 --- a/lib/Transforms/InstCombine/InstCombinePHI.cpp +++ b/lib/Transforms/InstCombine/InstCombinePHI.cpp @@ -211,20 +211,20 @@ Instruction *InstCombiner::FoldIntegerTypedPHI(PHINode &PN) { } // If it requires a conversion for every PHI operand, do not do it. - if (std::all_of(AvailablePtrVals.begin(), AvailablePtrVals.end(), - [&](Value *V) { - return (V->getType() != IntToPtr->getType()) || - isa<IntToPtrInst>(V); - })) + if (all_of(AvailablePtrVals, [&](Value *V) { + return (V->getType() != IntToPtr->getType()) || isa<IntToPtrInst>(V); + })) return nullptr; // If any of the operand that requires casting is a terminator // instruction, do not do it. - if (std::any_of(AvailablePtrVals.begin(), AvailablePtrVals.end(), - [&](Value *V) { - return (V->getType() != IntToPtr->getType()) && - isa<TerminatorInst>(V); - })) + if (any_of(AvailablePtrVals, [&](Value *V) { + if (V->getType() == IntToPtr->getType()) + return false; + + auto *Inst = dyn_cast<Instruction>(V); + return Inst && Inst->isTerminator(); + })) return nullptr; PHINode *NewPtrPHI = PHINode::Create( @@ -608,6 +608,7 @@ Instruction *InstCombiner::FoldPHIArgLoadIntoPHI(PHINode &PN) { LLVMContext::MD_align, LLVMContext::MD_dereferenceable, LLVMContext::MD_dereferenceable_or_null, + LLVMContext::MD_access_group, }; for (unsigned ID : KnownIDs) @@ -616,7 +617,7 @@ Instruction *InstCombiner::FoldPHIArgLoadIntoPHI(PHINode &PN) { // Add all operands to the new PHI and combine TBAA metadata. for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) { LoadInst *LI = cast<LoadInst>(PN.getIncomingValue(i)); - combineMetadata(NewLI, LI, KnownIDs); + combineMetadata(NewLI, LI, KnownIDs, true); Value *NewInVal = LI->getOperand(0); if (NewInVal != InVal) InVal = nullptr; @@ -649,7 +650,7 @@ Instruction *InstCombiner::FoldPHIArgLoadIntoPHI(PHINode &PN) { Instruction *InstCombiner::FoldPHIArgZextsIntoPHI(PHINode &Phi) { // We cannot create a new instruction after the PHI if the terminator is an // EHPad because there is no valid insertion point. - if (TerminatorInst *TI = Phi.getParent()->getTerminator()) + if (Instruction *TI = Phi.getParent()->getTerminator()) if (TI->isEHPad()) return nullptr; @@ -723,7 +724,7 @@ Instruction *InstCombiner::FoldPHIArgZextsIntoPHI(PHINode &Phi) { Instruction *InstCombiner::FoldPHIArgOpIntoPHI(PHINode &PN) { // We cannot create a new instruction after the PHI if the terminator is an // EHPad because there is no valid insertion point. - if (TerminatorInst *TI = PN.getParent()->getTerminator()) + if (Instruction *TI = PN.getParent()->getTerminator()) if (TI->isEHPad()) return nullptr; diff --git a/lib/Transforms/InstCombine/InstCombineSelect.cpp b/lib/Transforms/InstCombine/InstCombineSelect.cpp index 796b4021d273..faf58a08976d 100644 --- a/lib/Transforms/InstCombine/InstCombineSelect.cpp +++ b/lib/Transforms/InstCombine/InstCombineSelect.cpp @@ -54,34 +54,62 @@ static Value *createMinMax(InstCombiner::BuilderTy &Builder, return Builder.CreateSelect(Builder.CreateICmp(Pred, A, B), A, B); } -/// Fold -/// %A = icmp eq/ne i8 %x, 0 -/// %B = op i8 %x, %z -/// %C = select i1 %A, i8 %B, i8 %y -/// To -/// %C = select i1 %A, i8 %z, i8 %y -/// OP: binop with an identity constant -/// TODO: support for non-commutative and FP opcodes -static Instruction *foldSelectBinOpIdentity(SelectInst &Sel) { - - Value *Cond = Sel.getCondition(); - Value *X, *Z; +/// Replace a select operand based on an equality comparison with the identity +/// constant of a binop. +static Instruction *foldSelectBinOpIdentity(SelectInst &Sel, + const TargetLibraryInfo &TLI) { + // The select condition must be an equality compare with a constant operand. + Value *X; Constant *C; CmpInst::Predicate Pred; - if (!match(Cond, m_ICmp(Pred, m_Value(X), m_Constant(C))) || - !ICmpInst::isEquality(Pred)) + if (!match(Sel.getCondition(), m_Cmp(Pred, m_Value(X), m_Constant(C)))) return nullptr; - bool IsEq = Pred == ICmpInst::ICMP_EQ; - auto *BO = - dyn_cast<BinaryOperator>(IsEq ? Sel.getTrueValue() : Sel.getFalseValue()); - // TODO: support for undefs - if (BO && match(BO, m_c_BinOp(m_Specific(X), m_Value(Z))) && - ConstantExpr::getBinOpIdentity(BO->getOpcode(), X->getType()) == C) { - Sel.setOperand(IsEq ? 1 : 2, Z); - return &Sel; + bool IsEq; + if (ICmpInst::isEquality(Pred)) + IsEq = Pred == ICmpInst::ICMP_EQ; + else if (Pred == FCmpInst::FCMP_OEQ) + IsEq = true; + else if (Pred == FCmpInst::FCMP_UNE) + IsEq = false; + else + return nullptr; + + // A select operand must be a binop. + BinaryOperator *BO; + if (!match(Sel.getOperand(IsEq ? 1 : 2), m_BinOp(BO))) + return nullptr; + + // The compare constant must be the identity constant for that binop. + // If this a floating-point compare with 0.0, any zero constant will do. + Type *Ty = BO->getType(); + Constant *IdC = ConstantExpr::getBinOpIdentity(BO->getOpcode(), Ty, true); + if (IdC != C) { + if (!IdC || !CmpInst::isFPPredicate(Pred)) + return nullptr; + if (!match(IdC, m_AnyZeroFP()) || !match(C, m_AnyZeroFP())) + return nullptr; } - return nullptr; + + // Last, match the compare variable operand with a binop operand. + Value *Y; + if (!BO->isCommutative() && !match(BO, m_BinOp(m_Value(Y), m_Specific(X)))) + return nullptr; + if (!match(BO, m_c_BinOp(m_Value(Y), m_Specific(X)))) + return nullptr; + + // +0.0 compares equal to -0.0, and so it does not behave as required for this + // transform. Bail out if we can not exclude that possibility. + if (isa<FPMathOperator>(BO)) + if (!BO->hasNoSignedZeros() && !CannotBeNegativeZero(Y, &TLI)) + return nullptr; + + // BO = binop Y, X + // S = { select (cmp eq X, C), BO, ? } or { select (cmp ne X, C), ?, BO } + // => + // S = { select (cmp eq X, C), Y, ? } or { select (cmp ne X, C), ?, Y } + Sel.setOperand(IsEq ? 1 : 2, Y); + return &Sel; } /// This folds: @@ -343,13 +371,24 @@ Instruction *InstCombiner::foldSelectOpOp(SelectInst &SI, Instruction *TI, return nullptr; } + // 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())) + return nullptr; + // If we reach here, they do have operations in common. Value *NewSI = Builder.CreateSelect(SI.getCondition(), OtherOpT, OtherOpF, SI.getName() + ".v", &SI); Value *Op0 = MatchIsOpZero ? MatchOp : NewSI; Value *Op1 = MatchIsOpZero ? NewSI : MatchOp; if (auto *BO = dyn_cast<BinaryOperator>(TI)) { - return BinaryOperator::Create(BO->getOpcode(), Op0, Op1); + BinaryOperator *NewBO = BinaryOperator::Create(BO->getOpcode(), Op0, Op1); + NewBO->copyIRFlags(TI); + NewBO->andIRFlags(FI); + return NewBO; } if (auto *TGEP = dyn_cast<GetElementPtrInst>(TI)) { auto *FGEP = cast<GetElementPtrInst>(FI); @@ -670,17 +709,18 @@ static Value *foldSelectCttzCtlz(ICmpInst *ICI, Value *TrueVal, Value *FalseVal, match(Count, m_Trunc(m_Value(V)))) Count = V; + // Check that 'Count' is a call to intrinsic cttz/ctlz. Also check that the + // input to the cttz/ctlz is used as LHS for the compare instruction. + if (!match(Count, m_Intrinsic<Intrinsic::cttz>(m_Specific(CmpLHS))) && + !match(Count, m_Intrinsic<Intrinsic::ctlz>(m_Specific(CmpLHS)))) + return nullptr; + + IntrinsicInst *II = cast<IntrinsicInst>(Count); + // Check if the value propagated on zero is a constant number equal to the // sizeof in bits of 'Count'. unsigned SizeOfInBits = Count->getType()->getScalarSizeInBits(); - if (!match(ValueOnZero, m_SpecificInt(SizeOfInBits))) - return nullptr; - - // Check that 'Count' is a call to intrinsic cttz/ctlz. Also check that the - // input to the cttz/ctlz is used as LHS for the compare instruction. - if (match(Count, m_Intrinsic<Intrinsic::cttz>(m_Specific(CmpLHS))) || - match(Count, m_Intrinsic<Intrinsic::ctlz>(m_Specific(CmpLHS)))) { - IntrinsicInst *II = cast<IntrinsicInst>(Count); + if (match(ValueOnZero, m_SpecificInt(SizeOfInBits))) { // Explicitly clear the 'undef_on_zero' flag. IntrinsicInst *NewI = cast<IntrinsicInst>(II->clone()); NewI->setArgOperand(1, ConstantInt::getFalse(NewI->getContext())); @@ -688,6 +728,12 @@ static Value *foldSelectCttzCtlz(ICmpInst *ICI, Value *TrueVal, Value *FalseVal, return Builder.CreateZExtOrTrunc(NewI, ValueOnZero->getType()); } + // If the ValueOnZero is not the bitwidth, we can at least make use of the + // fact that the cttz/ctlz result will not be used if the input is zero, so + // it's okay to relax it to undef for that case. + if (II->hasOneUse() && !match(II->getArgOperand(1), m_One())) + II->setArgOperand(1, ConstantInt::getTrue(II->getContext())); + return nullptr; } @@ -1054,11 +1100,13 @@ Instruction *InstCombiner::foldSPFofSPF(Instruction *Inner, if (C == A || C == B) { // MAX(MAX(A, B), B) -> MAX(A, B) // MIN(MIN(a, b), a) -> MIN(a, b) + // TODO: This could be done in instsimplify. if (SPF1 == SPF2 && SelectPatternResult::isMinOrMax(SPF1)) return replaceInstUsesWith(Outer, Inner); // MAX(MIN(a, b), a) -> a // MIN(MAX(a, b), a) -> a + // TODO: This could be done in instsimplify. if ((SPF1 == SPF_SMIN && SPF2 == SPF_SMAX) || (SPF1 == SPF_SMAX && SPF2 == SPF_SMIN) || (SPF1 == SPF_UMIN && SPF2 == SPF_UMAX) || @@ -1071,6 +1119,7 @@ Instruction *InstCombiner::foldSPFofSPF(Instruction *Inner, if (match(B, m_APInt(CB)) && match(C, m_APInt(CC))) { // MIN(MIN(A, 23), 97) -> MIN(A, 23) // MAX(MAX(A, 97), 23) -> MAX(A, 97) + // TODO: This could be done in instsimplify. if ((SPF1 == SPF_UMIN && CB->ule(*CC)) || (SPF1 == SPF_SMIN && CB->sle(*CC)) || (SPF1 == SPF_UMAX && CB->uge(*CC)) || @@ -1091,6 +1140,7 @@ Instruction *InstCombiner::foldSPFofSPF(Instruction *Inner, // ABS(ABS(X)) -> ABS(X) // NABS(NABS(X)) -> NABS(X) + // TODO: This could be done in instsimplify. if (SPF1 == SPF2 && (SPF1 == SPF_ABS || SPF1 == SPF_NABS)) { return replaceInstUsesWith(Outer, Inner); } @@ -1503,6 +1553,60 @@ static Instruction *factorizeMinMaxTree(SelectPatternFlavor SPF, Value *LHS, return SelectInst::Create(CmpABC, MinMaxOp, ThirdOp); } +/// Try to reduce a rotate pattern that includes a compare and select into a +/// funnel shift intrinsic. Example: +/// rotl32(a, b) --> (b == 0 ? a : ((a >> (32 - b)) | (a << b))) +/// --> call llvm.fshl.i32(a, a, b) +static Instruction *foldSelectRotate(SelectInst &Sel) { + // The false value of the select must be a rotate of the true value. + Value *Or0, *Or1; + if (!match(Sel.getFalseValue(), m_OneUse(m_Or(m_Value(Or0), m_Value(Or1))))) + return nullptr; + + Value *TVal = Sel.getTrueValue(); + Value *SA0, *SA1; + if (!match(Or0, m_OneUse(m_LogicalShift(m_Specific(TVal), m_Value(SA0)))) || + !match(Or1, m_OneUse(m_LogicalShift(m_Specific(TVal), m_Value(SA1))))) + return nullptr; + + auto ShiftOpcode0 = cast<BinaryOperator>(Or0)->getOpcode(); + auto ShiftOpcode1 = cast<BinaryOperator>(Or1)->getOpcode(); + if (ShiftOpcode0 == ShiftOpcode1) + return nullptr; + + // We have one of these patterns so far: + // select ?, TVal, (or (lshr TVal, SA0), (shl TVal, SA1)) + // select ?, TVal, (or (shl TVal, SA0), (lshr TVal, SA1)) + // This must be a power-of-2 rotate for a bitmasking transform to be valid. + unsigned Width = Sel.getType()->getScalarSizeInBits(); + if (!isPowerOf2_32(Width)) + return nullptr; + + // Check the shift amounts to see if they are an opposite pair. + Value *ShAmt; + if (match(SA1, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA0))))) + ShAmt = SA0; + else if (match(SA0, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA1))))) + ShAmt = SA1; + else + return nullptr; + + // Finally, see if the select is filtering out a shift-by-zero. + Value *Cond = Sel.getCondition(); + ICmpInst::Predicate Pred; + if (!match(Cond, m_OneUse(m_ICmp(Pred, m_Specific(ShAmt), m_ZeroInt()))) || + Pred != ICmpInst::ICMP_EQ) + return nullptr; + + // This is a rotate that avoids shift-by-bitwidth UB in a suboptimal way. + // Convert to funnel shift intrinsic. + bool IsFshl = (ShAmt == SA0 && ShiftOpcode0 == BinaryOperator::Shl) || + (ShAmt == SA1 && ShiftOpcode1 == BinaryOperator::Shl); + Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr; + Function *F = Intrinsic::getDeclaration(Sel.getModule(), IID, Sel.getType()); + return IntrinsicInst::Create(F, { TVal, TVal, ShAmt }); +} + Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { Value *CondVal = SI.getCondition(); Value *TrueVal = SI.getTrueValue(); @@ -1617,31 +1721,6 @@ Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { // See if we are selecting two values based on a comparison of the two values. if (FCmpInst *FCI = dyn_cast<FCmpInst>(CondVal)) { if (FCI->getOperand(0) == TrueVal && FCI->getOperand(1) == FalseVal) { - // Transform (X == Y) ? X : Y -> Y - if (FCI->getPredicate() == FCmpInst::FCMP_OEQ) { - // This is not safe in general for floating point: - // consider X== -0, Y== +0. - // It becomes safe if either operand is a nonzero constant. - ConstantFP *CFPt, *CFPf; - if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) && - !CFPt->getValueAPF().isZero()) || - ((CFPf = dyn_cast<ConstantFP>(FalseVal)) && - !CFPf->getValueAPF().isZero())) - return replaceInstUsesWith(SI, FalseVal); - } - // Transform (X une Y) ? X : Y -> X - if (FCI->getPredicate() == FCmpInst::FCMP_UNE) { - // This is not safe in general for floating point: - // consider X== -0, Y== +0. - // It becomes safe if either operand is a nonzero constant. - ConstantFP *CFPt, *CFPf; - if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) && - !CFPt->getValueAPF().isZero()) || - ((CFPf = dyn_cast<ConstantFP>(FalseVal)) && - !CFPf->getValueAPF().isZero())) - return replaceInstUsesWith(SI, TrueVal); - } - // Canonicalize to use ordered comparisons by swapping the select // operands. // @@ -1660,31 +1739,6 @@ Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { // NOTE: if we wanted to, this is where to detect MIN/MAX } else if (FCI->getOperand(0) == FalseVal && FCI->getOperand(1) == TrueVal){ - // Transform (X == Y) ? Y : X -> X - if (FCI->getPredicate() == FCmpInst::FCMP_OEQ) { - // This is not safe in general for floating point: - // consider X== -0, Y== +0. - // It becomes safe if either operand is a nonzero constant. - ConstantFP *CFPt, *CFPf; - if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) && - !CFPt->getValueAPF().isZero()) || - ((CFPf = dyn_cast<ConstantFP>(FalseVal)) && - !CFPf->getValueAPF().isZero())) - return replaceInstUsesWith(SI, FalseVal); - } - // Transform (X une Y) ? Y : X -> Y - if (FCI->getPredicate() == FCmpInst::FCMP_UNE) { - // This is not safe in general for floating point: - // consider X== -0, Y== +0. - // It becomes safe if either operand is a nonzero constant. - ConstantFP *CFPt, *CFPf; - if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) && - !CFPt->getValueAPF().isZero()) || - ((CFPf = dyn_cast<ConstantFP>(FalseVal)) && - !CFPf->getValueAPF().isZero())) - return replaceInstUsesWith(SI, TrueVal); - } - // Canonicalize to use ordered comparisons by swapping the select // operands. // @@ -1717,7 +1771,7 @@ Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { 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.CreateIntrinsic(Intrinsic::fabs, { X }, FCI); + Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, FCI); return replaceInstUsesWith(SI, Fabs); } // With nsz: @@ -1730,7 +1784,7 @@ Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { (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.CreateIntrinsic(Intrinsic::fabs, { X }, FCI); + Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, X, FCI); return replaceInstUsesWith(SI, Fabs); } } @@ -1759,10 +1813,23 @@ Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { if (Instruction *FoldI = foldSelectIntoOp(SI, TrueVal, FalseVal)) return FoldI; - Value *LHS, *RHS, *LHS2, *RHS2; + Value *LHS, *RHS; Instruction::CastOps CastOp; SelectPatternResult SPR = matchSelectPattern(&SI, LHS, RHS, &CastOp); auto SPF = SPR.Flavor; + if (SPF) { + Value *LHS2, *RHS2; + if (SelectPatternFlavor SPF2 = matchSelectPattern(LHS, LHS2, RHS2).Flavor) + if (Instruction *R = foldSPFofSPF(cast<Instruction>(LHS), SPF2, LHS2, + RHS2, SI, SPF, RHS)) + return R; + if (SelectPatternFlavor SPF2 = matchSelectPattern(RHS, LHS2, RHS2).Flavor) + if (Instruction *R = foldSPFofSPF(cast<Instruction>(RHS), SPF2, LHS2, + RHS2, SI, SPF, LHS)) + return R; + // TODO. + // ABS(-X) -> ABS(X) + } if (SelectPatternResult::isMinOrMax(SPF)) { // Canonicalize so that @@ -1797,39 +1864,40 @@ Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { } // MAX(~a, ~b) -> ~MIN(a, b) + // MAX(~a, C) -> ~MIN(a, ~C) // MIN(~a, ~b) -> ~MAX(a, b) - Value *A, *B; - if (match(LHS, m_Not(m_Value(A))) && match(RHS, m_Not(m_Value(B))) && - (LHS->getNumUses() <= 2 || RHS->getNumUses() <= 2)) { - CmpInst::Predicate InvertedPred = getInverseMinMaxPred(SPF); - Value *InvertedCmp = Builder.CreateICmp(InvertedPred, A, B); - Value *NewSel = Builder.CreateSelect(InvertedCmp, A, B); - return BinaryOperator::CreateNot(NewSel); - } + // MIN(~a, C) -> ~MAX(a, ~C) + auto moveNotAfterMinMax = [&](Value *X, Value *Y) -> Instruction * { + Value *A; + if (match(X, m_Not(m_Value(A))) && !X->hasNUsesOrMore(3) && + !IsFreeToInvert(A, A->hasOneUse()) && + // Passing false to only consider m_Not and constants. + IsFreeToInvert(Y, false)) { + Value *B = Builder.CreateNot(Y); + Value *NewMinMax = createMinMax(Builder, getInverseMinMaxFlavor(SPF), + A, B); + // Copy the profile metadata. + if (MDNode *MD = SI.getMetadata(LLVMContext::MD_prof)) { + cast<SelectInst>(NewMinMax)->setMetadata(LLVMContext::MD_prof, MD); + // Swap the metadata if the operands are swapped. + if (X == SI.getFalseValue() && Y == SI.getTrueValue()) + cast<SelectInst>(NewMinMax)->swapProfMetadata(); + } - if (Instruction *I = factorizeMinMaxTree(SPF, LHS, RHS, Builder)) + return BinaryOperator::CreateNot(NewMinMax); + } + + return nullptr; + }; + + if (Instruction *I = moveNotAfterMinMax(LHS, RHS)) + return I; + if (Instruction *I = moveNotAfterMinMax(RHS, LHS)) return I; - } - if (SPF) { - // MAX(MAX(a, b), a) -> MAX(a, b) - // MIN(MIN(a, b), a) -> MIN(a, b) - // MAX(MIN(a, b), a) -> a - // MIN(MAX(a, b), a) -> a - // ABS(ABS(a)) -> ABS(a) - // NABS(NABS(a)) -> NABS(a) - if (SelectPatternFlavor SPF2 = matchSelectPattern(LHS, LHS2, RHS2).Flavor) - if (Instruction *R = foldSPFofSPF(cast<Instruction>(LHS),SPF2,LHS2,RHS2, - SI, SPF, RHS)) - return R; - if (SelectPatternFlavor SPF2 = matchSelectPattern(RHS, LHS2, RHS2).Flavor) - if (Instruction *R = foldSPFofSPF(cast<Instruction>(RHS),SPF2,LHS2,RHS2, - SI, SPF, LHS)) - return R; + if (Instruction *I = factorizeMinMaxTree(SPF, LHS, RHS, Builder)) + return I; } - - // TODO. - // ABS(-X) -> ABS(X) } // See if we can fold the select into a phi node if the condition is a select. @@ -1934,10 +2002,12 @@ Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { } } - if (BinaryOperator::isNot(CondVal)) { - SI.setOperand(0, BinaryOperator::getNotArgument(CondVal)); + Value *NotCond; + if (match(CondVal, m_Not(m_Value(NotCond)))) { + SI.setOperand(0, NotCond); SI.setOperand(1, FalseVal); SI.setOperand(2, TrueVal); + SI.swapProfMetadata(); return &SI; } @@ -1952,24 +2022,6 @@ Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { } } - // See if we can determine the result of this select based on a dominating - // condition. - BasicBlock *Parent = SI.getParent(); - if (BasicBlock *Dom = Parent->getSinglePredecessor()) { - auto *PBI = dyn_cast_or_null<BranchInst>(Dom->getTerminator()); - if (PBI && PBI->isConditional() && - PBI->getSuccessor(0) != PBI->getSuccessor(1) && - (PBI->getSuccessor(0) == Parent || PBI->getSuccessor(1) == Parent)) { - bool CondIsTrue = PBI->getSuccessor(0) == Parent; - Optional<bool> Implication = isImpliedCondition( - PBI->getCondition(), SI.getCondition(), DL, CondIsTrue); - if (Implication) { - Value *V = *Implication ? TrueVal : FalseVal; - return replaceInstUsesWith(SI, V); - } - } - } - // If we can compute the condition, there's no need for a select. // Like the above fold, we are attempting to reduce compile-time cost by // putting this fold here with limitations rather than in InstSimplify. @@ -1991,8 +2043,11 @@ Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { if (Instruction *Select = foldSelectCmpXchg(SI)) return Select; - if (Instruction *Select = foldSelectBinOpIdentity(SI)) + if (Instruction *Select = foldSelectBinOpIdentity(SI, TLI)) return Select; + if (Instruction *Rot = foldSelectRotate(SI)) + return Rot; + return nullptr; } diff --git a/lib/Transforms/InstCombine/InstCombineShifts.cpp b/lib/Transforms/InstCombine/InstCombineShifts.cpp index 1ca75f3989d4..c562d45a9e2b 100644 --- a/lib/Transforms/InstCombine/InstCombineShifts.cpp +++ b/lib/Transforms/InstCombine/InstCombineShifts.cpp @@ -593,7 +593,7 @@ Instruction *InstCombiner::visitShl(BinaryOperator &I) { SQ.getWithInstruction(&I))) return replaceInstUsesWith(I, V); - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; if (Instruction *V = commonShiftTransforms(I)) @@ -697,7 +697,7 @@ Instruction *InstCombiner::visitLShr(BinaryOperator &I) { SQ.getWithInstruction(&I))) return replaceInstUsesWith(I, V); - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; if (Instruction *R = commonShiftTransforms(I)) @@ -725,9 +725,9 @@ Instruction *InstCombiner::visitLShr(BinaryOperator &I) { Value *X; const APInt *ShOp1; - if (match(Op0, m_Shl(m_Value(X), m_APInt(ShOp1)))) { - unsigned ShlAmt = ShOp1->getZExtValue(); - if (ShlAmt < ShAmt) { + if (match(Op0, m_Shl(m_Value(X), m_APInt(ShOp1))) && ShOp1->ult(BitWidth)) { + if (ShOp1->ult(ShAmt)) { + unsigned ShlAmt = ShOp1->getZExtValue(); Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShlAmt); if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) { // (X <<nuw C1) >>u C2 --> X >>u (C2 - C1) @@ -740,7 +740,8 @@ Instruction *InstCombiner::visitLShr(BinaryOperator &I) { APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmt)); return BinaryOperator::CreateAnd(NewLShr, ConstantInt::get(Ty, Mask)); } - if (ShlAmt > ShAmt) { + if (ShOp1->ugt(ShAmt)) { + unsigned ShlAmt = ShOp1->getZExtValue(); Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmt - ShAmt); if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) { // (X <<nuw C1) >>u C2 --> X <<nuw (C1 - C2) @@ -753,7 +754,7 @@ Instruction *InstCombiner::visitLShr(BinaryOperator &I) { APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmt)); return BinaryOperator::CreateAnd(NewShl, ConstantInt::get(Ty, Mask)); } - assert(ShlAmt == ShAmt); + assert(*ShOp1 == ShAmt); // (X << C) >>u C --> X & (-1 >>u C) APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmt)); return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask)); @@ -825,7 +826,7 @@ Instruction *InstCombiner::visitAShr(BinaryOperator &I) { SQ.getWithInstruction(&I))) return replaceInstUsesWith(I, V); - if (Instruction *X = foldShuffledBinop(I)) + if (Instruction *X = foldVectorBinop(I)) return X; if (Instruction *R = commonShiftTransforms(I)) diff --git a/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp b/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp index 425f5ce384be..9bf87d024607 100644 --- a/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp +++ b/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp @@ -314,11 +314,32 @@ Value *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask, Known.One = std::move(IKnownOne); break; } - case Instruction::Select: - // If this is a select as part of a min/max pattern, don't simplify any - // further in case we break the structure. + case Instruction::Select: { Value *LHS, *RHS; - if (matchSelectPattern(I, LHS, RHS).Flavor != SPF_UNKNOWN) + SelectPatternFlavor SPF = matchSelectPattern(I, LHS, RHS).Flavor; + if (SPF == SPF_UMAX) { + // UMax(A, C) == A if ... + // The lowest non-zero bit of DemandMask is higher than the highest + // non-zero bit of C. + const APInt *C; + unsigned CTZ = DemandedMask.countTrailingZeros(); + if (match(RHS, m_APInt(C)) && CTZ >= C->getActiveBits()) + return LHS; + } else if (SPF == SPF_UMIN) { + // UMin(A, C) == A if ... + // The lowest non-zero bit of DemandMask is higher than the highest + // non-one bit of C. + // This comes from using DeMorgans on the above umax example. + const APInt *C; + unsigned CTZ = DemandedMask.countTrailingZeros(); + if (match(RHS, m_APInt(C)) && + CTZ >= C->getBitWidth() - C->countLeadingOnes()) + return LHS; + } + + // If this is a select as part of any other min/max pattern, don't simplify + // any further in case we break the structure. + if (SPF != SPF_UNKNOWN) return nullptr; if (SimplifyDemandedBits(I, 2, DemandedMask, RHSKnown, Depth + 1) || @@ -336,6 +357,7 @@ Value *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask, Known.One = RHSKnown.One & LHSKnown.One; Known.Zero = RHSKnown.Zero & LHSKnown.Zero; break; + } case Instruction::ZExt: case Instruction::Trunc: { unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits(); @@ -668,6 +690,30 @@ Value *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask, // TODO: Could compute known zero/one bits based on the input. break; } + case Intrinsic::fshr: + case Intrinsic::fshl: { + const APInt *SA; + if (!match(I->getOperand(2), m_APInt(SA))) + break; + + // Normalize to funnel shift left. APInt shifts of BitWidth are well- + // defined, so no need to special-case zero shifts here. + uint64_t ShiftAmt = SA->urem(BitWidth); + if (II->getIntrinsicID() == Intrinsic::fshr) + ShiftAmt = BitWidth - ShiftAmt; + + APInt DemandedMaskLHS(DemandedMask.lshr(ShiftAmt)); + APInt DemandedMaskRHS(DemandedMask.shl(BitWidth - ShiftAmt)); + if (SimplifyDemandedBits(I, 0, DemandedMaskLHS, LHSKnown, Depth + 1) || + SimplifyDemandedBits(I, 1, DemandedMaskRHS, RHSKnown, Depth + 1)) + return I; + + Known.Zero = LHSKnown.Zero.shl(ShiftAmt) | + RHSKnown.Zero.lshr(BitWidth - ShiftAmt); + Known.One = LHSKnown.One.shl(ShiftAmt) | + RHSKnown.One.lshr(BitWidth - ShiftAmt); + break; + } case Intrinsic::x86_mmx_pmovmskb: case Intrinsic::x86_sse_movmsk_ps: case Intrinsic::x86_sse2_movmsk_pd: @@ -923,11 +969,24 @@ InstCombiner::simplifyShrShlDemandedBits(Instruction *Shr, const APInt &ShrOp1, /// Implement SimplifyDemandedVectorElts for amdgcn buffer and image intrinsics. Value *InstCombiner::simplifyAMDGCNMemoryIntrinsicDemanded(IntrinsicInst *II, APInt DemandedElts, - int DMaskIdx) { + int DMaskIdx, + int TFCIdx) { 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) { @@ -1052,8 +1111,7 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, UndefElts = 0; - // Handle ConstantAggregateZero, ConstantVector, ConstantDataSequential. - if (Constant *C = dyn_cast<Constant>(V)) { + if (auto *C = dyn_cast<Constant>(V)) { // Check if this is identity. If so, return 0 since we are not simplifying // anything. if (DemandedElts.isAllOnesValue()) @@ -1061,7 +1119,6 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, Type *EltTy = cast<VectorType>(V->getType())->getElementType(); Constant *Undef = UndefValue::get(EltTy); - SmallVector<Constant*, 16> Elts; for (unsigned i = 0; i != VWidth; ++i) { if (!DemandedElts[i]) { // If not demanded, set to undef. @@ -1109,9 +1166,21 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, if (!I) return nullptr; // Only analyze instructions. bool MadeChange = false; + auto simplifyAndSetOp = [&](Instruction *Inst, unsigned OpNum, + APInt Demanded, APInt &Undef) { + auto *II = dyn_cast<IntrinsicInst>(Inst); + Value *Op = II ? II->getArgOperand(OpNum) : Inst->getOperand(OpNum); + if (Value *V = SimplifyDemandedVectorElts(Op, Demanded, Undef, Depth + 1)) { + if (II) + II->setArgOperand(OpNum, V); + else + Inst->setOperand(OpNum, V); + MadeChange = true; + } + }; + APInt UndefElts2(VWidth, 0); APInt UndefElts3(VWidth, 0); - Value *TmpV; switch (I->getOpcode()) { default: break; @@ -1122,9 +1191,7 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, if (!Idx) { // Note that we can't propagate undef elt info, because we don't know // which elt is getting updated. - TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, - UndefElts2, Depth + 1); - if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } + simplifyAndSetOp(I, 0, DemandedElts, UndefElts2); break; } @@ -1134,9 +1201,8 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt PreInsertDemandedElts = DemandedElts; if (IdxNo < VWidth) PreInsertDemandedElts.clearBit(IdxNo); - TmpV = SimplifyDemandedVectorElts(I->getOperand(0), PreInsertDemandedElts, - UndefElts, Depth + 1); - if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } + + simplifyAndSetOp(I, 0, PreInsertDemandedElts, UndefElts); // If this is inserting an element that isn't demanded, remove this // insertelement. @@ -1169,14 +1235,10 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, } APInt LHSUndefElts(LHSVWidth, 0); - TmpV = SimplifyDemandedVectorElts(I->getOperand(0), LeftDemanded, - LHSUndefElts, Depth + 1); - if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } + simplifyAndSetOp(I, 0, LeftDemanded, LHSUndefElts); APInt RHSUndefElts(LHSVWidth, 0); - TmpV = SimplifyDemandedVectorElts(I->getOperand(1), RightDemanded, - RHSUndefElts, Depth + 1); - if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } + simplifyAndSetOp(I, 1, RightDemanded, RHSUndefElts); bool NewUndefElts = false; unsigned LHSIdx = -1u, LHSValIdx = -1u; @@ -1260,32 +1322,43 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, break; } case Instruction::Select: { - APInt LeftDemanded(DemandedElts), RightDemanded(DemandedElts); - if (ConstantVector* CV = dyn_cast<ConstantVector>(I->getOperand(0))) { + // If this is a vector select, try to transform the select condition based + // on the current demanded elements. + SelectInst *Sel = cast<SelectInst>(I); + if (Sel->getCondition()->getType()->isVectorTy()) { + // TODO: We are not doing anything with UndefElts based on this call. + // It is overwritten below based on the other select operands. If an + // element of the select condition is known undef, then we are free to + // choose the output value from either arm of the select. If we know that + // one of those values is undef, then the output can be undef. + simplifyAndSetOp(I, 0, DemandedElts, UndefElts); + } + + // Next, see if we can transform the arms of the select. + APInt DemandedLHS(DemandedElts), DemandedRHS(DemandedElts); + if (auto *CV = dyn_cast<ConstantVector>(Sel->getCondition())) { for (unsigned i = 0; i < VWidth; i++) { + // isNullValue() always returns false when called on a ConstantExpr. + // Skip constant expressions to avoid propagating incorrect information. Constant *CElt = CV->getAggregateElement(i); - // Method isNullValue always returns false when called on a - // ConstantExpr. If CElt is a ConstantExpr then skip it in order to - // to avoid propagating incorrect information. if (isa<ConstantExpr>(CElt)) continue; + // TODO: If a select condition element is undef, we can demand from + // either side. If one side is known undef, choosing that side would + // propagate undef. if (CElt->isNullValue()) - LeftDemanded.clearBit(i); + DemandedLHS.clearBit(i); else - RightDemanded.clearBit(i); + DemandedRHS.clearBit(i); } } - TmpV = SimplifyDemandedVectorElts(I->getOperand(1), LeftDemanded, UndefElts, - Depth + 1); - if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } - - TmpV = SimplifyDemandedVectorElts(I->getOperand(2), RightDemanded, - UndefElts2, Depth + 1); - if (TmpV) { I->setOperand(2, TmpV); MadeChange = true; } + simplifyAndSetOp(I, 1, DemandedLHS, UndefElts2); + simplifyAndSetOp(I, 2, DemandedRHS, UndefElts3); - // Output elements are undefined if both are undefined. - UndefElts &= UndefElts2; + // Output elements are undefined if the element from each arm is undefined. + // TODO: This can be improved. See comment in select condition handling. + UndefElts = UndefElts2 & UndefElts3; break; } case Instruction::BitCast: { @@ -1323,12 +1396,7 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, break; } - TmpV = SimplifyDemandedVectorElts(I->getOperand(0), InputDemandedElts, - UndefElts2, Depth + 1); - if (TmpV) { - I->setOperand(0, TmpV); - MadeChange = true; - } + simplifyAndSetOp(I, 0, InputDemandedElts, UndefElts2); if (VWidth == InVWidth) { UndefElts = UndefElts2; @@ -1353,29 +1421,9 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, } break; } - case Instruction::And: - case Instruction::Or: - case Instruction::Xor: - case Instruction::Add: - case Instruction::Sub: - case Instruction::Mul: - // div/rem demand all inputs, because they don't want divide by zero. - TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, UndefElts, - Depth + 1); - if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } - TmpV = SimplifyDemandedVectorElts(I->getOperand(1), DemandedElts, - UndefElts2, Depth + 1); - if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } - - // Output elements are undefined if both are undefined. Consider things - // like undef&0. The result is known zero, not undef. - UndefElts &= UndefElts2; - break; case Instruction::FPTrunc: case Instruction::FPExt: - TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, UndefElts, - Depth + 1); - if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } + simplifyAndSetOp(I, 0, DemandedElts, UndefElts); break; case Instruction::Call: { @@ -1395,9 +1443,7 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, // Only the lower element is used. DemandedElts = 1; - TmpV = SimplifyDemandedVectorElts(II->getArgOperand(0), DemandedElts, - UndefElts, Depth + 1); - if (TmpV) { II->setArgOperand(0, TmpV); MadeChange = true; } + simplifyAndSetOp(II, 0, DemandedElts, UndefElts); // Only the lower element is undefined. The high elements are zero. UndefElts = UndefElts[0]; @@ -1406,9 +1452,7 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, // Unary scalar-as-vector operations that work column-wise. case Intrinsic::x86_sse_rcp_ss: case Intrinsic::x86_sse_rsqrt_ss: - TmpV = SimplifyDemandedVectorElts(II->getArgOperand(0), DemandedElts, - UndefElts, Depth + 1); - if (TmpV) { II->setArgOperand(0, TmpV); MadeChange = true; } + simplifyAndSetOp(II, 0, DemandedElts, UndefElts); // If lowest element of a scalar op isn't used then use Arg0. if (!DemandedElts[0]) { @@ -1428,9 +1472,7 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, case Intrinsic::x86_sse2_min_sd: case Intrinsic::x86_sse2_max_sd: case Intrinsic::x86_sse2_cmp_sd: { - TmpV = SimplifyDemandedVectorElts(II->getArgOperand(0), DemandedElts, - UndefElts, Depth + 1); - if (TmpV) { II->setArgOperand(0, TmpV); MadeChange = true; } + simplifyAndSetOp(II, 0, DemandedElts, UndefElts); // If lowest element of a scalar op isn't used then use Arg0. if (!DemandedElts[0]) { @@ -1440,9 +1482,7 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, // Only lower element is used for operand 1. DemandedElts = 1; - TmpV = SimplifyDemandedVectorElts(II->getArgOperand(1), DemandedElts, - UndefElts2, Depth + 1); - if (TmpV) { II->setArgOperand(1, TmpV); MadeChange = true; } + simplifyAndSetOp(II, 1, DemandedElts, UndefElts2); // Lower element is undefined if both lower elements are undefined. // Consider things like undef&0. The result is known zero, not undef. @@ -1459,9 +1499,7 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, // Don't use the low element of operand 0. APInt DemandedElts2 = DemandedElts; DemandedElts2.clearBit(0); - TmpV = SimplifyDemandedVectorElts(II->getArgOperand(0), DemandedElts2, - UndefElts, Depth + 1); - if (TmpV) { II->setArgOperand(0, TmpV); MadeChange = true; } + simplifyAndSetOp(II, 0, DemandedElts2, UndefElts); // If lowest element of a scalar op isn't used then use Arg0. if (!DemandedElts[0]) { @@ -1471,9 +1509,7 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, // Only lower element is used for operand 1. DemandedElts = 1; - TmpV = SimplifyDemandedVectorElts(II->getArgOperand(1), DemandedElts, - UndefElts2, Depth + 1); - if (TmpV) { II->setArgOperand(1, TmpV); MadeChange = true; } + simplifyAndSetOp(II, 1, DemandedElts, UndefElts2); // Take the high undef elements from operand 0 and take the lower element // from operand 1. @@ -1497,9 +1533,7 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, case Intrinsic::x86_avx512_mask_sub_sd_round: case Intrinsic::x86_avx512_mask_max_sd_round: case Intrinsic::x86_avx512_mask_min_sd_round: - TmpV = SimplifyDemandedVectorElts(II->getArgOperand(0), DemandedElts, - UndefElts, Depth + 1); - if (TmpV) { II->setArgOperand(0, TmpV); MadeChange = true; } + simplifyAndSetOp(II, 0, DemandedElts, UndefElts); // If lowest element of a scalar op isn't used then use Arg0. if (!DemandedElts[0]) { @@ -1509,12 +1543,8 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, // Only lower element is used for operand 1 and 2. DemandedElts = 1; - TmpV = SimplifyDemandedVectorElts(II->getArgOperand(1), DemandedElts, - UndefElts2, Depth + 1); - if (TmpV) { II->setArgOperand(1, TmpV); MadeChange = true; } - TmpV = SimplifyDemandedVectorElts(II->getArgOperand(2), DemandedElts, - UndefElts3, Depth + 1); - if (TmpV) { II->setArgOperand(2, TmpV); MadeChange = true; } + simplifyAndSetOp(II, 1, DemandedElts, UndefElts2); + simplifyAndSetOp(II, 2, DemandedElts, UndefElts3); // Lower element is undefined if all three lower elements are undefined. // Consider things like undef&0. The result is known zero, not undef. @@ -1559,14 +1589,8 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, } // Demand elements from the operand. - auto *Op = II->getArgOperand(OpNum); APInt OpUndefElts(InnerVWidth, 0); - TmpV = SimplifyDemandedVectorElts(Op, OpDemandedElts, OpUndefElts, - Depth + 1); - if (TmpV) { - II->setArgOperand(OpNum, TmpV); - MadeChange = true; - } + simplifyAndSetOp(II, OpNum, OpDemandedElts, OpUndefElts); // Pack the operand's UNDEF elements, one lane at a time. OpUndefElts = OpUndefElts.zext(VWidth); @@ -1594,10 +1618,7 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, // PERMV case Intrinsic::x86_avx2_permd: case Intrinsic::x86_avx2_permps: { - Value *Op1 = II->getArgOperand(1); - TmpV = SimplifyDemandedVectorElts(Op1, DemandedElts, UndefElts, - Depth + 1); - if (TmpV) { II->setArgOperand(1, TmpV); MadeChange = true; } + simplifyAndSetOp(II, 1, DemandedElts, UndefElts); break; } @@ -1611,16 +1632,40 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, break; case Intrinsic::amdgcn_buffer_load: case Intrinsic::amdgcn_buffer_load_format: + case Intrinsic::amdgcn_raw_buffer_load: + case Intrinsic::amdgcn_raw_buffer_load_format: + case Intrinsic::amdgcn_struct_buffer_load: + case Intrinsic::amdgcn_struct_buffer_load_format: return simplifyAMDGCNMemoryIntrinsicDemanded(II, DemandedElts); default: { if (getAMDGPUImageDMaskIntrinsic(II->getIntrinsicID())) - return simplifyAMDGCNMemoryIntrinsicDemanded(II, DemandedElts, 0); + return simplifyAMDGCNMemoryIntrinsicDemanded( + II, DemandedElts, 0, II->getNumArgOperands() - 2); break; } - } + } // switch on IntrinsicID break; + } // case Call + } // switch on Opcode + + // TODO: We bail completely on integer div/rem and shifts because they have + // UB/poison potential, but that should be refined. + BinaryOperator *BO; + if (match(I, m_BinOp(BO)) && !BO->isIntDivRem() && !BO->isShift()) { + simplifyAndSetOp(I, 0, DemandedElts, UndefElts); + simplifyAndSetOp(I, 1, DemandedElts, UndefElts2); + + // Any change to an instruction with potential poison must clear those flags + // because we can not guarantee those constraints now. Other analysis may + // determine that it is safe to re-apply the flags. + if (MadeChange) + BO->dropPoisonGeneratingFlags(); + + // Output elements are undefined if both are undefined. Consider things + // like undef & 0. The result is known zero, not undef. + UndefElts &= UndefElts2; } - } + return MadeChange ? I : nullptr; } diff --git a/lib/Transforms/InstCombine/InstCombineVectorOps.cpp b/lib/Transforms/InstCombine/InstCombineVectorOps.cpp index 1c2de6352fa5..0ad1fc0e791f 100644 --- a/lib/Transforms/InstCombine/InstCombineVectorOps.cpp +++ b/lib/Transforms/InstCombine/InstCombineVectorOps.cpp @@ -46,40 +46,34 @@ using namespace PatternMatch; #define DEBUG_TYPE "instcombine" /// Return true if the value is cheaper to scalarize than it is to leave as a -/// vector operation. isConstant indicates whether we're extracting one known -/// element. If false we're extracting a variable index. -static bool cheapToScalarize(Value *V, bool isConstant) { - if (Constant *C = dyn_cast<Constant>(V)) { - if (isConstant) return true; +/// vector operation. IsConstantExtractIndex indicates whether we are extracting +/// one known element from a vector constant. +/// +/// FIXME: It's possible to create more instructions than previously existed. +static bool cheapToScalarize(Value *V, bool IsConstantExtractIndex) { + // If we can pick a scalar constant value out of a vector, that is free. + if (auto *C = dyn_cast<Constant>(V)) + return IsConstantExtractIndex || C->getSplatValue(); - // If all elts are the same, we can extract it and use any of the values. - if (Constant *Op0 = C->getAggregateElement(0U)) { - for (unsigned i = 1, e = V->getType()->getVectorNumElements(); i != e; - ++i) - if (C->getAggregateElement(i) != Op0) - return false; - return true; - } - } - Instruction *I = dyn_cast<Instruction>(V); - if (!I) return false; + // An insertelement to the same constant index as our extract will simplify + // to the scalar inserted element. An insertelement to a different constant + // index is irrelevant to our extract. + if (match(V, m_InsertElement(m_Value(), m_Value(), m_ConstantInt()))) + return IsConstantExtractIndex; - // Insert element gets simplified to the inserted element or is deleted if - // this is constant idx extract element and its a constant idx insertelt. - if (I->getOpcode() == Instruction::InsertElement && isConstant && - isa<ConstantInt>(I->getOperand(2))) - return true; - if (I->getOpcode() == Instruction::Load && I->hasOneUse()) + if (match(V, m_OneUse(m_Load(m_Value())))) return true; - if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) - if (BO->hasOneUse() && - (cheapToScalarize(BO->getOperand(0), isConstant) || - cheapToScalarize(BO->getOperand(1), isConstant))) + + Value *V0, *V1; + if (match(V, m_OneUse(m_BinOp(m_Value(V0), m_Value(V1))))) + if (cheapToScalarize(V0, IsConstantExtractIndex) || + cheapToScalarize(V1, IsConstantExtractIndex)) return true; - if (CmpInst *CI = dyn_cast<CmpInst>(I)) - if (CI->hasOneUse() && - (cheapToScalarize(CI->getOperand(0), isConstant) || - cheapToScalarize(CI->getOperand(1), isConstant))) + + CmpInst::Predicate UnusedPred; + if (match(V, m_OneUse(m_Cmp(UnusedPred, m_Value(V0), m_Value(V1))))) + if (cheapToScalarize(V0, IsConstantExtractIndex) || + cheapToScalarize(V1, IsConstantExtractIndex)) return true; return false; @@ -166,92 +160,176 @@ Instruction *InstCombiner::scalarizePHI(ExtractElementInst &EI, PHINode *PN) { return &EI; } +static Instruction *foldBitcastExtElt(ExtractElementInst &Ext, + InstCombiner::BuilderTy &Builder, + bool IsBigEndian) { + Value *X; + uint64_t ExtIndexC; + if (!match(Ext.getVectorOperand(), m_BitCast(m_Value(X))) || + !X->getType()->isVectorTy() || + !match(Ext.getIndexOperand(), m_ConstantInt(ExtIndexC))) + return nullptr; + + // If this extractelement is using a bitcast from a vector of the same number + // of elements, see if we can find the source element from the source vector: + // extelt (bitcast VecX), IndexC --> bitcast X[IndexC] + Type *SrcTy = X->getType(); + Type *DestTy = Ext.getType(); + unsigned NumSrcElts = SrcTy->getVectorNumElements(); + unsigned NumElts = Ext.getVectorOperandType()->getNumElements(); + if (NumSrcElts == NumElts) + if (Value *Elt = findScalarElement(X, ExtIndexC)) + return new BitCastInst(Elt, DestTy); + + // If the source elements are wider than the destination, try to shift and + // truncate a subset of scalar bits of an insert op. + if (NumSrcElts < NumElts) { + Value *Scalar; + uint64_t InsIndexC; + if (!match(X, m_InsertElement(m_Value(), m_Value(Scalar), + m_ConstantInt(InsIndexC)))) + return nullptr; + + // The extract must be from the subset of vector elements that we inserted + // into. Example: if we inserted element 1 of a <2 x i64> and we are + // extracting an i16 (narrowing ratio = 4), then this extract must be from 1 + // of elements 4-7 of the bitcasted vector. + unsigned NarrowingRatio = NumElts / NumSrcElts; + if (ExtIndexC / NarrowingRatio != InsIndexC) + return nullptr; + + // We are extracting part of the original scalar. How that scalar is + // inserted into the vector depends on the endian-ness. Example: + // Vector Byte Elt Index: 0 1 2 3 4 5 6 7 + // +--+--+--+--+--+--+--+--+ + // inselt <2 x i32> V, <i32> S, 1: |V0|V1|V2|V3|S0|S1|S2|S3| + // extelt <4 x i16> V', 3: | |S2|S3| + // +--+--+--+--+--+--+--+--+ + // If this is little-endian, S2|S3 are the MSB of the 32-bit 'S' value. + // If this is big-endian, S2|S3 are the LSB of the 32-bit 'S' value. + // In this example, we must right-shift little-endian. Big-endian is just a + // truncate. + unsigned Chunk = ExtIndexC % NarrowingRatio; + if (IsBigEndian) + Chunk = NarrowingRatio - 1 - Chunk; + + // Bail out if this is an FP vector to FP vector sequence. That would take + // more instructions than we started with unless there is no shift, and it + // may not be handled as well in the backend. + bool NeedSrcBitcast = SrcTy->getScalarType()->isFloatingPointTy(); + bool NeedDestBitcast = DestTy->isFloatingPointTy(); + if (NeedSrcBitcast && NeedDestBitcast) + return nullptr; + + unsigned SrcWidth = SrcTy->getScalarSizeInBits(); + unsigned DestWidth = DestTy->getPrimitiveSizeInBits(); + unsigned ShAmt = Chunk * DestWidth; + + // TODO: This limitation is more strict than necessary. We could sum the + // number of new instructions and subtract the number eliminated to know if + // we can proceed. + if (!X->hasOneUse() || !Ext.getVectorOperand()->hasOneUse()) + if (NeedSrcBitcast || NeedDestBitcast) + return nullptr; + + if (NeedSrcBitcast) { + Type *SrcIntTy = IntegerType::getIntNTy(Scalar->getContext(), SrcWidth); + Scalar = Builder.CreateBitCast(Scalar, SrcIntTy); + } + + if (ShAmt) { + // Bail out if we could end with more instructions than we started with. + if (!Ext.getVectorOperand()->hasOneUse()) + return nullptr; + Scalar = Builder.CreateLShr(Scalar, ShAmt); + } + + if (NeedDestBitcast) { + Type *DestIntTy = IntegerType::getIntNTy(Scalar->getContext(), DestWidth); + return new BitCastInst(Builder.CreateTrunc(Scalar, DestIntTy), DestTy); + } + return new TruncInst(Scalar, DestTy); + } + + return nullptr; +} + Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) { - if (Value *V = SimplifyExtractElementInst(EI.getVectorOperand(), - EI.getIndexOperand(), + Value *SrcVec = EI.getVectorOperand(); + Value *Index = EI.getIndexOperand(); + if (Value *V = SimplifyExtractElementInst(SrcVec, Index, SQ.getWithInstruction(&EI))) return replaceInstUsesWith(EI, V); - // If vector val is constant with all elements the same, replace EI with - // that element. We handle a known element # below. - if (Constant *C = dyn_cast<Constant>(EI.getOperand(0))) - if (cheapToScalarize(C, false)) - return replaceInstUsesWith(EI, C->getAggregateElement(0U)); - // If extracting a specified index from the vector, see if we can recursively // find a previously computed scalar that was inserted into the vector. - if (ConstantInt *IdxC = dyn_cast<ConstantInt>(EI.getOperand(1))) { - unsigned VectorWidth = EI.getVectorOperandType()->getNumElements(); + auto *IndexC = dyn_cast<ConstantInt>(Index); + if (IndexC) { + unsigned NumElts = EI.getVectorOperandType()->getNumElements(); // InstSimplify should handle cases where the index is invalid. - if (!IdxC->getValue().ule(VectorWidth)) + if (!IndexC->getValue().ule(NumElts)) return nullptr; - unsigned IndexVal = IdxC->getZExtValue(); - // This instruction only demands the single element from the input vector. // If the input vector has a single use, simplify it based on this use // property. - if (EI.getOperand(0)->hasOneUse() && VectorWidth != 1) { - APInt UndefElts(VectorWidth, 0); - APInt DemandedMask(VectorWidth, 0); - DemandedMask.setBit(IndexVal); - if (Value *V = SimplifyDemandedVectorElts(EI.getOperand(0), DemandedMask, + if (SrcVec->hasOneUse() && NumElts != 1) { + APInt UndefElts(NumElts, 0); + APInt DemandedElts(NumElts, 0); + DemandedElts.setBit(IndexC->getZExtValue()); + if (Value *V = SimplifyDemandedVectorElts(SrcVec, DemandedElts, UndefElts)) { EI.setOperand(0, V); return &EI; } } - // If this extractelement is directly using a bitcast from a vector of - // the same number of elements, see if we can find the source element from - // it. In this case, we will end up needing to bitcast the scalars. - if (BitCastInst *BCI = dyn_cast<BitCastInst>(EI.getOperand(0))) { - if (VectorType *VT = dyn_cast<VectorType>(BCI->getOperand(0)->getType())) - if (VT->getNumElements() == VectorWidth) - if (Value *Elt = findScalarElement(BCI->getOperand(0), IndexVal)) - return new BitCastInst(Elt, EI.getType()); - } + if (Instruction *I = foldBitcastExtElt(EI, Builder, DL.isBigEndian())) + return I; // If there's a vector PHI feeding a scalar use through this extractelement // instruction, try to scalarize the PHI. - if (PHINode *PN = dyn_cast<PHINode>(EI.getOperand(0))) { - Instruction *scalarPHI = scalarizePHI(EI, PN); - if (scalarPHI) - return scalarPHI; - } + if (auto *Phi = dyn_cast<PHINode>(SrcVec)) + if (Instruction *ScalarPHI = scalarizePHI(EI, Phi)) + return ScalarPHI; } - if (Instruction *I = dyn_cast<Instruction>(EI.getOperand(0))) { - // Push extractelement into predecessor operation if legal and - // profitable to do so. - if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) { - if (I->hasOneUse() && - cheapToScalarize(BO, isa<ConstantInt>(EI.getOperand(1)))) { - Value *newEI0 = - Builder.CreateExtractElement(BO->getOperand(0), EI.getOperand(1), - EI.getName()+".lhs"); - Value *newEI1 = - Builder.CreateExtractElement(BO->getOperand(1), EI.getOperand(1), - EI.getName()+".rhs"); - return BinaryOperator::CreateWithCopiedFlags(BO->getOpcode(), - newEI0, newEI1, BO); - } - } else if (InsertElementInst *IE = dyn_cast<InsertElementInst>(I)) { + BinaryOperator *BO; + if (match(SrcVec, m_BinOp(BO)) && cheapToScalarize(SrcVec, IndexC)) { + // extelt (binop X, Y), Index --> binop (extelt X, Index), (extelt Y, Index) + Value *X = BO->getOperand(0), *Y = BO->getOperand(1); + Value *E0 = Builder.CreateExtractElement(X, Index); + Value *E1 = Builder.CreateExtractElement(Y, Index); + return BinaryOperator::CreateWithCopiedFlags(BO->getOpcode(), E0, E1, BO); + } + + Value *X, *Y; + CmpInst::Predicate Pred; + if (match(SrcVec, m_Cmp(Pred, m_Value(X), m_Value(Y))) && + cheapToScalarize(SrcVec, IndexC)) { + // extelt (cmp X, Y), Index --> cmp (extelt X, Index), (extelt Y, Index) + Value *E0 = Builder.CreateExtractElement(X, Index); + Value *E1 = Builder.CreateExtractElement(Y, Index); + return CmpInst::Create(cast<CmpInst>(SrcVec)->getOpcode(), Pred, E0, E1); + } + + if (auto *I = dyn_cast<Instruction>(SrcVec)) { + if (auto *IE = dyn_cast<InsertElementInst>(I)) { // Extracting the inserted element? - if (IE->getOperand(2) == EI.getOperand(1)) + if (IE->getOperand(2) == Index) return replaceInstUsesWith(EI, IE->getOperand(1)); // If the inserted and extracted elements are constants, they must not // be the same value, extract from the pre-inserted value instead. - if (isa<Constant>(IE->getOperand(2)) && isa<Constant>(EI.getOperand(1))) { - Worklist.AddValue(EI.getOperand(0)); + if (isa<Constant>(IE->getOperand(2)) && IndexC) { + Worklist.AddValue(SrcVec); EI.setOperand(0, IE->getOperand(0)); return &EI; } - } else if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I)) { + } else if (auto *SVI = dyn_cast<ShuffleVectorInst>(I)) { // If this is extracting an element from a shufflevector, figure out where // it came from and extract from the appropriate input element instead. - if (ConstantInt *Elt = dyn_cast<ConstantInt>(EI.getOperand(1))) { + if (auto *Elt = dyn_cast<ConstantInt>(Index)) { int SrcIdx = SVI->getMaskValue(Elt->getZExtValue()); Value *Src; unsigned LHSWidth = @@ -270,13 +348,12 @@ Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) { ConstantInt::get(Int32Ty, SrcIdx, false)); } - } else if (CastInst *CI = dyn_cast<CastInst>(I)) { + } else if (auto *CI = dyn_cast<CastInst>(I)) { // Canonicalize extractelement(cast) -> cast(extractelement). // Bitcasts can change the number of vector elements, and they cost // nothing. if (CI->hasOneUse() && (CI->getOpcode() != Instruction::BitCast)) { - Value *EE = Builder.CreateExtractElement(CI->getOperand(0), - EI.getIndexOperand()); + Value *EE = Builder.CreateExtractElement(CI->getOperand(0), Index); Worklist.AddValue(EE); return CastInst::Create(CI->getOpcode(), EE, EI.getType()); } @@ -791,43 +868,62 @@ Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) { if (isa<UndefValue>(ScalarOp) || isa<UndefValue>(IdxOp)) replaceInstUsesWith(IE, VecOp); - // If the inserted element was extracted from some other vector, and if the - // indexes are constant, try to turn this into a shufflevector operation. - if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) { - if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) { - unsigned NumInsertVectorElts = IE.getType()->getNumElements(); - unsigned NumExtractVectorElts = - EI->getOperand(0)->getType()->getVectorNumElements(); - unsigned ExtractedIdx = - cast<ConstantInt>(EI->getOperand(1))->getZExtValue(); - unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue(); + // If the inserted element was extracted from some other vector and both + // indexes are constant, 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 (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 (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); - // If we are extracting a value from a vector, then inserting it right - // back into the same place, just use the input vector. - if (EI->getOperand(0) == VecOp && ExtractedIdx == InsertedIdx) - return replaceInstUsesWith(IE, VecOp); + // 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 + // on this instruction and its operands, but that may not work currently. + // + // Here, we are trying to avoid creating shuffles before reaching + // the end of a chain of extract-insert pairs. This is complicated because + // we do not generally form arbitrary shuffle masks in instcombine + // (because those may codegen poorly), but collectShuffleElements() does + // exactly that. + // + // The rules for determining what is an acceptable target-independent + // shuffle mask are fuzzy because they evolve based on the backend's + // capabilities and real-world impact. + auto isShuffleRootCandidate = [](InsertElementInst &Insert) { + if (!Insert.hasOneUse()) + return true; + auto *InsertUser = dyn_cast<InsertElementInst>(Insert.user_back()); + if (!InsertUser) + return true; + return false; + }; - // If this insertelement isn't used by some other insertelement, turn it - // (and any insertelements it points to), into one big shuffle. - if (!IE.hasOneUse() || !isa<InsertElementInst>(IE.user_back())) { - SmallVector<Constant*, 16> Mask; - ShuffleOps LR = collectShuffleElements(&IE, Mask, nullptr, *this); + // Try to form a shuffle from a chain of extract-insert ops. + if (isShuffleRootCandidate(IE)) { + SmallVector<Constant*, 16> Mask; + ShuffleOps LR = collectShuffleElements(&IE, Mask, nullptr, *this); - // The proposed shuffle may be trivial, in which case we shouldn't - // perform the combine. - if (LR.first != &IE && LR.second != &IE) { - // We now have a shuffle of LHS, RHS, Mask. - if (LR.second == nullptr) - LR.second = UndefValue::get(LR.first->getType()); - return new ShuffleVectorInst(LR.first, LR.second, - ConstantVector::get(Mask)); - } + // The proposed shuffle may be trivial, in which case we shouldn't + // perform the combine. + if (LR.first != &IE && LR.second != &IE) { + // We now have a shuffle of LHS, RHS, Mask. + if (LR.second == nullptr) + LR.second = UndefValue::get(LR.first->getType()); + return new ShuffleVectorInst(LR.first, LR.second, + ConstantVector::get(Mask)); } } } @@ -857,7 +953,7 @@ Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) { /// Return true if we can evaluate the specified expression tree if the vector /// elements were shuffled in a different order. -static bool CanEvaluateShuffled(Value *V, ArrayRef<int> Mask, +static bool canEvaluateShuffled(Value *V, ArrayRef<int> Mask, unsigned Depth = 5) { // We can always reorder the elements of a constant. if (isa<Constant>(V)) @@ -904,8 +1000,15 @@ static bool CanEvaluateShuffled(Value *V, ArrayRef<int> Mask, case Instruction::FPTrunc: case Instruction::FPExt: case Instruction::GetElementPtr: { + // Bail out if we would create longer vector ops. We could allow creating + // longer vector ops, but that may result in more expensive codegen. We + // would also need to limit the transform to avoid undefined behavior for + // integer div/rem. + Type *ITy = I->getType(); + if (ITy->isVectorTy() && Mask.size() > ITy->getVectorNumElements()) + return false; for (Value *Operand : I->operands()) { - if (!CanEvaluateShuffled(Operand, Mask, Depth-1)) + if (!canEvaluateShuffled(Operand, Mask, Depth - 1)) return false; } return true; @@ -925,7 +1028,7 @@ static bool CanEvaluateShuffled(Value *V, ArrayRef<int> Mask, SeenOnce = true; } } - return CanEvaluateShuffled(I->getOperand(0), Mask, Depth-1); + return canEvaluateShuffled(I->getOperand(0), Mask, Depth - 1); } } return false; @@ -1009,12 +1112,12 @@ static Value *buildNew(Instruction *I, ArrayRef<Value*> NewOps) { llvm_unreachable("failed to rebuild vector instructions"); } -Value * -InstCombiner::EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask) { +static Value *evaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask) { // Mask.size() does not need to be equal to the number of vector elements. assert(V->getType()->isVectorTy() && "can't reorder non-vector elements"); Type *EltTy = V->getType()->getScalarType(); + Type *I32Ty = IntegerType::getInt32Ty(V->getContext()); if (isa<UndefValue>(V)) return UndefValue::get(VectorType::get(EltTy, Mask.size())); @@ -1025,9 +1128,9 @@ InstCombiner::EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask) { SmallVector<Constant *, 16> MaskValues; for (int i = 0, e = Mask.size(); i != e; ++i) { if (Mask[i] == -1) - MaskValues.push_back(UndefValue::get(Builder.getInt32Ty())); + MaskValues.push_back(UndefValue::get(I32Ty)); else - MaskValues.push_back(Builder.getInt32(Mask[i])); + MaskValues.push_back(ConstantInt::get(I32Ty, Mask[i])); } return ConstantExpr::getShuffleVector(C, UndefValue::get(C->getType()), ConstantVector::get(MaskValues)); @@ -1069,7 +1172,7 @@ InstCombiner::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 = evaluateInDifferentElementOrder(I->getOperand(i), Mask); NewOps.push_back(V); NeedsRebuild |= (V != I->getOperand(i)); } @@ -1096,11 +1199,11 @@ InstCombiner::EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask) { // If element is not in Mask, no need to handle the operand 1 (element to // be inserted). Just evaluate values in operand 0 according to Mask. if (!Found) - return EvaluateInDifferentElementOrder(I->getOperand(0), Mask); + return evaluateInDifferentElementOrder(I->getOperand(0), Mask); - Value *V = EvaluateInDifferentElementOrder(I->getOperand(0), Mask); + Value *V = evaluateInDifferentElementOrder(I->getOperand(0), Mask); return InsertElementInst::Create(V, I->getOperand(1), - Builder.getInt32(Index), "", I); + ConstantInt::get(I32Ty, Index), "", I); } } llvm_unreachable("failed to reorder elements of vector instruction!"); @@ -1350,12 +1453,144 @@ static Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf, return NewBO; } +/// Match a shuffle-select-shuffle pattern where the shuffles are widening and +/// narrowing (concatenating with undef and extracting back to the original +/// length). This allows replacing the wide select with a narrow select. +static Instruction *narrowVectorSelect(ShuffleVectorInst &Shuf, + InstCombiner::BuilderTy &Builder) { + // This must be a narrowing identity shuffle. It extracts the 1st N elements + // of the 1st vector operand of a shuffle. + if (!match(Shuf.getOperand(1), m_Undef()) || !Shuf.isIdentityWithExtract()) + return nullptr; + + // The vector being shuffled must be a vector select that we can eliminate. + // TODO: The one-use requirement could be eased if X and/or Y are constants. + Value *Cond, *X, *Y; + if (!match(Shuf.getOperand(0), + m_OneUse(m_Select(m_Value(Cond), m_Value(X), m_Value(Y))))) + return nullptr; + + // We need a narrow condition value. It must be extended with undef elements + // and have the same number of elements as this shuffle. + unsigned NarrowNumElts = Shuf.getType()->getVectorNumElements(); + Value *NarrowCond; + if (!match(Cond, m_OneUse(m_ShuffleVector(m_Value(NarrowCond), m_Undef(), + m_Constant()))) || + NarrowCond->getType()->getVectorNumElements() != NarrowNumElts || + !cast<ShuffleVectorInst>(Cond)->isIdentityWithPadding()) + return nullptr; + + // shuf (sel (shuf NarrowCond, undef, WideMask), X, Y), undef, NarrowMask) --> + // sel NarrowCond, (shuf X, undef, NarrowMask), (shuf Y, undef, NarrowMask) + Value *Undef = UndefValue::get(X->getType()); + Value *NarrowX = Builder.CreateShuffleVector(X, Undef, Shuf.getMask()); + Value *NarrowY = Builder.CreateShuffleVector(Y, Undef, Shuf.getMask()); + return SelectInst::Create(NarrowCond, NarrowX, NarrowY); +} + +/// Try to combine 2 shuffles into 1 shuffle by concatenating a shuffle mask. +static Instruction *foldIdentityExtractShuffle(ShuffleVectorInst &Shuf) { + Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1); + if (!Shuf.isIdentityWithExtract() || !isa<UndefValue>(Op1)) + return nullptr; + + Value *X, *Y; + Constant *Mask; + if (!match(Op0, m_ShuffleVector(m_Value(X), m_Value(Y), m_Constant(Mask)))) + return nullptr; + + // We are extracting a subvector from a shuffle. Remove excess elements from + // the 1st shuffle mask to eliminate the extract. + // + // This transform is conservatively limited to identity extracts because we do + // not allow arbitrary shuffle mask creation as a target-independent transform + // (because we can't guarantee that will lower efficiently). + // + // If the extracting shuffle has an undef mask element, it transfers to the + // new shuffle mask. Otherwise, copy the original mask element. Example: + // shuf (shuf X, Y, <C0, C1, C2, undef, C4>), undef, <0, undef, 2, 3> --> + // shuf X, Y, <C0, undef, C2, undef> + unsigned NumElts = Shuf.getType()->getVectorNumElements(); + SmallVector<Constant *, 16> NewMask(NumElts); + assert(NumElts < Mask->getType()->getVectorNumElements() && + "Identity with extract must have less elements than its inputs"); + + for (unsigned i = 0; i != NumElts; ++i) { + Constant *ExtractMaskElt = Shuf.getMask()->getAggregateElement(i); + Constant *MaskElt = Mask->getAggregateElement(i); + NewMask[i] = isa<UndefValue>(ExtractMaskElt) ? ExtractMaskElt : MaskElt; + } + return new ShuffleVectorInst(X, Y, ConstantVector::get(NewMask)); +} + +/// Try to replace a shuffle with an insertelement. +static Instruction *foldShuffleWithInsert(ShuffleVectorInst &Shuf) { + Value *V0 = Shuf.getOperand(0), *V1 = Shuf.getOperand(1); + SmallVector<int, 16> Mask = Shuf.getShuffleMask(); + + // The shuffle must not change vector sizes. + // TODO: This restriction could be removed if the insert has only one use + // (because the transform would require a new length-changing shuffle). + int NumElts = Mask.size(); + if (NumElts != (int)(V0->getType()->getVectorNumElements())) + return nullptr; + + // shuffle (insert ?, Scalar, IndexC), V1, Mask --> insert V1, Scalar, IndexC' + auto isShufflingScalarIntoOp1 = [&](Value *&Scalar, ConstantInt *&IndexC) { + // We need an insertelement with a constant index. + if (!match(V0, m_InsertElement(m_Value(), m_Value(Scalar), + m_ConstantInt(IndexC)))) + return false; + + // Test the shuffle mask to see if it splices the inserted scalar into the + // operand 1 vector of the shuffle. + int NewInsIndex = -1; + for (int i = 0; i != NumElts; ++i) { + // Ignore undef mask elements. + if (Mask[i] == -1) + continue; + + // The shuffle takes elements of operand 1 without lane changes. + if (Mask[i] == NumElts + i) + continue; + + // The shuffle must choose the inserted scalar exactly once. + if (NewInsIndex != -1 || Mask[i] != IndexC->getSExtValue()) + return false; + + // The shuffle is placing the inserted scalar into element i. + NewInsIndex = i; + } + + assert(NewInsIndex != -1 && "Did not fold shuffle with unused operand?"); + + // Index is updated to the potentially translated insertion lane. + IndexC = ConstantInt::get(IndexC->getType(), NewInsIndex); + return true; + }; + + // If the shuffle is unnecessary, insert the scalar operand directly into + // operand 1 of the shuffle. Example: + // shuffle (insert ?, S, 1), V1, <1, 5, 6, 7> --> insert V1, S, 0 + Value *Scalar; + ConstantInt *IndexC; + if (isShufflingScalarIntoOp1(Scalar, IndexC)) + return InsertElementInst::Create(V1, Scalar, IndexC); + + // Try again after commuting shuffle. Example: + // shuffle V0, (insert ?, S, 0), <0, 1, 2, 4> --> + // shuffle (insert ?, S, 0), V0, <4, 5, 6, 0> --> insert V0, S, 3 + std::swap(V0, V1); + ShuffleVectorInst::commuteShuffleMask(Mask, NumElts); + if (isShufflingScalarIntoOp1(Scalar, IndexC)) + return InsertElementInst::Create(V1, Scalar, IndexC); + + return nullptr; +} + Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) { Value *LHS = SVI.getOperand(0); Value *RHS = SVI.getOperand(1); - SmallVector<int, 16> Mask = SVI.getShuffleMask(); - Type *Int32Ty = Type::getInt32Ty(SVI.getContext()); - if (auto *V = SimplifyShuffleVectorInst( LHS, RHS, SVI.getMask(), SVI.getType(), SQ.getWithInstruction(&SVI))) return replaceInstUsesWith(SVI, V); @@ -1363,9 +1598,10 @@ Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) { if (Instruction *I = foldSelectShuffle(SVI, Builder, DL)) return I; - bool MadeChange = false; - unsigned VWidth = SVI.getType()->getVectorNumElements(); + if (Instruction *I = narrowVectorSelect(SVI, Builder)) + return I; + unsigned VWidth = SVI.getType()->getVectorNumElements(); APInt UndefElts(VWidth, 0); APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth)); if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) { @@ -1374,18 +1610,22 @@ Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) { 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; + + 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)) { - if (isa<UndefValue>(LHS) && LHS == RHS) { - // shuffle(undef,undef,mask) -> undef. - Value *Result = (VWidth == LHSWidth) - ? LHS : UndefValue::get(SVI.getType()); - return replaceInstUsesWith(SVI, Result); - } - // Remap any references to RHS to use LHS. SmallVector<Constant*, 16> Elts; for (unsigned i = 0, e = LHSWidth; i != VWidth; ++i) { @@ -1421,8 +1661,8 @@ Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) { if (isRHSID) return replaceInstUsesWith(SVI, RHS); } - if (isa<UndefValue>(RHS) && CanEvaluateShuffled(LHS, Mask)) { - Value *V = EvaluateInDifferentElementOrder(LHS, Mask); + if (isa<UndefValue>(RHS) && canEvaluateShuffled(LHS, Mask)) { + Value *V = evaluateInDifferentElementOrder(LHS, Mask); return replaceInstUsesWith(SVI, V); } diff --git a/lib/Transforms/InstCombine/InstructionCombining.cpp b/lib/Transforms/InstCombine/InstructionCombining.cpp index cff0d5447290..be7d43bbcf2c 100644 --- a/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -57,7 +57,6 @@ #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/Analysis/TargetFolder.h" #include "llvm/Analysis/TargetLibraryInfo.h" -#include "llvm/Transforms/Utils/Local.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" @@ -97,6 +96,7 @@ #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/InstCombine/InstCombine.h" #include "llvm/Transforms/InstCombine/InstCombineWorklist.h" +#include "llvm/Transforms/Utils/Local.h" #include <algorithm> #include <cassert> #include <cstdint> @@ -120,6 +120,10 @@ DEBUG_COUNTER(VisitCounter, "instcombine-visit", "Controls which instructions are visited"); static cl::opt<bool> +EnableCodeSinking("instcombine-code-sinking", cl::desc("Enable code sinking"), + cl::init(true)); + +static cl::opt<bool> EnableExpensiveCombines("expensive-combines", cl::desc("Enable expensive instruction combines")); @@ -179,7 +183,10 @@ bool InstCombiner::shouldChangeType(unsigned FromWidth, /// a fundamental type in IR, and there are many specialized optimizations for /// i1 types. bool InstCombiner::shouldChangeType(Type *From, Type *To) const { - assert(From->isIntegerTy() && To->isIntegerTy()); + // TODO: This could be extended to allow vectors. Datalayout changes might be + // needed to properly support that. + if (!From->isIntegerTy() || !To->isIntegerTy()) + return false; unsigned FromWidth = From->getPrimitiveSizeInBits(); unsigned ToWidth = To->getPrimitiveSizeInBits(); @@ -747,8 +754,9 @@ Value *InstCombiner::SimplifySelectsFeedingBinaryOp(BinaryOperator &I, /// Given a 'sub' instruction, return the RHS of the instruction if the LHS is a /// constant zero (which is the 'negate' form). Value *InstCombiner::dyn_castNegVal(Value *V) const { - if (BinaryOperator::isNeg(V)) - return BinaryOperator::getNegArgument(V); + Value *NegV; + if (match(V, m_Neg(m_Value(NegV)))) + return NegV; // Constants can be considered to be negated values if they can be folded. if (ConstantInt *C = dyn_cast<ConstantInt>(V)) @@ -1351,22 +1359,46 @@ Value *InstCombiner::Descale(Value *Val, APInt Scale, bool &NoSignedWrap) { } while (true); } -Instruction *InstCombiner::foldShuffledBinop(BinaryOperator &Inst) { +Instruction *InstCombiner::foldVectorBinop(BinaryOperator &Inst) { if (!Inst.getType()->isVectorTy()) return nullptr; + BinaryOperator::BinaryOps Opcode = Inst.getOpcode(); + unsigned NumElts = cast<VectorType>(Inst.getType())->getNumElements(); + Value *LHS = Inst.getOperand(0), *RHS = Inst.getOperand(1); + assert(cast<VectorType>(LHS->getType())->getNumElements() == NumElts); + assert(cast<VectorType>(RHS->getType())->getNumElements() == NumElts); + + // If both operands of the binop are vector concatenations, then perform the + // narrow binop on each pair of the source operands followed by concatenation + // of the results. + Value *L0, *L1, *R0, *R1; + Constant *Mask; + 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()) { + // 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. + // TODO: We could ease the mask requirement to allow different undef lanes, + // but that requires an analysis of the binop-with-undef output value. + Value *NewBO0 = Builder.CreateBinOp(Opcode, L0, R0); + if (auto *BO = dyn_cast<BinaryOperator>(NewBO0)) + BO->copyIRFlags(&Inst); + Value *NewBO1 = Builder.CreateBinOp(Opcode, L1, R1); + if (auto *BO = dyn_cast<BinaryOperator>(NewBO1)) + BO->copyIRFlags(&Inst); + return new ShuffleVectorInst(NewBO0, NewBO1, Mask); + } + // It may not be safe to reorder shuffles and things like div, urem, etc. // because we may trap when executing those ops on unknown vector elements. // See PR20059. if (!isSafeToSpeculativelyExecute(&Inst)) return nullptr; - unsigned VWidth = cast<VectorType>(Inst.getType())->getNumElements(); - Value *LHS = Inst.getOperand(0), *RHS = Inst.getOperand(1); - assert(cast<VectorType>(LHS->getType())->getNumElements() == VWidth); - assert(cast<VectorType>(RHS->getType())->getNumElements() == VWidth); - auto createBinOpShuffle = [&](Value *X, Value *Y, Constant *M) { - Value *XY = Builder.CreateBinOp(Inst.getOpcode(), X, Y); + Value *XY = Builder.CreateBinOp(Opcode, X, Y); if (auto *BO = dyn_cast<BinaryOperator>(XY)) BO->copyIRFlags(&Inst); return new ShuffleVectorInst(XY, UndefValue::get(XY->getType()), M); @@ -1375,7 +1407,6 @@ Instruction *InstCombiner::foldShuffledBinop(BinaryOperator &Inst) { // If both arguments of the binary operation are shuffles that use the same // mask and shuffle within a single vector, move the shuffle after the binop. Value *V1, *V2; - Constant *Mask; if (match(LHS, m_ShuffleVector(m_Value(V1), m_Undef(), m_Constant(Mask))) && match(RHS, m_ShuffleVector(m_Value(V2), m_Undef(), m_Specific(Mask))) && V1->getType() == V2->getType() && @@ -1393,42 +1424,69 @@ Instruction *InstCombiner::foldShuffledBinop(BinaryOperator &Inst) { if (match(&Inst, m_c_BinOp( m_OneUse(m_ShuffleVector(m_Value(V1), m_Undef(), m_Constant(Mask))), m_Constant(C))) && - V1->getType() == Inst.getType()) { + V1->getType()->getVectorNumElements() <= NumElts) { + assert(Inst.getType()->getScalarType() == V1->getType()->getScalarType() && + "Shuffle should not change scalar type"); + // Find constant NewC that has property: // shuffle(NewC, ShMask) = C // If such constant does not exist (example: ShMask=<0,0> and C=<1,2>) // reorder is not possible. A 1-to-1 mapping is not required. Example: // ShMask = <1,1,2,2> and C = <5,5,6,6> --> NewC = <undef,5,6,undef> + bool ConstOp1 = isa<Constant>(RHS); SmallVector<int, 16> ShMask; ShuffleVectorInst::getShuffleMask(Mask, ShMask); - SmallVector<Constant *, 16> - NewVecC(VWidth, UndefValue::get(C->getType()->getScalarType())); + unsigned SrcVecNumElts = V1->getType()->getVectorNumElements(); + UndefValue *UndefScalar = UndefValue::get(C->getType()->getScalarType()); + SmallVector<Constant *, 16> NewVecC(SrcVecNumElts, UndefScalar); bool MayChange = true; - for (unsigned I = 0; I < VWidth; ++I) { + for (unsigned I = 0; I < NumElts; ++I) { + Constant *CElt = C->getAggregateElement(I); if (ShMask[I] >= 0) { - assert(ShMask[I] < (int)VWidth); - Constant *CElt = C->getAggregateElement(I); + assert(ShMask[I] < (int)NumElts && "Not expecting narrowing shuffle"); Constant *NewCElt = NewVecC[ShMask[I]]; - if (!CElt || (!isa<UndefValue>(NewCElt) && NewCElt != CElt)) { + // Bail out if: + // 1. The constant vector contains a constant expression. + // 2. The shuffle needs an element of the constant vector that can't + // be mapped to a new constant vector. + // 3. This is a widening shuffle that copies elements of V1 into the + // extended elements (extending with undef is allowed). + if (!CElt || (!isa<UndefValue>(NewCElt) && NewCElt != CElt) || + I >= SrcVecNumElts) { MayChange = false; break; } NewVecC[ShMask[I]] = CElt; } + // If this is a widening shuffle, we must be able to extend with undef + // elements. If the original binop does not produce an undef in the high + // lanes, then this transform is not safe. + // TODO: We could shuffle those non-undef constant values into the + // result by using a constant vector (rather than an undef vector) + // as operand 1 of the new binop, but that might be too aggressive + // for target-independent shuffle creation. + if (I >= SrcVecNumElts) { + Constant *MaybeUndef = + ConstOp1 ? ConstantExpr::get(Opcode, UndefScalar, CElt) + : ConstantExpr::get(Opcode, CElt, UndefScalar); + if (!isa<UndefValue>(MaybeUndef)) { + MayChange = false; + break; + } + } } if (MayChange) { Constant *NewC = ConstantVector::get(NewVecC); // It may not be safe to execute a binop on a vector with undef elements // because the entire instruction can be folded to undef or create poison // that did not exist in the original code. - bool ConstOp1 = isa<Constant>(Inst.getOperand(1)); if (Inst.isIntDivRem() || (Inst.isShift() && ConstOp1)) - NewC = getSafeVectorConstantForBinop(Inst.getOpcode(), NewC, ConstOp1); + NewC = getSafeVectorConstantForBinop(Opcode, NewC, ConstOp1); // Op(shuffle(V1, Mask), C) -> shuffle(Op(V1, NewC), Mask) // Op(C, shuffle(V1, Mask)) -> shuffle(Op(NewC, V1), Mask) - Value *NewLHS = isa<Constant>(LHS) ? NewC : V1; - Value *NewRHS = isa<Constant>(LHS) ? V1 : NewC; + Value *NewLHS = ConstOp1 ? V1 : NewC; + Value *NewRHS = ConstOp1 ? NewC : V1; return createBinOpShuffle(NewLHS, NewRHS, Mask); } } @@ -1436,6 +1494,62 @@ Instruction *InstCombiner::foldShuffledBinop(BinaryOperator &Inst) { return nullptr; } +/// Try to narrow the width of a binop if at least 1 operand is an extend of +/// of a value. This requires a potentially expensive known bits check to make +/// sure the narrow op does not overflow. +Instruction *InstCombiner::narrowMathIfNoOverflow(BinaryOperator &BO) { + // We need at least one extended operand. + Value *Op0 = BO.getOperand(0), *Op1 = BO.getOperand(1); + + // If this is a sub, we swap the operands since we always want an extension + // on the RHS. The LHS can be an extension or a constant. + if (BO.getOpcode() == Instruction::Sub) + std::swap(Op0, Op1); + + Value *X; + bool IsSext = match(Op0, m_SExt(m_Value(X))); + if (!IsSext && !match(Op0, m_ZExt(m_Value(X)))) + return nullptr; + + // If both operands are the same extension from the same source type and we + // can eliminate at least one (hasOneUse), this might work. + CastInst::CastOps CastOpc = IsSext ? Instruction::SExt : Instruction::ZExt; + Value *Y; + if (!(match(Op1, m_ZExtOrSExt(m_Value(Y))) && X->getType() == Y->getType() && + cast<Operator>(Op1)->getOpcode() == CastOpc && + (Op0->hasOneUse() || Op1->hasOneUse()))) { + // If that did not match, see if we have a suitable constant operand. + // Truncating and extending must produce the same constant. + Constant *WideC; + if (!Op0->hasOneUse() || !match(Op1, m_Constant(WideC))) + return nullptr; + Constant *NarrowC = ConstantExpr::getTrunc(WideC, X->getType()); + if (ConstantExpr::getCast(CastOpc, NarrowC, BO.getType()) != WideC) + return nullptr; + Y = NarrowC; + } + + // Swap back now that we found our operands. + if (BO.getOpcode() == Instruction::Sub) + std::swap(X, Y); + + // Both operands have narrow versions. Last step: the math must not overflow + // in the narrow width. + if (!willNotOverflow(BO.getOpcode(), X, Y, BO, IsSext)) + return nullptr; + + // bo (ext X), (ext Y) --> ext (bo X, Y) + // bo (ext X), C --> ext (bo X, C') + Value *NarrowBO = Builder.CreateBinOp(BO.getOpcode(), X, Y, "narrow"); + if (auto *NewBinOp = dyn_cast<BinaryOperator>(NarrowBO)) { + if (IsSext) + NewBinOp->setHasNoSignedWrap(); + else + NewBinOp->setHasNoUnsignedWrap(); + } + return CastInst::Create(CastOpc, NarrowBO, BO.getType()); +} + Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { SmallVector<Value*, 8> Ops(GEP.op_begin(), GEP.op_end()); Type *GEPType = GEP.getType(); @@ -1963,9 +2077,22 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { areMatchingArrayAndVecTypes(GEPEltType, SrcEltType)) || (GEPEltType->isVectorTy() && SrcEltType->isArrayTy() && areMatchingArrayAndVecTypes(SrcEltType, GEPEltType)))) { - GEP.setOperand(0, SrcOp); - GEP.setSourceElementType(SrcEltType); - return &GEP; + + // Create a new GEP here, as using `setOperand()` followed by + // `setSourceElementType()` won't actually update the type of the + // existing GEP Value. Causing issues if this Value is accessed when + // constructing an AddrSpaceCastInst + Value *NGEP = + GEP.isInBounds() + ? Builder.CreateInBoundsGEP(nullptr, SrcOp, {Ops[1], Ops[2]}) + : Builder.CreateGEP(nullptr, SrcOp, {Ops[1], Ops[2]}); + NGEP->takeName(&GEP); + + // Preserve GEP address space to satisfy users + if (NGEP->getType()->getPointerAddressSpace() != GEP.getAddressSpace()) + return new AddrSpaceCastInst(NGEP, GEPType); + + return replaceInstUsesWith(GEP, NGEP); } // See if we can simplify: @@ -2137,14 +2264,21 @@ static bool isAllocSiteRemovable(Instruction *AI, } Instruction *InstCombiner::visitAllocSite(Instruction &MI) { - // If we have a malloc call which is only used in any amount of comparisons - // to null and free calls, delete the calls and replace the comparisons with - // true or false as appropriate. + // If we have a malloc call which is only used in any amount of comparisons to + // null and free calls, delete the calls and replace the comparisons with true + // or false as appropriate. + + // This is based on the principle that we can substitute our own allocation + // function (which will never return null) rather than knowledge of the + // specific function being called. In some sense this can change the permitted + // outputs of a program (when we convert a malloc to an alloca, the fact that + // the allocation is now on the stack is potentially visible, for example), + // but we believe in a permissible manner. SmallVector<WeakTrackingVH, 64> Users; // If we are removing an alloca with a dbg.declare, insert dbg.value calls // before each store. - TinyPtrVector<DbgInfoIntrinsic *> DIIs; + TinyPtrVector<DbgVariableIntrinsic *> DIIs; std::unique_ptr<DIBuilder> DIB; if (isa<AllocaInst>(MI)) { DIIs = FindDbgAddrUses(&MI); @@ -2215,14 +2349,14 @@ Instruction *InstCombiner::visitAllocSite(Instruction &MI) { /// The move is performed only if the block containing the call to free /// will be removed, i.e.: /// 1. it has only one predecessor P, and P has two successors -/// 2. it contains the call and an unconditional branch +/// 2. it contains the call, noops, and an unconditional branch /// 3. its successor is the same as its predecessor's successor /// /// The profitability is out-of concern here and this function should /// be called only if the caller knows this transformation would be /// profitable (e.g., for code size). -static Instruction * -tryToMoveFreeBeforeNullTest(CallInst &FI) { +static Instruction *tryToMoveFreeBeforeNullTest(CallInst &FI, + const DataLayout &DL) { Value *Op = FI.getArgOperand(0); BasicBlock *FreeInstrBB = FI.getParent(); BasicBlock *PredBB = FreeInstrBB->getSinglePredecessor(); @@ -2235,20 +2369,34 @@ tryToMoveFreeBeforeNullTest(CallInst &FI) { return nullptr; // Validate constraint #2: Does this block contains only the call to - // free and an unconditional branch? - // FIXME: We could check if we can speculate everything in the - // predecessor block - if (FreeInstrBB->size() != 2) - return nullptr; + // free, noops, and an unconditional branch? BasicBlock *SuccBB; - if (!match(FreeInstrBB->getTerminator(), m_UnconditionalBr(SuccBB))) + Instruction *FreeInstrBBTerminator = FreeInstrBB->getTerminator(); + if (!match(FreeInstrBBTerminator, m_UnconditionalBr(SuccBB))) return nullptr; + // If there are only 2 instructions in the block, at this point, + // this is the call to free and unconditional. + // If there are more than 2 instructions, check that they are noops + // i.e., they won't hurt the performance of the generated code. + if (FreeInstrBB->size() != 2) { + for (const Instruction &Inst : *FreeInstrBB) { + if (&Inst == &FI || &Inst == FreeInstrBBTerminator) + continue; + auto *Cast = dyn_cast<CastInst>(&Inst); + if (!Cast || !Cast->isNoopCast(DL)) + return nullptr; + } + } // Validate the rest of constraint #1 by matching on the pred branch. - TerminatorInst *TI = PredBB->getTerminator(); + Instruction *TI = PredBB->getTerminator(); BasicBlock *TrueBB, *FalseBB; ICmpInst::Predicate Pred; - if (!match(TI, m_Br(m_ICmp(Pred, m_Specific(Op), m_Zero()), TrueBB, FalseBB))) + if (!match(TI, m_Br(m_ICmp(Pred, + m_CombineOr(m_Specific(Op), + m_Specific(Op->stripPointerCasts())), + m_Zero()), + TrueBB, FalseBB))) return nullptr; if (Pred != ICmpInst::ICMP_EQ && Pred != ICmpInst::ICMP_NE) return nullptr; @@ -2259,7 +2407,17 @@ tryToMoveFreeBeforeNullTest(CallInst &FI) { assert(FreeInstrBB == (Pred == ICmpInst::ICMP_EQ ? FalseBB : TrueBB) && "Broken CFG: missing edge from predecessor to successor"); - FI.moveBefore(TI); + // At this point, we know that everything in FreeInstrBB can be moved + // before TI. + for (BasicBlock::iterator It = FreeInstrBB->begin(), End = FreeInstrBB->end(); + It != End;) { + Instruction &Instr = *It++; + if (&Instr == FreeInstrBBTerminator) + break; + Instr.moveBefore(TI); + } + assert(FreeInstrBB->size() == 1 && + "Only the branch instruction should remain"); return &FI; } @@ -2286,7 +2444,7 @@ Instruction *InstCombiner::visitFree(CallInst &FI) { // into // free(foo); if (MinimizeSize) - if (Instruction *I = tryToMoveFreeBeforeNullTest(FI)) + if (Instruction *I = tryToMoveFreeBeforeNullTest(FI, DL)) return I; return nullptr; @@ -2379,9 +2537,11 @@ Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) { unsigned NewWidth = Known.getBitWidth() - std::max(LeadingKnownZeros, LeadingKnownOnes); // Shrink the condition operand if the new type is smaller than the old type. - // This may produce a non-standard type for the switch, but that's ok because - // the backend should extend back to a legal type for the target. - if (NewWidth > 0 && NewWidth < Known.getBitWidth()) { + // But do not shrink to a non-standard type, because backend can't generate + // good code for that yet. + // TODO: We can make it aggressive again after fixing PR39569. + if (NewWidth > 0 && NewWidth < Known.getBitWidth() && + shouldChangeType(Known.getBitWidth(), NewWidth)) { IntegerType *Ty = IntegerType::get(SI.getContext(), NewWidth); Builder.SetInsertPoint(&SI); Value *NewCond = Builder.CreateTrunc(Cond, Ty, "trunc"); @@ -2902,7 +3062,7 @@ static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) { // Cannot move control-flow-involving, volatile loads, vaarg, etc. if (isa<PHINode>(I) || I->isEHPad() || I->mayHaveSideEffects() || - isa<TerminatorInst>(I)) + I->isTerminator()) return false; // Do not sink alloca instructions out of the entry block. @@ -2934,7 +3094,7 @@ static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) { // Also sink all related debug uses from the source basic block. Otherwise we // get debug use before the def. - SmallVector<DbgInfoIntrinsic *, 1> DbgUsers; + SmallVector<DbgVariableIntrinsic *, 1> DbgUsers; findDbgUsers(DbgUsers, I); for (auto *DII : DbgUsers) { if (DII->getParent() == SrcBlock) { @@ -3000,7 +3160,7 @@ bool InstCombiner::run() { } // See if we can trivially sink this instruction to a successor basic block. - if (I->hasOneUse()) { + if (EnableCodeSinking && I->hasOneUse()) { BasicBlock *BB = I->getParent(); Instruction *UserInst = cast<Instruction>(*I->user_begin()); BasicBlock *UserParent; @@ -3183,7 +3343,7 @@ static bool AddReachableCodeToWorklist(BasicBlock *BB, const DataLayout &DL, // Recursively visit successors. If this is a branch or switch on a // constant, only visit the reachable successor. - TerminatorInst *TI = BB->getTerminator(); + Instruction *TI = BB->getTerminator(); if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { if (BI->isConditional() && isa<ConstantInt>(BI->getCondition())) { bool CondVal = cast<ConstantInt>(BI->getCondition())->getZExtValue(); @@ -3198,7 +3358,7 @@ static bool AddReachableCodeToWorklist(BasicBlock *BB, const DataLayout &DL, } } - for (BasicBlock *SuccBB : TI->successors()) + for (BasicBlock *SuccBB : successors(TI)) Worklist.push_back(SuccBB); } while (!Worklist.empty()); |
