3 ms·

To be clear, the compiler is not forbidden from optimizing `always_returns_true` to unconditionally return true. After all, undefined behavior can cause anyth

by comex 7y ago

To be clear, the compiler is not forbidden from optimizing `always_returns_true` to unconditionally return true. After all, undefined behavior can cause anything to happen, and that includes returning true. Normally LLVM would perform exactly that optimization. But in this case `always_returns_true` is inlined first, so it becomes something like `undef < 150 || undef > 120`; LLVM propagates the `undef` outward through the expression until the whole condition is `undef`, and then it arbitrarily picks that the condition should be false. But `always_returns_true` is not an example of how this particular undefined behavior can be useful as an optimization, merely an example of how it can be dangerous. For some examples of how it can be useful: - Document describing the origins of `undef` in LLVM: http://nondot.org/sabre/LLVMNotes/UndefinedValue.txt http://nondot.org/sabre/LLVMNotes/UndefinedValue.txt Basically, it helps to be able to replace "cond ? some_value : undef" with "some_value", especially when the code has been transformed to SSA form. - Some architectures literally have a 257th possible value, like Itanium [1] [2]. On Itanium, every register can be set to "Not a Thing", i.e. uninitialized, and the CPU will trap if you try to store such a value to memory. Ironically, NaT was created in order to make the CPU's behavior more defined in a certain case, or at least more predictable... argh, I'm too tired to explain it properly; look at section 2.3.1 of [2] for a somewhat confusing explanation. [1] https://devblogs.microsoft.com/oldnewthing/20040119-00/?p=41003 https://devblogs.microsoft.com/oldnewthing/20040119-00/?p=41... [2] https://www.cse.unsw.edu.au/~cs9244/06/seminars/07-gaol.pdf https://www.cse.unsw.edu.au/~cs9244/06/seminars/07-gaol.pdf

martinhath 7y ago
I _think_ I understand the rationale behind `undef` in LLVM, but I still think it's a bad one, since it can, and does, lead to very surprising behaviour. > LLVM propagates the `undef` outward through the expression until the whole condition is `undef`, and then it arbitrarily picks that the condition should be false. I think this illustrates what I find counter-intuitive about this whole mess; any function of `undef` shouldn't itself be `undef`. `undef < undef` is false in my head. `undef < 150` is just unknown, not undefined, since we don't know what `undef` is. > Basically, it helps to be able to replace "cond ? some_value : undef" with "some_value" This feels really contrived; in what setting would this actually be useful?
- comex 7y ago
  > This feels really contrived; in what setting would this actually be useful? The text file I linked to explains it in more detail, so I'll defer to that. > I think this illustrates what I find counter-intuitive about this whole mess; any function of `undef` shouldn't itself be `undef`. `undef < undef` is false in my head. `undef < 150` is just unknown, not undefined, since we don't know what `undef` is. Except that for `undef < undef`, what if they're two different undefs? You would have to track each potentially uninitialized value separately. And then the optimizer would want to strategically choose values for the different undefs – e.g. "we want to merge 'cond ? some_value : undef123' with 'some_value', so let's set undef123 equal to some_value... except that could negatively impact this other section of code that uses it". It's certainly possible, but it would make the optimizer's job somewhat harder.
ralfjung 7y ago
Thanks, I have added a link to that LLVM document to the post!
comex 7y ago
Since it's too late to edit my comment, I'm replying to note I was a bit off. `undef` actually doesn't propagate all the way to the conditional; instead, LLVM replaces `undef < 150` with `false`, and the same for `undef > 120`, and then `false || false` is simplified to `false`. In C, comparing indeterminate values is undefined behavior, so LLVM would be allowed to replace `undef < 150` with `undef`, but it seems that LLVM itself has slightly stronger semantics. See also: https://llvm.org/docs/LangRef.html#undefined-values https://llvm.org/docs/LangRef.html#undefined-values

by comex 7y ago

martinhath 7y ago

I _think_ I understand the rationale behind `undef` in LLVM, but I still think it's a bad one, since it can, and does, lead to very surprising behaviour. > LLVM propagates the `undef` outward through the expression until the whole condition is `undef`, and then it arbitrarily picks that the condition should be false. I think this illustrates what I find counter-intuitive about this whole mess; any function of `undef` shouldn't itself be `undef`. `undef < undef` is false in my head. `undef < 150` is just unknown, not undefined, since we don't know what `undef` is. > Basically, it helps to be able to replace "cond ? some_value : undef" with "some_value" This feels really contrived; in what setting would this actually be useful?

comex 7y ago
> This feels really contrived; in what setting would this actually be useful? The text file I linked to explains it in more detail, so I'll defer to that. > I think this illustrates what I find counter-intuitive about this whole mess; any function of `undef` shouldn't itself be `undef`. `undef < undef` is false in my head. `undef < 150` is just unknown, not undefined, since we don't know what `undef` is. Except that for `undef < undef`, what if they're two different undefs? You would have to track each potentially uninitialized value separately. And then the optimizer would want to strategically choose values for the different undefs – e.g. "we want to merge 'cond ? some_value : undef123' with 'some_value', so let's set undef123 equal to some_value... except that could negatively impact this other section of code that uses it". It's certainly possible, but it would make the optimizer's job somewhat harder.

ralfjung 7y ago

Thanks, I have added a link to that LLVM document to the post!

comex 7y ago

Since it's too late to edit my comment, I'm replying to note I was a bit off. `undef` actually doesn't propagate all the way to the conditional; instead, LLVM replaces `undef < 150` with `false`, and the same for `undef > 120`, and then `false || false` is simplified to `false`. In C, comparing indeterminate values is undefined behavior, so LLVM would be allowed to replace `undef < 150` with `undef`, but it seems that LLVM itself has slightly stronger semantics. See also: https://llvm.org/docs/LangRef.html#undefined-values https://llvm.org/docs/LangRef.html#undefined-values