[InstCombine] Push negation through multiply (PR44234)

[nikic]

Summary

Fixes https://bugs.llvm.org/show_bug.cgi?id=44234 by adding multiply support to freelyNegateValue(). Only one of the operands needs to be negatible, so this still fits within the framework.

[nikic]

llvm/test/Transforms/InstCombine/and-or-icmps.ll

207 ↗

(On Diff #240367)

We have a regression here... the relevant difference is that the %B7 neg gets reassociated to act on %B23 instead, which is then pushed through to the %B11 udiv, which is a sext at that point and gets folded to zext. That somehow prevents other folds. As this is a fuzzer generated test case I'm not particularly worried about this, but can take a closer look if people think this is important.

[nikic]

Rebase

[xbolva00]

Thanks on working on this

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

940

Not related to this change:

Should we worry about recursion depth here? Probably not a issue in practise..

llvm/test/Transforms/InstCombine/sub.ll

701–702

commuted

[nikic]

Fix typo

[nikic]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

940

Due to the one-use restriction (which prevents degenerating to exponential walks) I'm not really worried about recursion here. It could in theory visit many instructions (if you have a thousand multiplies in a chain...), but will never result in super-linear runtime, which I think is the main concern.

But I can add a depth limit if desired.

[nikic]

Rebase over D73411.

[nikic]

Looks like the regression in and-or-icmps.ll wasn't actually caused by the IR difference itself, but the worklist order change caused by performing the negation. After rebasing over D73411 the regression disappeared :)

[xbolva00]

Great! LG.

@spatel ?

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

case Instruction::Shl:
     return nullptr;
 
   // 0-(trunc A)  =>  trunc (0-A)
   case Instruction::Trunc:
     if (Value *NegA = freelyNegateValue(I->getOperand(0)))
       return Builder.CreateTrunc(NegA, I->getType(), I->getName() + ".neg");
     return nullptr;
 
+  // 0-(A*B)  =>  (0-A)*B
+  // 0-(A*B)  =>  A*(0-B)
+  case Instruction::Mul:
+    if (Value *NegA = freelyNegateValue(I->getOperand(0)))
+      return Builder.CreateMul(NegA, I->getOperand(1), V->getName() + ".neg");
+    if (Value *NegB = freelyNegateValue(I->getOperand(1)))
+      return Builder.CreateMul(I->getOperand(0), NegB, V->getName() + ".neg");
+    return nullptr;
+
   default:
     return nullptr;
   }
 }
 
 static Value *foldOperationIntoSelectOperand(Instruction &I, Value *SO,
                                              InstCombiner::BuilderTy &Builder) {
   if (auto *Cast = dyn_cast<CastInst>(&I))

llvm/test/Transforms/InstCombine/mul.ll

 ;
   %neg = sub i32 0, %x
   %mul = mul i32 %neg, %y
   ret i32 %mul
 }
 
 define i32 @test_mul_canonicalize_op1(i32 %x, i32 %z) {
 ; CHECK-LABEL: @test_mul_canonicalize_op1(
-; CHECK-NEXT:    [[Y:%.*]] = mul i32 [[Z:%.*]], 3
-; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[Y]], [[X:%.*]]
-; CHECK-NEXT:    [[MUL:%.*]] = sub i32 0, [[TMP1]]
-; CHECK-NEXT:    ret i32 [[MUL]]
+; CHECK-NEXT:    [[Y_NEG:%.*]] = mul i32 [[Z:%.*]], -3
+; CHECK-NEXT:    [[DOTNEG:%.*]] = mul i32 [[Y_NEG]], [[X:%.*]]
+; CHECK-NEXT:    ret i32 [[DOTNEG]]
 ;
   %y = mul i32 %z, 3
   %neg = sub i32 0, %x
   %mul = mul i32 %y, %neg
   ret i32 %mul
 }
 
 define i32 @test_mul_canonicalize_nsw(i32 %x, i32 %y) {

llvm/test/Transforms/InstCombine/sub.ll

;
   %shl = shl i64 %shr, %b
   %trunc = trunc i64 %shl to i32
   %neg = sub i32 0, %trunc
   ret i32 %neg
 }
 
 define i64 @test_neg_mul_sub(i64 %a, i64 %b, i64 %c) {
 ; CHECK-LABEL: @test_neg_mul_sub(
-; CHECK-NEXT:    [[SUB:%.*]] = sub i64 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[MUL:%.*]] = mul i64 [[SUB]], [[C:%.*]]
-; CHECK-NEXT:    [[NEG:%.*]] = sub i64 0, [[MUL]]
-; CHECK-NEXT:    ret i64 [[NEG]]
+; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub i64 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[MUL_NEG:%.*]] = mul i64 [[SUB_NEG]], [[C:%.*]]
+; CHECK-NEXT:    ret i64 [[MUL_NEG]]
 ;
   %sub = sub i64 %a, %b
   %mul = mul i64 %sub, %c
   %neg = sub i64 0, %mul
   ret i64 %neg
 }
 
-define i64 @test_neg_mul_sub_communted(i64 %a, i64 %b, i64 %c) {
-; CHECK-LABEL: @test_neg_mul_sub_communted(
+define i64 @test_neg_mul_sub_commuted(i64 %a, i64 %b, i64 %c) {
+; CHECK-LABEL: @test_neg_mul_sub_commuted(
 ; CHECK-NEXT:    [[COMPLEX:%.*]] = mul i64 [[C:%.*]], [[C]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i64 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[MUL:%.*]] = mul i64 [[COMPLEX]], [[SUB]]
-; CHECK-NEXT:    [[NEG:%.*]] = sub i64 0, [[MUL]]
-; CHECK-NEXT:    ret i64 [[NEG]]
+; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub i64 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[MUL_NEG:%.*]] = mul i64 [[COMPLEX]], [[SUB_NEG]]
+; CHECK-NEXT:    ret i64 [[MUL_NEG]]
 ;
   %complex = mul i64 %c, %c
   %sub = sub i64 %a, %b
   %mul = mul i64 %complex, %sub
   %neg = sub i64 0, %mul
   ret i64 %neg
 }