[InstCombine] ~(~X + Y) -> X - Y

[xbolva00]

Summary

Proof:
https://alive2.llvm.org/ce/z/4xharr

Solves PR47051

[xbolva00]

Add OneUse check

[lebedev.ri]

Let's not introduce any new unneeded one-use checks.

[RKSimon]

llvm/test/Transforms/InstCombine/not-add.ll

86

Please can you add an additional vector test with at least one undef element in the -1 constant

[xbolva00]

llvm/test/Transforms/InstCombine/not-add.ll

94

@lebedev.ri

not seems better than sub x, y so oneuse check is ok (?)

[spatel]

llvm/test/Transforms/InstCombine/not-add.ll

94

It's true that in some cases (for example, expensive FP ops), we have leaned toward a more restrictive one-use check.

In this case, however, I do not think that the relative analysis improvement of an xor vs. sub should limit the transform.

Reducing the number of operand uses and dependency chain could allow follow-on improvements.

[xbolva00]

llvm/test/Transforms/InstCombine/not-add.ll

94

Ok, thanks. Will drop it.

[xbolva00]

Drop one use check.
Added vector test with undef.

[spatel]

Please pre-commit the test file and upload diff with context.

llvm/test/Transforms/InstCombine/not-add.ll

125

Maximize the disaster potential of poison/undef by making this "add nsw nuw"?

[nikic]

llvm/test/Transforms/InstCombine/not-add.ll

94

Is this transform even legal without the one-use restriction? It *increases* the number of uses, as such it's not obvious that it the transform without one-use restriction is undef-safe.

[xbolva00]

Tests precommited.

[lebedev.ri]

llvm/test/Transforms/InstCombine/not-add.ll

94

Is this transform even legal without the one-use restriction? It *increases* the number of uses, as such it's not obvious that it the transform without one-use restriction is undef-safe.

Increased instruction count is only a legality issue
if it is increased for the computation of the value,
which isn't the case here.
Otherwise basically every instcombine fold would be invalid.

----------------------------------------
define i8 @src(i8 %x, i8 %y) {
%0:
  %notx = xor i8 %x, 255
  %a = add i8 %notx, %y
  %nota = xor i8 %a, 255
  call void @use(i8 %notx)
  call void @use(i8 %a)
  ret i8 %nota
}
=>
define i8 @tgt(i8 %x, i8 %y) {
%0:
  %notx = xor i8 %x, 255
  %a = add i8 %notx, %y
  %s = sub i8 %x, %y
  call void @use(i8 %notx)
  call void @use(i8 %a)
  ret i8 %s
}
Transformation seems to be correct!

[nikic]

llvm/test/Transforms/InstCombine/not-add.ll

94

After all this time, I'm probably still confused about undef semantics :)

Let me try to explain what I am concerned about: To simplify your example, let's say that %x = 0 and %y = undef. This leaves us with:

define i8 @src() {
  %a = add i8 255, undef
  %nota = xor i8 %a, 255
  call void @use(i8 %a)
  ret i8 %nota
}
=>
define i8 @tgt(i8 %y) {
  %a = add i8 255, undef
  %s = sub i8 0, undef
  call void @use(i8 %a)
  ret i8 %s
}

For @src, if we set undef=0, then %a = 255 and %nota = 0. In @tgt, we have two separate undefs that can be chosen independently, so we could end up with %a = 255 and %nota = 255 for example.

Is my interpretation incorrect? I've seen this issue come up in the past with transforms that increase the number of uses of values, but maybe I'm missing an important distinction here (e.g. is the fact that add 255, undef can be folded to undef relevant here? Do we assume that such a fold must happen?)

I don't think alive can be used to check multi-use correctness currently due to some implementation issue (https://github.com/AliveToolkit/alive2/issues/450).

[xbolva00]

llvm/test/Transforms/InstCombine/not-add.ll

94

Yeah, but there must be some rules otherwise almost all folds would be invalid.

[xbolva00]

llvm/test/Transforms/InstCombine/not-add.ll

94

cc @aqjune

[nikic]

llvm/test/Transforms/InstCombine/not-add.ll

94

While I would like to understand this, I also want to say that this shouldn't block this patch. Feel free to go ahead :)

[xbolva00]

llvm/test/Transforms/InstCombine/not-add.ll

94

