summaryrefslogtreecommitdiff
path: root/lib/Transforms/InstCombine
diff options
context:
space:
mode:
authorDimitry Andric <dim@FreeBSD.org>2019-01-19 10:01:25 +0000
committerDimitry Andric <dim@FreeBSD.org>2019-01-19 10:01:25 +0000
commitd8e91e46262bc44006913e6796843909f1ac7bcd (patch)
tree7d0c143d9b38190e0fa0180805389da22cd834c5 /lib/Transforms/InstCombine
parentb7eb8e35e481a74962664b63dfb09483b200209a (diff)
Notes
Diffstat (limited to 'lib/Transforms/InstCombine')
-rw-r--r--lib/Transforms/InstCombine/InstCombineAddSub.cpp321
-rw-r--r--lib/Transforms/InstCombine/InstCombineAndOrXor.cpp595
-rw-r--r--lib/Transforms/InstCombine/InstCombineCalls.cpp532
-rw-r--r--lib/Transforms/InstCombine/InstCombineCasts.cpp126
-rw-r--r--lib/Transforms/InstCombine/InstCombineCompares.cpp663
-rw-r--r--lib/Transforms/InstCombine/InstCombineInternal.h64
-rw-r--r--lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp143
-rw-r--r--lib/Transforms/InstCombine/InstCombineMulDivRem.cpp102
-rw-r--r--lib/Transforms/InstCombine/InstCombinePHI.cpp27
-rw-r--r--lib/Transforms/InstCombine/InstCombineSelect.cpp323
-rw-r--r--lib/Transforms/InstCombine/InstCombineShifts.cpp17
-rw-r--r--lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp255
-rw-r--r--lib/Transforms/InstCombine/InstCombineVectorOps.cpp526
-rw-r--r--lib/Transforms/InstCombine/InstructionCombining.cpp262
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());