Index: llvm/trunk/lib/Transforms/InstCombine/InstCombineAddSub.cpp =================================================================== --- llvm/trunk/lib/Transforms/InstCombine/InstCombineAddSub.cpp +++ llvm/trunk/lib/Transforms/InstCombine/InstCombineAddSub.cpp @@ -954,6 +954,48 @@ return true; return false; + } + +// Checks if any operand is negative and we can convert add to sub. +// This function checks for following negative patterns +// ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C)) +// TODO: ADD(XOR(AND(Z, ~C), ~C), 1) == NEG(OR(Z, C)) if C is even +// TODO: XOR(AND(Z, ~C), (~C + 1)) == NEG(OR(Z, C)) if C is odd +Value *checkForNegativeOperand(BinaryOperator &I, + InstCombiner::BuilderTy *Builder) { + Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); + + // This function creates 2 instructions to replace ADD, we need at least one + // of LHS or RHS to have one use to ensure benefit in transform. + if (!LHS->hasOneUse() && !RHS->hasOneUse()) + return nullptr; + + bool IHasNSW = I.hasNoSignedWrap(); + bool IHasNUW = I.hasNoUnsignedWrap(); + + Value *X = nullptr, *Y = nullptr, *Z = nullptr; + const APInt *C1 = nullptr, *C2 = nullptr; + + // if ONE is on other side, swap + if (match(RHS, m_Add(m_Value(X), m_One()))) + std::swap(LHS, RHS); + + if (match(LHS, m_Add(m_Value(X), m_One()))) { + // if XOR on other side, swap + if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1)))) + std::swap(X, RHS); + + // X = XOR(Y, C1), Y = OR(Z, C2), C2 = NOT(C1) ==> X == NOT(AND(Z, C1)) + // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, AND(Z, C1)) + if (match(X, m_Xor(m_Value(Y), m_APInt(C1)))) { + if (match(Y, m_Or(m_Value(Z), m_APInt(C2))) && (*C2 == ~(*C1))) { + Value *NewAnd = Builder->CreateAnd(Z, *C1); + return Builder->CreateSub(RHS, NewAnd, "", IHasNUW, IHasNSW); + } + } + } + + return nullptr; } Instruction *InstCombiner::visitAdd(BinaryOperator &I) { @@ -1065,6 +1107,9 @@ if (Value *V = dyn_castNegVal(RHS)) return BinaryOperator::CreateSub(LHS, V); + if (Value *V = checkForNegativeOperand(I, Builder)) + return ReplaceInstUsesWith(I, V); + // A+B --> A|B iff A and B have no bits set in common. if (IntegerType *IT = dyn_cast(I.getType())) { APInt LHSKnownOne(IT->getBitWidth(), 0); Index: llvm/trunk/test/Transforms/InstCombine/add2.ll =================================================================== --- llvm/trunk/test/Transforms/InstCombine/add2.ll +++ llvm/trunk/test/Transforms/InstCombine/add2.ll @@ -87,6 +87,69 @@ ; CHECK-NEXT: ret i16 %d } +define i32 @test10(i32 %x) { + %x.not = or i32 %x, -1431655766 + %neg = xor i32 %x.not, 1431655765 + %add = add i32 %x, 1 + %add1 = add i32 %add, %neg + ret i32 %add1 +; CHECK-LABEL: @test10( +; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, -1431655766 +; CHECK-NEXT: ret i32 [[AND]] +} + +define i32 @test11(i32 %x, i32 %y) { + %x.not = or i32 %x, -1431655766 + %neg = xor i32 %x.not, 1431655765 + %add = add i32 %y, 1 + %add1 = add i32 %add, %neg + ret i32 %add1 +; CHECK-LABEL: @test11( +; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, 1431655765 +; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]] +; CHECK-NEXT: ret i32 [[SUB]] +} + +define i32 @test12(i32 %x, i32 %y) { + %shr = ashr i32 %x, 3 + %shr.not = or i32 %shr, -1431655766 + %neg = xor i32 %shr.not, 1431655765 + %add = add i32 %y, 1 + %add1 = add i32 %add, %neg + ret i32 %add1 +; CHECK-LABEL: @test12( +; CHECK-NEXT: [[SHR:%[a-z0-9]+]] = ashr i32 %x, 3 +; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 [[SHR]], 1431655765 +; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]] +; CHECK-NEXT: ret i32 [[SUB]] +} + +define i32 @test13(i32 %x, i32 %y) { + %x.not = or i32 %x, -1431655767 + %neg = xor i32 %x.not, 1431655766 + %add = add i32 %y, 1 + %add1 = add i32 %add, %neg + ret i32 %add1 +; CHECK-LABEL: @test13( +; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, 1431655766 +; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]] +; CHECK-NEXT: ret i32 [[SUB]] +} + +define i32 @test14(i32 %x, i32 %y) { + %shr = ashr i32 %x, 3 + %shr.not = or i32 %shr, -1431655767 + %neg = xor i32 %shr.not, 1431655766 + %add = add i32 %y, 1 + %add1 = add i32 %add, %neg + ret i32 %add1 +; CHECK-LABEL: @test14( +; CHECK-NEXT: [[SHR:%[a-z0-9]+]] = ashr i32 %x, 3 +; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 [[SHR]], 1431655766 +; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]] +; CHECK-NEXT: ret i32 [[SUB]] +} + define i16 @add_nsw_mul_nsw(i16 %x) { %add1 = add nsw i16 %x, %x %add2 = add nsw i16 %add1, %x