Thanks. @spatel - is patch ok for you?

---

We know this is example of problematic case and needs freeze:
usub.sat(a, b) + b => a > b ? a : b
(increases number of uses of A)

Basically same thing happens here:
x = ...
y = ...
z = ~x + y
use(z)
a = ~(z)

>

x = ...
y = ...
z = ~x + y
use(z)
a = (x - y)

(increases number of uses of X and Y)

[spatel]

I agree that this looks wrong for the example with undef substituted in...but that also means that almost every instcombine that doesn't specify hasOneUse() is wrong!
But then how are we not miscompiling more often? We must be simplifying instructions with undefs before they can escape and cause trouble as @nikic hinted at?
@efriedma @regehr @nlopes - comments?

[efriedma]

@spatel The category of "undef-unsafe" transforms is relatively narrow; it's specifically transforms that use identities that don't work with possibly-undef inputs. For example, transforming x*2 -> x+x isn't legal because the bottom bit goes from zero to possibly-undef. Some people have referred to it as "increasing the number of uses", but really it's "using algebraic rules that don't work with undef". It doesn't have anything to do with the total number of uses of the value.

[aqjune]

To prove correctness of a transformation of expressions with constants and undefs, following these steps is sufficient:
(1) Replace an undef with a set of all possible values. For example, i8 undef is {0, 1, 2, ..., 255}.
(2) Evaluate each operation by pairwisely picking elements from operands' sets.
(3) If the final result is in a subset relation, the transformation is correct.

define i8 @src() {
  %a = add i8 255, undef // %a = {0, ... ,255}
  %nota = xor i8 %a, 255 // %nota = {0, ..., 255}
  call void @use(i8 %a)  // use({0, ..., 255})
  ret i8 %nota           // return {0, ..., 255}
}
=>
define i8 @tgt(i8 %y) {
  %a = add i8 255, undef
  %s = sub i8 0, undef
  call void @use(i8 %a) // use({0, ..., 255})
  ret i8 %s             // return {0, ..., 255}
}

Since the sets given to @use() as well as ret are equal between the source and target, this transformation is correct.

An example that converts mul x, 2 to add x, x:

// Let's assume that x = undef = {0, ..., 255}
y = mul x, 2 // y = {0, 2, 4, ..., 254}
=>
 y = add x, x // y = {0, 0+1, 1+0, 0+2, 1+1, ..., 255} = {0, ..., 255}

Since the target's y contains {1, 3, 5, ...}, which did not appear at the source, this transformation is incorrect. Similarly, a transformation that converts x * (a + b) --> x * a + x * b is incorrect if x was undef.

The statement 'each use of undef can see different values' is a simpler version of this. It is still effective however - bringing sets all the time isn't practical for reasoning, really (it should be very painful).

+--- (my previous statements before editing) ---+
Checking whether the number of uses is increased is a quick way to check whether the optimization is incorrect. If it replaces an old use that was guaranteed not to be undef before then it may yield a different value.
+--- ---+
->
Okay, I see that my statements were misleading...
The case where undef becomes problematic is when the transformation created new uses of a variable. The reason is that, since operations are pairwise operations on sets, introduction of new uses is likely to do something bad that did not appear under non-undef world. So, it can be a good indicator to see something can happen under undef.
However, it doesn't mean that introducing more uses is always bad - if we can prove that they are equivalent, it is still safe.

[aqjune]

llvm/test/Transforms/InstCombine/not-add.ll

94

Alive2 has an issue regarding this, but it works when the values are given as arguments to a single function call:
https://alive2.llvm.org/ce/z/evh2Ss
Until the bug is fixed, the trick above should work.

[aqjune]

llvm/test/Transforms/InstCombine/not-add.ll

94

@xbolva00 : The transformation seems okay, fortunately:
https://alive2.llvm.org/ce/z/eF6-Fg

[nikic]

@aqjune Thank you! So my mistake here is that it's not valid to use "let undef = xxx" type reasoning to construct counter examples, one has to always consider a superposition of all possible values for undef at the same time.

This LGTM :)

[xbolva00]

