[InstCombine] enhance freelyNegateValue() by handling 'not'

[spatel]

Summary

This patch extends D77230. If we have a 'not' instruction inside a negated expression, we can ignore extra uses of that op because the negation has a one-to-one replacement: negate becomes increment.

Alive2 examples of the test cases:
http://volta.cs.utah.edu:8080/z/T5-u9P
http://volta.cs.utah.edu:8080/z/eT89L6

[spatel]

Note that we don't see test diffs for simpler cases because we already handle this related pattern:

// C - ~X == X + (1+C)
if (match(Op1, m_Not(m_Value(X))))
  return BinaryOperator::CreateAdd(X, AddOne(C));

[lebedev.ri]

LG
I'll attempt to resurrect Negator patch..

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

Value *InstCombiner::freelyNegateValue(Value *V) {
   // 0-(A ashr (BW-1))  =>  A lshr (BW-1)
   case Instruction::AShr:
     if (match(I->getOperand(1), m_SpecificInt(BitWidth - 1)))
       return Builder.CreateLShr(
           I->getOperand(0), I->getOperand(1),
           I->getName() + ".neg", cast<BinaryOperator>(I)->isExact());
     return nullptr;
 
+  // Negation is equivalent to bitwise-not + 1.
+  case Instruction::Xor: {
+    // Special case for negate of 'not' - replace with increment:
+    // 0 - (~A)  =>  ((A ^ -1) ^ -1) + 1  =>  A + 1
+    Value *A;
+    if (match(I, m_Not(m_Value(A))))
+      return Builder.CreateAdd(A, ConstantInt::get(A->getType(), 1),
+                               I->getName() + ".neg");
+
+    // General case xor (not a 'not') requires creating a new xor, so this has a
+    // one-use limitation:
+    // 0 - (A ^ C)  =>  ((A ^ C) ^ -1) + 1  =>  A ^ ~C + 1
+    Constant *C;
+    if (match(I, m_OneUse(m_Xor(m_Value(A), m_Constant(C))))) {
+      Value *Xor = Builder.CreateXor(A, ConstantExpr::getNot(C));
+      return Builder.CreateAdd(Xor, ConstantInt::get(Xor->getType(), 1),
+                               I->getName() + ".neg");
+    }
+    return nullptr;
+  }
+
   default:
     break;
   }
 
   // TODO: The "sub" pattern below could also be applied without the one-use
   // restriction. Not allowing it for now in line with existing behavior.
   if (!I->hasOneUse())
     return nullptr;
 
   switch (I->getOpcode()) {
   // 0-(A-B)  =>  B-A
   case Instruction::Sub:
     return Builder.CreateSub(
         I->getOperand(1), I->getOperand(0), I->getName() + ".neg");
 
-  // Negation is equivalent to bitwise-not + 1:
-  // 0 - (A ^ C)  =>  ((A ^ C) ^ -1) + 1  =>  A ^ ~C + 1
-  case Instruction::Xor: {
-    Constant *C;
-    if (match(I->getOperand(1), m_Constant(C))) {
-      Value *Xor = Builder.CreateXor(I->getOperand(0), ConstantExpr::getNot(C));
-      return Builder.CreateAdd(Xor, ConstantInt::get(Xor->getType(), 1),
-                               I->getName() + ".neg");
-    }
-    return nullptr;
-  }
-
   // 0-(A sdiv C)  =>  A sdiv (0-C)  provided the negation doesn't overflow.
   case Instruction::SDiv: {
     Constant *C = dyn_cast<Constant>(I->getOperand(1));
     if (C && !C->containsUndefElement() && C->isNotMinSignedValue() &&
         C->isNotOneValue())
       return Builder.CreateSDiv(I->getOperand(0), ConstantExpr::getNeg(C),
           I->getName() + ".neg", cast<BinaryOperator>(I)->isExact());
     return nullptr;

llvm/test/Transforms/InstCombine/sub-of-negatible.ll

;
   %r = sub i4 0, %s
   ret i4 %r
 }
 
 define i8 @negate_shl_not_uses(i8 %x, i8 %y) {
 ; CHECK-LABEL: @negate_shl_not_uses(
 ; CHECK-NEXT:    [[O:%.*]] = xor i8 [[X:%.*]], -1
 ; CHECK-NEXT:    call void @use8(i8 [[O]])
-; CHECK-NEXT:    [[S:%.*]] = shl i8 [[O]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = sub i8 0, [[S]]
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    [[O_NEG:%.*]] = add i8 [[X]], 1
+; CHECK-NEXT:    [[S_NEG:%.*]] = shl i8 [[O_NEG]], [[Y:%.*]]
+; CHECK-NEXT:    ret i8 [[S_NEG]]
 ;
   %o = xor i8 %x, -1
   call void @use8(i8 %o)
   %s = shl i8 %o, %y
   %r = sub i8 0, %s
   ret i8 %r
 }
 
 define <2 x i4> @negate_mul_not_uses_vec(<2 x i4> %x, <2 x i4> %y) {
 ; CHECK-LABEL: @negate_mul_not_uses_vec(
 ; CHECK-NEXT:    [[O:%.*]] = xor <2 x i4> [[X:%.*]], <i4 -1, i4 -1>
 ; CHECK-NEXT:    call void @use_v2i4(<2 x i4> [[O]])
-; CHECK-NEXT:    [[S:%.*]] = mul <2 x i4> [[O]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = sub <2 x i4> zeroinitializer, [[S]]
-; CHECK-NEXT:    ret <2 x i4> [[R]]
+; CHECK-NEXT:    [[O_NEG:%.*]] = add <2 x i4> [[X]], <i4 1, i4 1>
+; CHECK-NEXT:    [[S_NEG:%.*]] = mul <2 x i4> [[O_NEG]], [[Y:%.*]]
+; CHECK-NEXT:    ret <2 x i4> [[S_NEG]]
 ;
   %o = xor <2 x i4> %x, <i4 -1, i4 -1>
   call void @use_v2i4(<2 x i4> %o)
   %s = mul <2 x i4> %o, %y
   %r = sub <2 x i4> zeroinitializer, %s
   ret <2 x i4> %r
 }