[InstCombine] Move negation handling into freelyNegateValue()

[nikic]

Summary

Followup to D72978. This moves existing negation handling in InstCombine into freelyNegateValue(), which make it more composable. In particular, root negations of div/zext/sext/ashr/lshr/sub can now always be performed through a shl/trunc as well.

The next step is to add multiply support to fix https://bugs.llvm.org/show_bug.cgi?id=44234.

[nikic]

Also move the ashr/lshr and trunc patterns into freelyNegateValue() and keep existing handling regarding one-use checks.

[spatel]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

867

Seems like this would be more efficient as a "switch(V->getOpcode())"?

Then, we could combine cases like ashr/lshr by using Builder.CreateBinOp(V->getOpcode()...). Similarly combine zext/sext with Builder.CreateCast().

[nikic]

Use switch instead of match chain.

[nikic]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

867

I've switched this to use switch, but ended up not combining the cases. The problem is that we need to swap the signedness of the opcodes (zext <-> sext, lshr <-> ashr), which is just awkward enough that keeping the cases separate looks more readable. (Especially as there is no direct API for creating an "lshr or ashr" with exact flag.)

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

Instruction *InstCombiner::visitSub(BinaryOperator &I) {
 
   // Y - ~X --> (X + 1) + Y
   if (match(Op1, m_OneUse(m_Not(m_Value(X))))) {
     return BinaryOperator::CreateAdd(
         Builder.CreateAdd(Op0, ConstantInt::get(I.getType(), 1)), X);
   }
 
   if (Constant *C = dyn_cast<Constant>(Op0)) {
-    bool IsNegate = match(C, m_ZeroInt());
+    // -f(x) -> f(-x) if possible.
+    if (match(C, m_Zero()))
+      if (Value *Neg = freelyNegateValue(Op1))
+        return replaceInstUsesWith(I, Neg);
+
     Value *X;
-    if (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
-      // 0 - (zext bool) --> sext bool
+    if (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
       // C - (zext bool) --> bool ? C - 1 : C
-      if (IsNegate)
-        return CastInst::CreateSExtOrBitCast(X, I.getType());
       return SelectInst::Create(X, SubOne(C), C);
-    }
-    if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
-      // 0 - (sext bool) --> zext bool
+    if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
       // C - (sext bool) --> bool ? C + 1 : C
-      if (IsNegate)
-        return CastInst::CreateZExtOrBitCast(X, I.getType());
       return SelectInst::Create(X, AddOne(C), C);
-    }
 
     // C - ~X == X + (1+C)
     if (match(Op1, m_Not(m_Value(X))))
       return BinaryOperator::CreateAdd(X, AddOne(C));
 
     // Try to fold constant sub into select arguments.
     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
       if (Instruction *R = FoldOpIntoSelect(I, SI))
if (Instruction *NewSel = SinkSubIntoSelect(
             [Builder = &Builder, Op0](Value *OtherHandOfSelect) {
               return Builder->CreateSub(/*OtherHandOfSub=*/Op0,
                                         OtherHandOfSelect);
             }))
       return NewSel;
   }
 
   if (Op1->hasOneUse()) {
-    Value *X = nullptr, *Y = nullptr, *Z = nullptr;
+    Value *Y = nullptr, *Z = nullptr;
     Constant *C = nullptr;
 
     // (X - (Y - Z))  -->  (X + (Z - Y)).
     if (match(Op1, m_Sub(m_Value(Y), m_Value(Z))))
       return BinaryOperator::CreateAdd(Op0,
                                       Builder.CreateSub(Z, Y, Op1->getName()));
 
     // (X - (X & Y))   -->   (X & ~Y)
     if (match(Op1, m_c_And(m_Value(Y), m_Specific(Op0))))
       return BinaryOperator::CreateAnd(Op0,
                                   Builder.CreateNot(Y, Y->getName() + ".not"));
 
-    // 0 - (X sdiv C)  -> (X sdiv -C)  provided the negation doesn't overflow.
-    if (match(Op0, m_Zero())) {
-      Constant *Op11C;
-      if (match(Op1, m_SDiv(m_Value(X), m_Constant(Op11C))) &&
-          !Op11C->containsUndefElement() && Op11C->isNotMinSignedValue() &&
-          Op11C->isNotOneValue()) {
-        Instruction *BO =
-            BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(Op11C));
-        BO->setIsExact(cast<BinaryOperator>(Op1)->isExact());
-        return BO;
-      }
-    }
-
-    // 0 - (X << Y)  -> (-X << Y)   when X is freely negatable.
-    if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero()))
-      if (Value *XNeg = freelyNegateValue(X))
-        return BinaryOperator::CreateShl(XNeg, Y);
-
     // Subtracting -1/0 is the same as adding 1/0:
     // sub [nsw] Op0, sext(bool Y) -> add [nsw] Op0, zext(bool Y)
     // 'nuw' is dropped in favor of the canonical form.
     if (match(Op1, m_SExt(m_Value(Y))) &&
         Y->getType()->getScalarSizeInBits() == 1) {
       Value *Zext = Builder.CreateZExt(Y, I.getType());
       BinaryOperator *Add = BinaryOperator::CreateAdd(Op0, Zext);
       Add->setHasNoSignedWrap(I.hasNoSignedWrap());

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

 /// Get negated V (that is 0-V) without increasing instruction count,
 /// assuming that the original V will become unused.
 Value *InstCombiner::freelyNegateValue(Value *V) {
   if (Value *NegV = dyn_castNegVal(V))
     return NegV;
 
   if (!V->hasOneUse())
     return nullptr;
 
   Value *A, *B;
+  Constant *C;
+  if (match(V, m_Sub(m_Value(A), m_Value(B)))) {
     // 0-(A-B)  =>  B-A
-  if (match(V, m_Sub(m_Value(A), m_Value(B))))
-    return Builder.CreateSub(B, A);
+    return Builder.CreateSub(B, A, V->getName() + ".neg");
+  } else if (match(V, m_SDiv(m_Value(A), m_Constant(C)))) {
+    // 0-(X sdiv C)  =>  X sdiv (0-C)  provided the negation doesn't overflow.
+    if (!C->containsUndefElement() && C->isNotMinSignedValue() &&
+        C->isNotOneValue())
+      return Builder.CreateSDiv(A, ConstantExpr::getNeg(C),
+          V->getName() + ".neg", cast<BinaryOperator>(V)->isExact());
+  } else if (match(V, m_ZExt(m_Value(A)))) {
+    // 0-(zext i1 A)  =>  sext i1 A
+    if (A->getType()->isIntOrIntVectorTy(1))
+      return Builder.CreateSExtOrBitCast(
+          A, V->getType(), V->getName() + ".neg");
+  } else if (match(V, m_SExt(m_Value(A)))) {
+    // 0-(sext i1 A)  =>  zext i1 A
+    if (A->getType()->isIntOrIntVectorTy(1))
+      return Builder.CreateZExtOrBitCast(
+          A, V->getType(), V->getName() + ".neg");
+  } 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");
+  }
 
   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());

