Sanjoy Das via llvm-dev
2016-Oct-20 01:55 UTC
[llvm-dev] RFC: Killing undef and spreading poison
Hi Alexandre, On Wed, Oct 19, 2016 at 6:27 PM, Alexandre Isoard <alexandre.isoard at gmail.com> wrote:> Really interesting read. I am perplexed now, and am not even sure what is > the meaning of undef anymore.Welcome aboard. :)> Example (unrelated to your blog post, but still weird): > %x = sext i1 undef to i2 > > I understand that I can replace it by either of: > %x = i2 0 > %x = i2 -1 > > But can I replace it by: > %x = i2 undef > > I would have said no, at first sight, because -2 and 1 should not be > possible values. > But if I look at each bit, independently, each one can be either 0 or 1. > Then, if we > forget their "entanglement" (like we do shamelessly with xor %x, %x), and > then > concatenate them back together, we get the i2 undef...Yes. If your definition of sext is: sext(x): if x == 0 then 0 else -1 then things are fine. However, if your definition of sext is something like: sext(x): t = zext x result = 0 for i = 0 to bitwidth: result |= t << i; return result then sext(undef) is, in fact, undef for the reason you highlighted. In general, you cannot increase the number of uses of undef and preserve semantics. You could say that the "zext x" above is "either 0 or 1" (i.e. it implicitly freezes its input), but then e.g. (in todays scheme) "trunc(zext(x))" cannot be replaced by "x". -- Sanjoy
Mehdi Amini via llvm-dev
2016-Oct-20 03:29 UTC
[llvm-dev] RFC: Killing undef and spreading poison
> On Oct 19, 2016, at 6:55 PM, Sanjoy Das <sanjoy at playingwithpointers.com> wrote: > > Hi Alexandre, > > On Wed, Oct 19, 2016 at 6:27 PM, Alexandre Isoard > <alexandre.isoard at gmail.com> wrote: >> Really interesting read. I am perplexed now, and am not even sure what is >> the meaning of undef anymore. > > Welcome aboard. :) > >> Example (unrelated to your blog post, but still weird): >> %x = sext i1 undef to i2 >> >> I understand that I can replace it by either of: >> %x = i2 0 >> %x = i2 -1 >> >> But can I replace it by: >> %x = i2 undefMy understanding has always been: you can pick whatever value for undef, but you have to pick one. Sext is defined by LangRef as: The ‘sext‘ instruction performs a sign extension by copying the sign bit (highest order bit) of the value until it reaches the bit size of the type ty2. When sign extending from i1, the extension always results in -1 or 0. So whatever value you pick for `%x = sext i1 undef to i2`, you can only produce -1 and 0, replacing with `%x = i2 undef` seems to be invalid as I read LangRef.>> I would have said no, at first sight, because -2 and 1 should not be >> possible values. >> But if I look at each bit, independently, each one can be either 0 or 1. >> Then, if we >> forget their "entanglement" (like we do shamelessly with xor %x, %x), and >> then >> concatenate them back together, we get the i2 undef... > > Yes. > > If your definition of sext is: > > sext(x): > if x == 0 then 0 else -1 > > then things are fine. However, if your definition of sext is something like: > > sext(x): > t = zext x > result = 0 > for i = 0 to bitwidth: > result |= t << i; > return resultI don’t understand this definition of sext? Are you trying to express that we will copy the sign one bit at a time, and so every `new` bit is a new “read” of the undef sign?> > then sext(undef) is, in fact, undef for the reason you highlighted. > In general, you cannot increase the number of uses of undef and > preserve semantics. > > You could say that the "zext x" above is "either 0 or 1" (i.e. it > implicitly freezes its input), but then e.g. (in todays scheme) > "trunc(zext(x))" cannot be replaced by "x”.I didn’t get this last part? — Mehdi
Sanjoy Das via llvm-dev
2016-Oct-20 03:40 UTC
[llvm-dev] RFC: Killing undef and spreading poison
Hi Mehdi, On Wed, Oct 19, 2016 at 8:29 PM, Mehdi Amini <mehdi.amini at apple.com> wrote:>> sext(x): >> t = zext x >> result = 0 >> for i = 0 to bitwidth: >> result |= t << i; >> return result > > I don’t understand this definition of sext? > Are you trying to express that we will copy the sign one bit at a time, and so every `new` bit is a new “read” of the undef sign?Yes, that's what I was trying to express. But, as you pointed out, that isn't the actual definition of sext as specified in the lang ref.>> then sext(undef) is, in fact, undef for the reason you highlighted. >> In general, you cannot increase the number of uses of undef and >> preserve semantics. >> >> You could say that the "zext x" above is "either 0 or 1" (i.e. it >> implicitly freezes its input), but then e.g. (in todays scheme) >> "trunc(zext(x))" cannot be replaced by "x”. > > I didn’t get this last part?If zext(x) is defined to always produce a concrete value (that is, zext(undef) is either 0 or 1), then this program can never fail the assert: %t = zext i1 %some_val to i2 %t.trunc = trunc(%t) to i1 assert(%t.trunc == %t.trunc) even if %some_val is undef. However, if you get rid of the trunc/zext pair, and transform this to: assert(%some_val == %some_val) then it can fail the assert if %some_val is undef. For the transform above to be allowed, zext(undef) needs to retain the "undefness" in its result (that is, it needs to be a non-deterministic choice between 0 and 1 at each use site). Does that answer your question, or were you asking something else? -- Sanjoy