Ok, thanks.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(NotVal, m_LShr(m_Constant(C), m_Value(Y))) &&
       Type *EltTy = C->getType()->getScalarType();
       C = Constant::replaceUndefsWith(C, ConstantInt::getNullValue(EltTy));
       return BinaryOperator::CreateAShr(ConstantExpr::getNot(C), Y);
     }
 
     // ~(X + C) --> -(C + 1) - X
     if (match(Op0, m_Add(m_Value(X), m_Constant(C))))
       return BinaryOperator::CreateSub(ConstantExpr::getNeg(AddOne(C)), X);
+
+    // ~(~X + Y) --> X - Y
+    if (match(NotVal, m_c_Add(m_Not(m_Value(X)), m_Value(Y))))
+      return BinaryOperator::CreateWithCopiedFlags(Instruction::Sub, X, Y,
+                                                   NotVal);
   }
 
   // Use DeMorgan and reassociation to eliminate a 'not' op.
   Constant *C1;
   if (match(Op1, m_Constant(C1))) {
     Constant *C2;
     if (match(Op0, m_OneUse(m_Or(m_Not(m_Value(X)), m_Constant(C2))))) {
       // (~X | C2) ^ C1 --> ((X & ~C2) ^ -1) ^ C1 --> (X & ~C2) ^ ~C1

llvm/test/Transforms/InstCombine/not-add.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine -S < %s | FileCheck %s
 
 declare void @use(i8)
-declare i8 @get()
 
 define i8 @basic(i8 %x, i8 %y) {
 ; CHECK-LABEL: @basic(
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
-; CHECK-NEXT:    [[A:%.*]] = add i8 [[NOTX]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i8 [[A]], -1
+; CHECK-NEXT:    [[NOTA:%.*]] = sub i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i8 [[NOTA]]
 ;
   %notx = xor i8 %x, -1
   %a = add i8 %notx, %y
   %nota = xor i8 %a, -1
   ret i8 %nota
 }
 
 define i8 @basic_com_add(i8 %x, i8 %y) {
 ; CHECK-LABEL: @basic_com_add(
-; CHECK-NEXT:    [[NOTY:%.*]] = xor i8 [[Y:%.*]], -1
-; CHECK-NEXT:    [[A:%.*]] = add i8 [[NOTY]], [[X:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i8 [[A]], -1
+; CHECK-NEXT:    [[NOTA:%.*]] = sub i8 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[NOTA]]
 ;
   %noty = xor i8 %y, -1
   %a = add i8 %x, %noty
   %nota = xor i8 %a, -1
   ret i8 %nota
 }
 
 define i8 @basic_use_xor(i8 %x, i8 %y) {
 ; CHECK-LABEL: @basic_use_xor(
 ; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTX]])
-; CHECK-NEXT:    [[A:%.*]] = add i8 [[NOTX]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i8 [[A]], -1
+; CHECK-NEXT:    [[NOTA:%.*]] = sub i8 [[X]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i8 [[NOTA]]
 ;
   %notx = xor i8 %x, -1
   call void @use(i8 %notx)
   %a = add i8 %notx, %y
   %nota = xor i8 %a, -1
   ret i8 %nota
 }
 
 define i8 @basic_use_add(i8 %x, i8 %y) {
 ; CHECK-LABEL: @basic_use_add(
 ; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
 ; CHECK-NEXT:    [[A:%.*]] = add i8 [[NOTX]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[A]])
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i8 [[A]], -1
+; CHECK-NEXT:    [[NOTA:%.*]] = sub i8 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i8 [[NOTA]]
 ;
   %notx = xor i8 %x, -1
   %a = add i8 %notx, %y
   call void @use(i8 %a)
   %nota = xor i8 %a, -1
   ret i8 %nota
 }
 
 define i8 @basic_use_both(i8 %x, i8 %y) {
 ; CHECK-LABEL: @basic_use_both(
 ; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTX]])
 ; CHECK-NEXT:    [[A:%.*]] = add i8 [[NOTX]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[A]])
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i8 [[A]], -1
+; CHECK-NEXT:    [[NOTA:%.*]] = sub i8 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i8 [[NOTA]]
 ;
   %notx = xor i8 %x, -1
   call void @use(i8 %notx)
   %a = add i8 %notx, %y
   call void @use(i8 %a)
   %nota = xor i8 %a, -1
   ret i8 %nota
 }
 
 define i8 @basic_preserve_nsw(i8 %x, i8 %y) {
 ; CHECK-LABEL: @basic_preserve_nsw(
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
-; CHECK-NEXT:    [[A:%.*]] = add nsw i8 [[NOTX]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i8 [[A]], -1
+; CHECK-NEXT:    [[NOTA:%.*]] = sub nsw i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i8 [[NOTA]]
 ;
   %notx = xor i8 %x, -1
   %a = add nsw i8 %notx, %y
   %nota = xor i8 %a, -1
   ret i8 %nota
 }
 
 define i8 @basic_preserve_nuw(i8 %x, i8 %y) {
 ; CHECK-LABEL: @basic_preserve_nuw(
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
-; CHECK-NEXT:    [[A:%.*]] = add nuw i8 [[NOTX]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i8 [[A]], -1
+; CHECK-NEXT:    [[NOTA:%.*]] = sub nuw i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i8 [[NOTA]]
 ;
   %notx = xor i8 %x, -1
   %a = add nuw i8 %notx, %y
   %nota = xor i8 %a, -1
   ret i8 %nota
 }
 
 define i8 @basic_preserve_nuw_nsw(i8 %x, i8 %y) {
 ; CHECK-LABEL: @basic_preserve_nuw_nsw(
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
-; CHECK-NEXT:    [[A:%.*]] = add nuw nsw i8 [[NOTX]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i8 [[A]], -1
+; CHECK-NEXT:    [[NOTA:%.*]] = sub nuw nsw i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i8 [[NOTA]]
 ;
   %notx = xor i8 %x, -1
   %a = add nuw nsw i8 %notx, %y
   %nota = xor i8 %a, -1
   ret i8 %nota
 }
 
 define <4 x i32> @vector_test(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @vector_test(
-; CHECK-NEXT:    [[NOTX:%.*]] = xor <4 x i32> [[X:%.*]], <i32 -1, i32 -1, i32 -1, i32 -1>
-; CHECK-NEXT:    [[A:%.*]] = add <4 x i32> [[NOTX]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor <4 x i32> [[A]], <i32 -1, i32 -1, i32 -1, i32 -1>
+; CHECK-NEXT:    [[NOTA:%.*]] = sub <4 x i32> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <4 x i32> [[NOTA]]
 ;
   %notx = xor <4 x i32> %x, <i32 -1, i32 -1, i32 -1, i32 -1>
   %a = add <4 x i32> %notx, %y
   %nota = xor <4 x i32> %a, <i32 -1, i32 -1, i32 -1, i32 -1>
   ret <4 x i32> %nota
 }
 
 define <4 x i32> @vector_test_undef(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @vector_test_undef(
-; CHECK-NEXT:    [[NOTX:%.*]] = xor <4 x i32> [[X:%.*]], <i32 -1, i32 undef, i32 undef, i32 -1>
-; CHECK-NEXT:    [[A:%.*]] = add <4 x i32> [[NOTX]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor <4 x i32> [[A]], <i32 -1, i32 -1, i32 undef, i32 undef>
+; CHECK-NEXT:    [[NOTA:%.*]] = sub <4 x i32> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <4 x i32> [[NOTA]]
 ;
   %notx = xor <4 x i32> %x, <i32 -1, i32 undef, i32 undef, i32 -1>
   %a = add <4 x i32> %notx, %y
   %nota = xor <4 x i32> %a, <i32 -1, i32 -1, i32 undef, i32 undef>
   ret <4 x i32> %nota
 }
 
 
 define <4 x i32> @vector_test_undef_nsw_nuw(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @vector_test_undef_nsw_nuw(
-; CHECK-NEXT:    [[NOTX:%.*]] = xor <4 x i32> [[X:%.*]], <i32 -1, i32 undef, i32 undef, i32 -1>
-; CHECK-NEXT:    [[A:%.*]] = add nuw nsw <4 x i32> [[NOTX]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor <4 x i32> [[A]], <i32 -1, i32 -1, i32 undef, i32 undef>
+; CHECK-NEXT:    [[NOTA:%.*]] = sub nuw nsw <4 x i32> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <4 x i32> [[NOTA]]
 ;
   %notx = xor <4 x i32> %x, <i32 -1, i32 undef, i32 undef, i32 -1>
   %a = add nsw nuw <4 x i32> %notx, %y
   %nota = xor <4 x i32> %a, <i32 -1, i32 -1, i32 undef, i32 undef>
   ret <4 x i32> %nota
 }