llvm/test/Transforms/InstCombine/sub.ll

 ;
   %C = sub i32 0, %A
   %D = srem i32 %B, %C
   ret i32 %D
 }
 
 define i32 @test16(i32 %A) {
 ; CHECK-LABEL: @test16(
-; CHECK-NEXT:    [[Y:%.*]] = sdiv i32 [[A:%.*]], -1123
-; CHECK-NEXT:    ret i32 [[Y]]
+; CHECK-NEXT:    [[X_NEG:%.*]] = sdiv i32 [[A:%.*]], -1123
+; CHECK-NEXT:    ret i32 [[X_NEG]]
 ;
   %X = sdiv i32 %A, 1123
   %Y = sub i32 0, %X
   ret i32 %Y
 }
 
 ; Can't fold subtract here because negation it might oveflow.
 ; PR3142
;
   %G = sub i64 %C, ptrtoint ([42 x i16]* @Arr to i64)
   ret i64 %G
 }
 
 
 define i64 @test25(i8* %P, i64 %A){
 ; CHECK-LABEL: @test25(
 ; CHECK-NEXT:    [[B_IDX:%.*]] = shl nsw i64 [[A:%.*]], 1
-; CHECK-NEXT:    [[DIFF_NEG:%.*]] = add i64 [[B_IDX]], -84
-; CHECK-NEXT:    ret i64 [[DIFF_NEG]]
+; CHECK-NEXT:    [[DOTNEG:%.*]] = add i64 [[B_IDX]], -84
+; CHECK-NEXT:    ret i64 [[DOTNEG]]
 ;
   %B = getelementptr inbounds [42 x i16], [42 x i16]* @Arr, i64 0, i64 %A
   %C = ptrtoint i16* %B to i64
   %G = sub i64 %C, ptrtoint (i16* getelementptr ([42 x i16], [42 x i16]* @Arr, i64 1, i64 0) to i64)
   ret i64 %G
 }
 
 @Arr_as1 = external addrspace(1) global [42 x i16]
 
 define i16 @test25_as1(i8 addrspace(1)* %P, i64 %A) {
 ; CHECK-LABEL: @test25_as1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[A:%.*]] to i16
 ; CHECK-NEXT:    [[B_IDX:%.*]] = shl nsw i16 [[TMP1]], 1
-; CHECK-NEXT:    [[DIFF_NEG:%.*]] = add i16 [[B_IDX]], -84
-; CHECK-NEXT:    ret i16 [[DIFF_NEG]]
+; CHECK-NEXT:    [[DOTNEG:%.*]] = add i16 [[B_IDX]], -84
+; CHECK-NEXT:    ret i16 [[DOTNEG]]
 ;
   %B = getelementptr inbounds [42 x i16], [42 x i16] addrspace(1)* @Arr_as1, i64 0, i64 %A
   %C = ptrtoint i16 addrspace(1)* %B to i16
   %G = sub i16 %C, ptrtoint (i16 addrspace(1)* getelementptr ([42 x i16], [42 x i16] addrspace(1)* @Arr_as1, i64 1, i64 0) to i16)
   ret i16 %G
 }
 
 define i32 @test26(i32 %x) {
 ; CHECK-LABEL: @test26(
-; CHECK-NEXT:    [[NEG:%.*]] = shl i32 -3, [[X:%.*]]
-; CHECK-NEXT:    ret i32 [[NEG]]
+; CHECK-NEXT:    [[SHL_NEG:%.*]] = shl i32 -3, [[X:%.*]]
+; CHECK-NEXT:    ret i32 [[SHL_NEG]]
 ;
   %shl = shl i32 3, %x
   %neg = sub i32 0, %shl
   ret i32 %neg
 }
 
 define i64 @test_neg_shl_sub(i64 %a, i64 %b) {
 ; CHECK-LABEL: @test_neg_shl_sub(
-; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[NEG:%.*]] = shl i64 [[TMP1]], 2
-; CHECK-NEXT:    ret i64 [[NEG]]
+; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub i64 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[MUL_NEG:%.*]] = shl i64 [[SUB_NEG]], 2
+; CHECK-NEXT:    ret i64 [[MUL_NEG]]
 ;
   %sub = sub i64 %a, %b
   %mul = shl i64 %sub, 2
   %neg = sub i64 0, %mul
   ret i64 %neg
 }
 
 define i64 @test_neg_shl_sub_extra_use1(i64 %a, i64 %b, i64* %p) {
;
   %mul = shl i64 %sub, 2
   store i64 %mul, i64* %p
   %neg = sub i64 0, %mul
   ret i64 %neg
 }
 
 define i64 @test_neg_shl_div(i64 %a) {
 ; CHECK-LABEL: @test_neg_shl_div(
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i64 [[A:%.*]], 3
-; CHECK-NEXT:    [[SHL:%.*]] = shl i64 [[DIV]], 2
-; CHECK-NEXT:    [[NEG:%.*]] = sub i64 0, [[SHL]]
-; CHECK-NEXT:    ret i64 [[NEG]]
+; CHECK-NEXT:    [[DIV_NEG:%.*]] = sdiv i64 [[A:%.*]], -3
+; CHECK-NEXT:    [[SHL_NEG:%.*]] = shl i64 [[DIV_NEG]], 2
+; CHECK-NEXT:    ret i64 [[SHL_NEG]]
 ;
   %div = sdiv i64 %a, 3
   %shl = shl i64 %div, 2
   %neg = sub i64 0, %shl
   ret i64 %neg
 }
 
 define i64 @test_neg_shl_zext_i1(i1 %a, i64 %b) {
 ; CHECK-LABEL: @test_neg_shl_zext_i1(
-; CHECK-NEXT:    [[EXT:%.*]] = zext i1 [[A:%.*]] to i64
-; CHECK-NEXT:    [[SHL:%.*]] = shl i64 [[EXT]], [[B:%.*]]
-; CHECK-NEXT:    [[NEG:%.*]] = sub i64 0, [[SHL]]
-; CHECK-NEXT:    ret i64 [[NEG]]
+; CHECK-NEXT:    [[EXT_NEG:%.*]] = sext i1 [[A:%.*]] to i64
+; CHECK-NEXT:    [[SHL_NEG:%.*]] = shl i64 [[EXT_NEG]], [[B:%.*]]
+; CHECK-NEXT:    ret i64 [[SHL_NEG]]
 ;
   %ext = zext i1 %a to i64
   %shl = shl i64 %ext, %b
   %neg = sub i64 0, %shl
   ret i64 %neg
 }
 
 define i64 @test_neg_shl_sext_i1(i1 %a, i64 %b) {
 ; CHECK-LABEL: @test_neg_shl_sext_i1(
-; CHECK-NEXT:    [[EXT:%.*]] = sext i1 [[A:%.*]] to i64
-; CHECK-NEXT:    [[SHL:%.*]] = shl i64 [[EXT]], [[B:%.*]]
-; CHECK-NEXT:    [[NEG:%.*]] = sub i64 0, [[SHL]]
-; CHECK-NEXT:    ret i64 [[NEG]]
+; CHECK-NEXT:    [[EXT_NEG:%.*]] = zext i1 [[A:%.*]] to i64
+; CHECK-NEXT:    [[SHL_NEG:%.*]] = shl i64 [[EXT_NEG]], [[B:%.*]]
+; CHECK-NEXT:    ret i64 [[SHL_NEG]]
 ;
   %ext = sext i1 %a to i64
   %shl = shl i64 %ext, %b
   %neg = sub i64 0, %shl
   ret i64 %neg
 }
 
 define i32 @test27(i32 %x, i32 %y) {
;
   %neg = sub i32 0, %z
   %mul = mul i32 %y, %neg
   %sub = sub i32 %x, %mul
   ret i32 %sub
 }
 
 define i64 @test29(i8* %foo, i64 %i, i64 %j) {
 ; CHECK-LABEL: @test29(
-; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 [[I:%.*]], [[J:%.*]]
-; CHECK-NEXT:    ret i64 [[TMP1]]
+; CHECK-NEXT:    [[DOTNEG:%.*]] = sub i64 [[I:%.*]], [[J:%.*]]
+; CHECK-NEXT:    ret i64 [[DOTNEG]]
 ;
   %gep1 = getelementptr inbounds i8, i8* %foo, i64 %i
   %gep2 = getelementptr inbounds i8, i8* %foo, i64 %j
   %cast1 = ptrtoint i8* %gep1 to i64
   %cast2 = ptrtoint i8* %gep2 to i64
   %sub = sub i64 %cast1, %cast2
   ret i64 %sub
 }
 
 define i64 @test30(i8* %foo, i64 %i, i64 %j) {
 ; CHECK-LABEL: @test30(
 ; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nsw i64 [[I:%.*]], 2
-; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 [[GEP1_IDX]], [[J:%.*]]
-; CHECK-NEXT:    ret i64 [[TMP1]]
+; CHECK-NEXT:    [[DOTNEG:%.*]] = sub i64 [[GEP1_IDX]], [[J:%.*]]
+; CHECK-NEXT:    ret i64 [[DOTNEG]]
 ;
   %bit = bitcast i8* %foo to i32*
   %gep1 = getelementptr inbounds i32, i32* %bit, i64 %i
   %gep2 = getelementptr inbounds i8, i8* %foo, i64 %j
   %cast1 = ptrtoint i32* %gep1 to i64
   %cast2 = ptrtoint i8* %gep2 to i64
   %sub = sub i64 %cast1, %cast2
   ret i64 %sub
 }
 
 define i16 @test30_as1(i8 addrspace(1)* %foo, i16 %i, i16 %j) {
 ; CHECK-LABEL: @test30_as1(
 ; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nsw i16 [[I:%.*]], 2
-; CHECK-NEXT:    [[TMP1:%.*]] = sub i16 [[GEP1_IDX]], [[J:%.*]]
-; CHECK-NEXT:    ret i16 [[TMP1]]
+; CHECK-NEXT:    [[DOTNEG:%.*]] = sub i16 [[GEP1_IDX]], [[J:%.*]]
+; CHECK-NEXT:    ret i16 [[DOTNEG]]
 ;
   %bit = bitcast i8 addrspace(1)* %foo to i32 addrspace(1)*
   %gep1 = getelementptr inbounds i32, i32 addrspace(1)* %bit, i16 %i
   %gep2 = getelementptr inbounds i8, i8 addrspace(1)* %foo, i16 %j
   %cast1 = ptrtoint i32 addrspace(1)* %gep1 to i16
   %cast2 = ptrtoint i8 addrspace(1)* %gep2 to i16
   %sub = sub i16 %cast1, %cast2
   ret i16 %sub
;
   %shl = shl <2 x i64> %A, <i64 3, i64 4>
   %sub = sub <2 x i64> %shl, %A
   ret <2 x i64> %sub
 }
 
 define <2 x i32> @test37(<2 x i32> %A) {
 ; CHECK-LABEL: @test37(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq <2 x i32> [[A:%.*]], <i32 -2147483648, i32 -2147483648>
-; CHECK-NEXT:    [[SUB:%.*]] = sext <2 x i1> [[TMP1]] to <2 x i32>
-; CHECK-NEXT:    ret <2 x i32> [[SUB]]
+; CHECK-NEXT:    [[DIV_NEG:%.*]] = sext <2 x i1> [[TMP1]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[DIV_NEG]]
 ;
   %div = sdiv <2 x i32> %A, <i32 -2147483648, i32 -2147483648>
   %sub = sub nsw <2 x i32> zeroinitializer, %div
   ret <2 x i32> %sub
 }
 
 define i32 @test38(i32 %A) {
 ; CHECK-LABEL: @test38(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[A:%.*]], -2147483648
-; CHECK-NEXT:    [[SUB:%.*]] = sext i1 [[TMP1]] to i32
-; CHECK-NEXT:    ret i32 [[SUB]]
+; CHECK-NEXT:    [[DIV_NEG:%.*]] = sext i1 [[TMP1]] to i32
+; CHECK-NEXT:    ret i32 [[DIV_NEG]]
 ;
   %div = sdiv i32 %A, -2147483648
   %sub = sub nsw i32 0, %div
   ret i32 %sub
 }
 
 define i16 @test40(i16 %a, i16 %b) {
 ; CHECK-LABEL: @test40(

 
 define i64 @test58([100 x [100 x i8]]* %foo, i64 %i, i64 %j) {
 ; Note the reassociate pass and another instcombine pass will further optimize this to
 ; "%sub = i64 %i, %j, ret i64 %sub"
 ; gep1 and gep2 have only one use
 ; CHECK-LABEL: @test58(
 ; CHECK-NEXT:    [[GEP2_OFFS:%.*]] = add i64 [[J:%.*]], 4200
 ; CHECK-NEXT:    [[GEP1_OFFS:%.*]] = add i64 [[I:%.*]], 4200
-; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 [[GEP1_OFFS]], [[GEP2_OFFS]]
-; CHECK-NEXT:    ret i64 [[TMP1]]
+; CHECK-NEXT:    [[DOTNEG:%.*]] = sub i64 [[GEP1_OFFS]], [[GEP2_OFFS]]
+; CHECK-NEXT:    ret i64 [[DOTNEG]]
 ;
   %gep1 = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 42, i64 %i
   %gep2 = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 42, i64 %j
   %cast1 = ptrtoint i8* %gep1 to i64
   %cast2 = ptrtoint i8* %gep2 to i64
   %sub = sub i64 %cast1, %cast2
   ret i64 %sub
 }