Skip to content

Commit bcfa0f5

Browse files
nikicnikic
committed
[InstCombine] Move negation handling into freelyNegateValue()
Followup to D72978. This moves existing negation handling in InstCombine into freelyNegateValue(), which make it composable. In particular, root negations of div/zext/sext/ashr/lshr/sub can now always be performed through a shl/trunc as well. Differential Revision: https://reviews.llvm.org/D73288
1 parent 0957748 commit bcfa0f5

File tree

3 files changed

+145
-142
lines changed

3 files changed

+145
-142
lines changed

‎llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

Lines changed: 17 additions & 75 deletions
Original file line numberDiff line numberDiff line change
@@ -1734,22 +1734,18 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) {
17341734
}
17351735

17361736
if (Constant *C = dyn_cast<Constant>(Op0)) {
1737-
bool IsNegate = match(C, m_ZeroInt());
1737+
// -f(x) -> f(-x) if possible.
1738+
if (match(C, m_Zero()))
1739+
if (Value *Neg = freelyNegateValue(Op1))
1740+
return replaceInstUsesWith(I, Neg);
1741+
17381742
Value *X;
1739-
if (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1740-
// 0 - (zext bool) --> sext bool
1743+
if (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
17411744
// C - (zext bool) --> bool ? C - 1 : C
1742-
if (IsNegate)
1743-
return CastInst::CreateSExtOrBitCast(X, I.getType());
17441745
return SelectInst::Create(X, SubOne(C), C);
1745-
}
1746-
if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1747-
// 0 - (sext bool) --> zext bool
1746+
if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
17481747
// C - (sext bool) --> bool ? C + 1 : C
1749-
if (IsNegate)
1750-
return CastInst::CreateZExtOrBitCast(X, I.getType());
17511748
return SelectInst::Create(X, AddOne(C), C);
1752-
}
17531749

17541750
// C - ~X == X + (1+C)
17551751
if (match(Op1, m_Not(m_Value(X))))
@@ -1778,51 +1774,15 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) {
17781774

17791775
const APInt *Op0C;
17801776
if (match(Op0, m_APInt(Op0C))) {
1781-
1782-
if (Op0C->isNullValue()) {
1783-
Value *Op1Wide;
1784-
match(Op1, m_TruncOrSelf(m_Value(Op1Wide)));
1785-
bool HadTrunc = Op1Wide != Op1;
1786-
bool NoTruncOrTruncIsOneUse = !HadTrunc || Op1->hasOneUse();
1787-
unsigned BitWidth = Op1Wide->getType()->getScalarSizeInBits();
1788-
1789-
Value *X;
1790-
const APInt *ShAmt;
1791-
// -(X >>u 31) -> (X >>s 31)
1792-
if (NoTruncOrTruncIsOneUse &&
1793-
match(Op1Wide, m_LShr(m_Value(X), m_APInt(ShAmt))) &&
1794-
*ShAmt == BitWidth - 1) {
1795-
Value *ShAmtOp = cast<Instruction>(Op1Wide)->getOperand(1);
1796-
Instruction *NewShift = BinaryOperator::CreateAShr(X, ShAmtOp);
1797-
NewShift->copyIRFlags(Op1Wide);
1798-
if (!HadTrunc)
1799-
return NewShift;
1800-
Builder.Insert(NewShift);
1801-
return TruncInst::CreateTruncOrBitCast(NewShift, Op1->getType());
1802-
}
1803-
// -(X >>s 31) -> (X >>u 31)
1804-
if (NoTruncOrTruncIsOneUse &&
1805-
match(Op1Wide, m_AShr(m_Value(X), m_APInt(ShAmt))) &&
1806-
*ShAmt == BitWidth - 1) {
1807-
Value *ShAmtOp = cast<Instruction>(Op1Wide)->getOperand(1);
1808-
Instruction *NewShift = BinaryOperator::CreateLShr(X, ShAmtOp);
1809-
NewShift->copyIRFlags(Op1Wide);
1810-
if (!HadTrunc)
1811-
return NewShift;
1812-
Builder.Insert(NewShift);
1813-
return TruncInst::CreateTruncOrBitCast(NewShift, Op1->getType());
1814-
}
1815-
1816-
if (!HadTrunc && Op1->hasOneUse()) {
1817-
Value *LHS, *RHS;
1818-
SelectPatternFlavor SPF = matchSelectPattern(Op1, LHS, RHS).Flavor;
1819-
if (SPF == SPF_ABS || SPF == SPF_NABS) {
1820-
// This is a negate of an ABS/NABS pattern. Just swap the operands
1821-
// of the select.
1822-
cast<SelectInst>(Op1)->swapValues();
1823-
// Don't swap prof metadata, we didn't change the branch behavior.
1824-
return replaceInstUsesWith(I, Op1);
1825-
}
1777+
if (Op0C->isNullValue() && Op1->hasOneUse()) {
1778+
Value *LHS, *RHS;
1779+
SelectPatternFlavor SPF = matchSelectPattern(Op1, LHS, RHS).Flavor;
1780+
if (SPF == SPF_ABS || SPF == SPF_NABS) {
1781+
// This is a negate of an ABS/NABS pattern. Just swap the operands
1782+
// of the select.
1783+
cast<SelectInst>(Op1)->swapValues();
1784+
// Don't swap prof metadata, we didn't change the branch behavior.
1785+
return replaceInstUsesWith(I, Op1);
18261786
}
18271787
}
18281788

@@ -1957,7 +1917,7 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) {
19571917
}
19581918

19591919
if (Op1->hasOneUse()) {
1960-
Value *X = nullptr, *Y = nullptr, *Z = nullptr;
1920+
Value *Y = nullptr, *Z = nullptr;
19611921
Constant *C = nullptr;
19621922

19631923
// (X - (Y - Z)) --> (X + (Z - Y)).
@@ -1970,24 +1930,6 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) {
19701930
return BinaryOperator::CreateAnd(Op0,
19711931
Builder.CreateNot(Y, Y->getName() + ".not"));
19721932

1973-
// 0 - (X sdiv C) -> (X sdiv -C) provided the negation doesn't overflow.
1974-
if (match(Op0, m_Zero())) {
1975-
Constant *Op11C;
1976-
if (match(Op1, m_SDiv(m_Value(X), m_Constant(Op11C))) &&
1977-
!Op11C->containsUndefElement() && Op11C->isNotMinSignedValue() &&
1978-
Op11C->isNotOneValue()) {
1979-
Instruction *BO =
1980-
BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(Op11C));
1981-
BO->setIsExact(cast<BinaryOperator>(Op1)->isExact());
1982-
return BO;
1983-
}
1984-
}
1985-
1986-
// 0 - (X << Y) -> (-X << Y) when X is freely negatable.
1987-
if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero()))
1988-
if (Value *XNeg = freelyNegateValue(X))
1989-
return BinaryOperator::CreateShl(XNeg, Y);
1990-
19911933
// Subtracting -1/0 is the same as adding 1/0:
19921934
// sub [nsw] Op0, sext(bool Y) -> add [nsw] Op0, zext(bool Y)
19931935
// 'nuw' is dropped in favor of the canonical form.

‎llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

Lines changed: 72 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -862,15 +862,82 @@ Value *InstCombiner::freelyNegateValue(Value *V) {
862862
if (Value *NegV = dyn_castNegVal(V))
863863
return NegV;
864864

865-
if (!V->hasOneUse())
865+
Instruction *I = dyn_cast<Instruction>(V);
866+
if (!I)
866867
return nullptr;
867868

868-
Value *A, *B;
869+
unsigned BitWidth = I->getType()->getScalarSizeInBits();
870+
switch (I->getOpcode()) {
871+
// 0-(zext i1 A) => sext i1 A
872+
case Instruction::ZExt:
873+
if (I->getOperand(0)->getType()->isIntOrIntVectorTy(1))
874+
return Builder.CreateSExtOrBitCast(
875+
I->getOperand(0), I->getType(), I->getName() + ".neg");
876+
return nullptr;
877+
878+
// 0-(sext i1 A) => zext i1 A
879+
case Instruction::SExt:
880+
if (I->getOperand(0)->getType()->isIntOrIntVectorTy(1))
881+
return Builder.CreateZExtOrBitCast(
882+
I->getOperand(0), I->getType(), I->getName() + ".neg");
883+
return nullptr;
884+
885+
// 0-(A lshr (BW-1)) => A ashr (BW-1)
886+
case Instruction::LShr:
887+
if (match(I->getOperand(1), m_SpecificInt(BitWidth - 1)))
888+
return Builder.CreateAShr(
889+
I->getOperand(0), I->getOperand(1),
890+
I->getName() + ".neg", cast<BinaryOperator>(I)->isExact());
891+
return nullptr;
892+
893+
// 0-(A ashr (BW-1)) => A lshr (BW-1)
894+
case Instruction::AShr:
895+
if (match(I->getOperand(1), m_SpecificInt(BitWidth - 1)))
896+
return Builder.CreateLShr(
897+
I->getOperand(0), I->getOperand(1),
898+
I->getName() + ".neg", cast<BinaryOperator>(I)->isExact());
899+
return nullptr;
900+
901+
default:
902+
break;
903+
}
904+
905+
// TODO: The "sub" pattern below could also be applied without the one-use
906+
// restriction. Not allowing it for now in line with existing behavior.
907+
if (!I->hasOneUse())
908+
return nullptr;
909+
910+
switch (I->getOpcode()) {
869911
// 0-(A-B) => B-A
870-
if (match(V, m_Sub(m_Value(A), m_Value(B))))
871-
return Builder.CreateSub(B, A);
912+
case Instruction::Sub:
913+
return Builder.CreateSub(
914+
I->getOperand(1), I->getOperand(0), I->getName() + ".neg");
915+
916+
// 0-(A sdiv C) => A sdiv (0-C) provided the negation doesn't overflow.
917+
case Instruction::SDiv: {
918+
Constant *C = dyn_cast<Constant>(I->getOperand(1));
919+
if (C && !C->containsUndefElement() && C->isNotMinSignedValue() &&
920+
C->isNotOneValue())
921+
return Builder.CreateSDiv(I->getOperand(0), ConstantExpr::getNeg(C),
922+
I->getName() + ".neg", cast<BinaryOperator>(I)->isExact());
923+
return nullptr;
924+
}
872925

873-
return nullptr;
926+
// 0-(A<<B) => (0-A)<<B
927+
case Instruction::Shl:
928+
if (Value *NegA = freelyNegateValue(I->getOperand(0)))
929+
return Builder.CreateShl(NegA, I->getOperand(1), I->getName() + ".neg");
930+
return nullptr;
931+
932+
// 0-(trunc A) => trunc (0-A)
933+
case Instruction::Trunc:
934+
if (Value *NegA = freelyNegateValue(I->getOperand(0)))
935+
return Builder.CreateTrunc(NegA, I->getType(), I->getName() + ".neg");
936+
return nullptr;
937+
938+
default:
939+
return nullptr;
940+
}
874941
}
875942

876943
static Value *foldOperationIntoSelectOperand(Instruction &I, Value *SO,

0 commit comments

Comments
 (0)