This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by xbolva00 on Aug 8 2020, 5:12 PM.

Diff Detail

Event Timeline

xbolva00 created this revision.Aug 8 2020, 5:12 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 8 2020, 5:12 PM
xbolva00 requested review of this revision.Aug 8 2020, 5:12 PM
xbolva00 updated this revision to Diff 284157.Aug 8 2020, 5:20 PM

Add OneUse check

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

RKSimon added a subscriber: RKSimon.Aug 9 2020, 1:07 AM
RKSimon added inline comments.
llvm/test/Transforms/InstCombine/not-add.ll
87

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

xbolva00 added inline comments.Aug 9 2020, 1:56 AM
llvm/test/Transforms/InstCombine/not-add.ll
95

@lebedev.ri

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

spatel added inline comments.Aug 9 2020, 6:13 AM
llvm/test/Transforms/InstCombine/not-add.ll
95

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 added inline comments.Aug 9 2020, 6:16 AM
llvm/test/Transforms/InstCombine/not-add.ll
95

Ok, thanks. Will drop it.

xbolva00 updated this revision to Diff 284193.Aug 9 2020, 6:25 AM

Drop one use check.
Added vector test with undef.

spatel added a comment.Aug 9 2020, 6:47 AM

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

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

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

nikic added a subscriber: nikic.Aug 9 2020, 7:08 AM
nikic added inline comments.
llvm/test/Transforms/InstCombine/not-add.ll
95

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 updated this revision to Diff 284194.Aug 9 2020, 7:09 AM

Tests precommited.

xbolva00 marked an inline comment as done.Aug 9 2020, 7:10 AM
lebedev.ri added inline comments.Aug 9 2020, 7:23 AM
llvm/test/Transforms/InstCombine/not-add.ll
95

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 added inline comments.Aug 9 2020, 7:50 AM
llvm/test/Transforms/InstCombine/not-add.ll
95

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 added inline comments.Aug 10 2020, 6:51 AM
llvm/test/Transforms/InstCombine/not-add.ll
95

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

xbolva00 added inline comments.
llvm/test/Transforms/InstCombine/not-add.ll
95
nikic added inline comments.Aug 10 2020, 12:00 PM
llvm/test/Transforms/InstCombine/not-add.ll
95

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 added inline comments.Aug 10 2020, 12:16 PM
llvm/test/Transforms/InstCombine/not-add.ll
95

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)

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?

@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 added a comment.EditedAug 10 2020, 11:11 PM

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 added inline comments.Aug 10 2020, 11:13 PM
llvm/test/Transforms/InstCombine/not-add.ll
95

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 added inline comments.Aug 11 2020, 12:27 AM
llvm/test/Transforms/InstCombine/not-add.ll
95

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

nikic accepted this revision.Aug 11 2020, 1:01 AM

@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 :)

This revision is now accepted and ready to land.Aug 11 2020, 1:01 AM
xbolva00 updated this revision to Diff 284613.Aug 11 2020, 2:04 AM

Ok, thanks.

This revision was automatically updated to reflect the committed changes.