Proof:
https://alive2.llvm.org/ce/z/4xharr
Solves PR47051
Details
Details
- Reviewers
spatel nikic - Commits
- rGc2f010131013: [InstCombine] ~(~X + Y) -> X - Y
Diff Detail
Diff Detail
Event Timeline
| 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 | |
| llvm/test/Transforms/InstCombine/not-add.ll | ||
|---|---|---|
| 94 | not seems better than sub x, y so oneuse check is ok (?) | |
| 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. | |
| llvm/test/Transforms/InstCombine/not-add.ll | ||
|---|---|---|
| 94 | Ok, thanks. Will drop it. | |
Comment Actions
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"? | |
| 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. | |
| llvm/test/Transforms/InstCombine/not-add.ll | ||
|---|---|---|
| 94 |
Increased instruction count is only a legality issue ----------------------------------------
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! | |
| 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). | |
| llvm/test/Transforms/InstCombine/not-add.ll | ||
|---|---|---|
| 94 | Yeah, but there must be some rules otherwise almost all folds would be invalid. | |
| 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 :) | |
| 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: Basically same thing happens here: >x = ... (increases number of uses of X and Y) | |
Comment Actions
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?
Comment Actions
@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.
Comment Actions
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.
| 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: | |
| llvm/test/Transforms/InstCombine/not-add.ll | ||
|---|---|---|
| 94 | @xbolva00 : The transformation seems okay, fortunately: | |
Comment Actions
@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 :)
Please can you add an additional vector test with at least one undef element in the -1 constant