diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
--- a/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
@@ -1900,6 +1900,27 @@
return SelectInst::Create(Cmp, Neg, A);
}
+ // Now that we know we have failed to fold this `sub a, b`, iff `a != 0`,
+ // let's see if it's worth exploding it into `add a, (sub 0, b)`.
+ // It is worth doing if the negation can be sunk into `b`.
+ if (!match(Op0, m_Zero()) && isFreeToNegate(Op1)) {
+ // While this does temporairly increase instruction count, we have ensured
+ // that this `neg` will get absorbed into Op1, so this is ok.
+ Instruction *NegOp1 =
+ BinaryOperator::CreateNeg(Op1, Op1->getName() + ".neg");
+ Instruction *NewAdd = BinaryOperator::CreateAdd(NegOp1, Op0);
+ // Normally, the `neg` would have been added to InstCombine's WorkList
+ // first, and then the `add`. So we'd first revisit `add`, but we just made
+ // it so that one of the `add`s operands is `neg`, so it would hoist that
+ // `neg` and recreate subtraction, and we'll endlessly loop...
+ // Instead, let's manually first add the `add` and *then* `neg`, this way
+ // we will first visit the `neg`, and go on folding it into it's operand.
+ Worklist.Add(NewAdd);
+ Worklist.Add(NegOp1);
+ Builder.Insert(NegOp1);
+ return NewAdd;
+ }
+
if (Instruction *Ext = narrowMathIfNoOverflow(I))
return Ext;
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
--- a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
+++ b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
@@ -199,6 +199,55 @@
return true; // Can freely invert all users!
}
+/// Return true if the specified value is free to negate (subtract from 0).
+/// This happens in cases where the 0 can be eliminated.
+/// For instructions, this is limited to single-use instructions.
+/// The analysis is recursive.
+static inline bool isFreeToNegate(Value *V, unsigned Depth = 0) {
+ // -(-(X)) -> X.
+ if (match(V, m_Neg(m_Value())))
+ return true;
+
+ // Constants can be considered to be negated values.
+ if (match(V, m_AnyIntegralConstant()))
+ return true;
+
+ // Rest of the checking is recursive, so time to pessimistically bailout.
+ if (Depth > 6)
+ return false;
+
+ // If we have a non-instruction, and it's not a constant, then give up.
+ if (!isa<Instruction>(V))
+ return false;
+ // The instruction-in-question must be one-use.
+ if (!V->hasOneUse())
+ return false;
+
+ auto *I = cast<Instruction>(V);
+ switch (I->getOpcode()) {
+ case Instruction::Select:
+ // `select` is negatible if both hands of select are negatible.
+ return isFreeToNegate(I->getOperand(1), Depth + 1) &&
+ isFreeToNegate(I->getOperand(2), Depth + 1);
+ case Instruction::Shl:
+ case Instruction::Sub:
+ // `shl`, `sub` are negatible if their first operand is negatible.
+ return isFreeToNegate(I->getOperand(0), Depth + 1);
+ case Instruction::Add:
+ // `add` is negatible if both of it's operands are negatible.
+ return isFreeToNegate(I->getOperand(0), Depth + 1) &&
+ isFreeToNegate(I->getOperand(1), Depth + 1);
+ case Instruction::Mul:
+ // `mul` is negatible one of it's operands is negatible.
+ return isFreeToNegate(I->getOperand(0), Depth + 1) ||
+ isFreeToNegate(I->getOperand(1), Depth + 1);
+ default:
+ return false; // Don't know, likely not negatible for free.
+ }
+
+ return false;
+}
+
/// Some binary operators require special handling to avoid poison and undefined
/// behavior. If a constant vector has undef elements, replace those undefs with
/// identity constants if possible because those are always safe to execute.
diff --git a/llvm/test/Transforms/InstCombine/sub-of-negatible.ll b/llvm/test/Transforms/InstCombine/sub-of-negatible.ll
--- a/llvm/test/Transforms/InstCombine/sub-of-negatible.ll
+++ b/llvm/test/Transforms/InstCombine/sub-of-negatible.ll
@@ -30,8 +30,8 @@
; Shift-left can be negated if all uses can be updated
define i8 @t2(i8 %x, i8 %y) {
; CHECK-LABEL: @t2(
-; CHECK-NEXT: [[T0:%.*]] = shl i8 -42, [[Y:%.*]]
-; CHECK-NEXT: [[T1:%.*]] = sub i8 [[X:%.*]], [[T0]]
+; CHECK-NEXT: [[TMP1:%.*]] = shl i8 42, [[Y:%.*]]
+; CHECK-NEXT: [[T1:%.*]] = add i8 [[TMP1]], [[X:%.*]]
; CHECK-NEXT: ret i8 [[T1]]
;
%t0 = shl i8 -42, %y
@@ -54,8 +54,8 @@
; CHECK-LABEL: @t3(
; CHECK-NEXT: [[T0:%.*]] = sub i8 0, [[Z:%.*]]
; CHECK-NEXT: call void @use8(i8 [[T0]])
-; CHECK-NEXT: [[T1:%.*]] = shl i8 [[T0]], [[Y:%.*]]
-; CHECK-NEXT: [[T2:%.*]] = sub i8 [[X:%.*]], [[T1]]
+; CHECK-NEXT: [[TMP1:%.*]] = shl i8 [[Z]], [[Y:%.*]]
+; CHECK-NEXT: [[T2:%.*]] = add i8 [[TMP1]], [[X:%.*]]
; CHECK-NEXT: ret i8 [[T2]]
;
%t0 = sub i8 0, %z
@@ -84,8 +84,8 @@
; Select can be negated if all it's operands can be negated and all the users of select can be updated
define i8 @t4(i8 %x, i1 %y) {
; CHECK-LABEL: @t4(
-; CHECK-NEXT: [[T0:%.*]] = select i1 [[Y:%.*]], i8 -42, i8 44
-; CHECK-NEXT: [[T1:%.*]] = sub i8 [[X:%.*]], [[T0]]
+; CHECK-NEXT: [[TMP1:%.*]] = select i1 [[Y:%.*]], i8 42, i8 -44
+; CHECK-NEXT: [[T1:%.*]] = add i8 [[TMP1]], [[X:%.*]]
; CHECK-NEXT: ret i8 [[T1]]
;
%t0 = select i1 %y, i8 -42, i8 44
@@ -118,8 +118,8 @@
; CHECK-LABEL: @t6(
; CHECK-NEXT: [[T0:%.*]] = sub i8 0, [[Z:%.*]]
; CHECK-NEXT: call void @use8(i8 [[T0]])
-; CHECK-NEXT: [[T1:%.*]] = select i1 [[Y:%.*]], i8 -42, i8 [[T0]]
-; CHECK-NEXT: [[T2:%.*]] = sub i8 [[X:%.*]], [[T1]]
+; CHECK-NEXT: [[TMP1:%.*]] = select i1 [[Y:%.*]], i8 42, i8 [[Z]]
+; CHECK-NEXT: [[T2:%.*]] = add i8 [[TMP1]], [[X:%.*]]
; CHECK-NEXT: ret i8 [[T2]]
;
%t0 = sub i8 0, %z
@@ -130,9 +130,9 @@
}
define i8 @t7(i8 %x, i1 %y, i8 %z) {
; CHECK-LABEL: @t7(
-; CHECK-NEXT: [[T0:%.*]] = shl i8 1, [[Z:%.*]]
-; CHECK-NEXT: [[T1:%.*]] = select i1 [[Y:%.*]], i8 0, i8 [[T0]]
-; CHECK-NEXT: [[T2:%.*]] = sub i8 [[X:%.*]], [[T1]]
+; CHECK-NEXT: [[T0_OP:%.*]] = shl i8 -1, [[Z:%.*]]
+; CHECK-NEXT: [[TMP1:%.*]] = select i1 [[Y:%.*]], i8 0, i8 [[T0_OP]]
+; CHECK-NEXT: [[T2:%.*]] = add i8 [[TMP1]], [[X:%.*]]
; CHECK-NEXT: ret i8 [[T2]]
;
%t0 = shl i8 1, %z
@@ -290,3 +290,11 @@
%t2 = sub i8 %x, %t1
ret i8 %t2
}
+
+; We shouldn't try to convert -b into 0+(-b)
+define i32 @dont_touch_negation_itself(i32 %x, i32 %y) {
+ %a = mul i32 %y, 3
+ %b = mul i32 %a, %x
+ %mul = sub i32 0, %b
+ ret i32 %mul
+}