[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

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

923

Not related to this change:

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

llvm/test/Transforms/InstCombine/sub.ll

702

commuted

[nikic]

Fix typo

[nikic]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

923

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

Value *InstCombiner::freelyNegateValue(Value *V) {
   } else if (match(V, m_Shl(m_Value(A), m_Value(B)))) {
     // 0-(A<<B)  =>  (0-A)<<B
     if (Value *NegA = freelyNegateValue(A))
       return Builder.CreateShl(NegA, B, V->getName() + ".neg");
   } else if (match(V, m_Trunc(m_Value(A)))) {
     // 0-(trunc A)  =>  trunc (0-A)
     if (Value *NegA = freelyNegateValue(A))
       return Builder.CreateTrunc(NegA, V->getType());
+  } else if (match(V, m_Mul(m_Value(A), m_Value(B)))) {
+    // 0-(A*B)  =>  (0-A)*B
+    // 0-(A*B)  =>  A*(0-B)
+    if (Value *NegA = freelyNegateValue(A))
+      return Builder.CreateMul(NegA, B, V->getName() + ".neg");
+    if (Value *NegB = freelyNegateValue(B))
+      return Builder.CreateMul(A, NegB, V->getName() + ".neg");
   }
 
   return nullptr;
 }
 
 static Value *foldOperationIntoSelectOperand(Instruction &I, Value *SO,
                                              InstCombiner::BuilderTy &Builder) {
   if (auto *Cast = dyn_cast<CastInst>(&I))
     return Builder.CreateCast(Cast->getOpcode(), SO, I.getType());
 
   assert(I.isBinaryOp() && "Unexpected opcode for select folding");
 
   // Figure out if the constant is the left or the right argument.

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

;
   ret <2 x i1> %and
 }
 
 ; This is a fuzzer-generated test that would assert because
 ; we'd get into foldAndOfICmps() without running InstSimplify
 ; on an 'and' that should have been killed. It's not obvious
 ; why, but removing anything hides the bug, hence the long test.
 
 define void @simplify_before_foldAndOfICmps() {
 ; CHECK-LABEL: @simplify_before_foldAndOfICmps(
 ; CHECK-NEXT:    [[A8:%.*]] = alloca i16, align 2
 ; CHECK-NEXT:    [[L7:%.*]] = load i16, i16* [[A8]], align 2
-; CHECK-NEXT:    [[C10:%.*]] = icmp ult i16 [[L7]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i16 [[L7]], -1
+; CHECK-NEXT:    [[B11:%.*]] = zext i1 [[TMP1]] to i16
+; CHECK-NEXT:    [[C10:%.*]] = icmp ugt i16 [[L7]], [[B11]]
+; CHECK-NEXT:    [[C5:%.*]] = icmp slt i16 [[L7]], 1
+; CHECK-NEXT:    [[C11:%.*]] = icmp ne i16 [[L7]], 0
 ; CHECK-NEXT:    [[C7:%.*]] = icmp slt i16 [[L7]], 0
-; CHECK-NEXT:    [[C18:%.*]] = or i1 [[C7]], [[C10]]
-; CHECK-NEXT:    [[L7_LOBIT:%.*]] = ashr i16 [[L7]], 15
-; CHECK-NEXT:    [[TMP1:%.*]] = sext i16 [[L7_LOBIT]] to i64
-; CHECK-NEXT:    [[G26:%.*]] = getelementptr i1, i1* null, i64 [[TMP1]]
+; CHECK-NEXT:    [[B15:%.*]] = xor i1 [[C7]], [[C10]]
+; CHECK-NEXT:    [[B19:%.*]] = xor i1 [[C11]], [[B15]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[C10]], [[C5]]
+; CHECK-NEXT:    [[C3:%.*]] = and i1 [[B19]], [[TMP2]]
+; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[C10]], true
+; CHECK-NEXT:    [[C18:%.*]] = or i1 [[C7]], [[TMP3]]
+; CHECK-NEXT:    [[TMP4:%.*]] = sext i1 [[C3]] to i64
+; CHECK-NEXT:    [[G26:%.*]] = getelementptr i1, i1* null, i64 [[TMP4]]
 ; CHECK-NEXT:    store i16 [[L7]], i16* undef, align 2
 ; CHECK-NEXT:    store i1 [[C18]], i1* undef, align 1
 ; CHECK-NEXT:    store i1* [[G26]], i1** undef, align 8
 ; CHECK-NEXT:    ret void
 ;
   %A8 = alloca i16
   %L7 = load i16, i16* %A8
   %G21 = getelementptr i16, i16* %A8, i8 -1

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(
 ; 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
 }