Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Incorrect fold of uadd.with.overflow with undef #42533

Closed
nunoplopes opened this issue Sep 1, 2019 · 13 comments
Closed

Incorrect fold of uadd.with.overflow with undef #42533

nunoplopes opened this issue Sep 1, 2019 · 13 comments
Assignees
Labels
bugzilla Issues migrated from bugzilla miscompilation

Comments

@nunoplopes
Copy link
Member

Bugzilla Link 43188
Resolution FIXED
Resolved on Jan 03, 2021 10:01
Version trunk
OS All
CC @LebedevRI,@RKSimon,@nikic,@regehr
Fixed by commit(s) 370608, f094d65

Extended Description

Alive2 complains about a transformation in Transforms/ConstProp/overflow-ops.ll:

define {i8, i1} @​uadd_undef() {
%0:
%t = uadd_overflow i8 142, undef
ret {i8, i1} %t
}
=>
define {i8, i1} @​uadd_undef() {
%0:
ret {i8, i1} undef
}
Transformation doesn't verify!
ERROR: Value mismatch

Example:

Source:
{i8, i1} %t = { #x8e (142, -114), #x0 (0) } [based on undef value]

Target:
Source value: { #x8e (142, -114), #x0 (0) } [based on undef value]
Target value: { #x00 (0), #x0 (0) }

In summary, there's no value in the source that the undef can take that allows uadd to return {0, 0}. To return 0, it has to overflow (unsigned), and hence the 2nd value would be 1.
Two valid return values I can think off: {%a, 0}; {undef, 1}.

@nunoplopes
Copy link
Member Author

assigned to @LebedevRI

@LebedevRI
Copy link
Member

Uhm, i thought we fixed that already?
Will take a look.

@nunoplopes
Copy link
Member Author

Just realized this is related to #​42209. Not sure constprop has a different code path than that bug.

@LebedevRI
Copy link
Member

Seems to originate from https://reviews.llvm.org/D55950

@LebedevRI
Copy link
Member

r370608

@nunoplopes
Copy link
Member Author

I've just added support for struct consts in Alive2, so we can verify these now :)
We now get:
define {i8, i1} @​uadd_undef() {
%0:
%t = uadd_overflow i8 142, undef
ret {i8, i1} %t
}
=>
define {i8, i1} @​uadd_undef() {
%0:
ret {i8, i1} { undef, 0 }
}

This is still incorrect. It has to be { undef, 1 }. You cannot get, for example, {0, 0} in the original program, while the optimized one can produce that.

@LebedevRI
Copy link
Member

Then instsimplify is wrong too :)
So uadd should produce { undef, 1 }
Anything else? What about sadd, ssub/usub, smul/umul?

@nikic
Copy link
Contributor

nikic commented Sep 1, 2019

I'm getting flashbacks to https://reviews.llvm.org/D63065 and AliveToolkit/alive2#71 here. I've been arguing that the proposed { undef, false } fold is illegal because alive's modeling was buggy (at the time). The original revision also suggests the results we should be using instead, namely { -1, 0 } for add an { 0, 0 } for sub.

@nunoplopes
Copy link
Member Author

Sorry for the delay; I was refactoring things in Alive so I could run all of overflow tests.
These are the failed tests:

define {i8, i1} @​uadd_undef() {
%0:
%t = uadd_overflow i8 142, undef
ret {i8, i1} %t
}
=>
define {i8, i1} @​uadd_undef() {
%0:
ret {i8, i1} { undef, 0 }
}
Transformation doesn't verify!
ERROR: Value mismatch

define {i8, i1} @​usub_undef() {
%0:
%t = usub_overflow i8 4, undef
ret {i8, i1} %t
}
=>
define {i8, i1} @​usub_undef() {
%0:
ret {i8, i1} { undef, 0 }
}
Transformation doesn't verify!
ERROR: Value mismatch

define {i8, i1} @​sadd_undef() {
%0:
%t = sadd_overflow i8 undef, 246
ret {i8, i1} %t
}
=>
define {i8, i1} @​sadd_undef() {
%0:
ret {i8, i1} { undef, 0 }
}
Transformation doesn't verify!
ERROR: Value mismatch

define {i8, i1} @​ssub_undef() {
%0:
%t = ssub_overflow i8 undef, 246
ret {i8, i1} %t
}
=>
define {i8, i1} @​ssub_undef() {
%0:
ret {i8, i1} { undef, 0 }
}

Ok, so {undef, 0} is not a correct result because you cannot have something like:
b = a + 42
=>
b = 41

Because that requires an overflow.
On a 2nd thought, {undef, 1} doesn't seem correct either, because you cannot have x + undef -> x with an overflow (the only way to produce x is without overflow).
So the only correct fold seems to be { %lhs, 0 } (we just make undef = 0). Not ideal, since it keeps the use of the operand, but I can't think of other correct fold.

@nunoplopes
Copy link
Member Author

I'm getting flashbacks to https://reviews.llvm.org/D63065 and
AliveToolkit/alive2#71 here. I've been arguing
that the proposed { undef, false } fold is illegal because alive's modeling
was buggy (at the time). The original revision also suggests the results we
should be using instead, namely { -1, 0 } for add an { 0, 0 } for sub.

Ah, your proposal sounds good, yes. It's basically saturating the operation.

@LebedevRI
Copy link
Member

So the only correct fold seems to be { %lhs, 0 } (we just make undef = 0).
For uadd/sadd/usub/ssub, yes?

Not ideal, since it keeps the use of the operand, but I can't think of other
correct fold.

I tried, and i'm not sure how to feed alive constant struct, like "{ undef, 0 }"
Am i correct that it can't parse it?

@nunoplopes
Copy link
Member Author

So the only correct fold seems to be { %lhs, 0 } (we just make undef = 0).
For uadd/sadd/usub/ssub, yes?

Not ideal, since it keeps the use of the operand, but I can't think of other
correct fold.

I tried, and i'm not sure how to feed alive constant struct, like "{ undef,
0 }"
Am i correct that it can't parse it?

Sorry, parsing in the alive tool isn't implemented yet. The only way to experiment with this is either using the alive-tv tool (takes 2 LLVM IR files), or the opt plugin.

@nikic
Copy link
Contributor

nikic commented Jan 3, 2021

The remaining issue is fixed by f094d65.

@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 10, 2021
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bugzilla Issues migrated from bugzilla miscompilation
Projects
None yet
Development

No branches or pull requests

3 participants