3 ms·
This is a great article. I'm really enjoying some of the compiler optimizations I'm seeing. It's an area not oft explored for me. However, I'm having a bit of
by codyb 12y ago
This is a great article. I'm really enjoying some of the compiler optimizations I'm seeing. It's an area not oft explored for me.
However, I'm having a bit of an issue understanding what the compiler is doing here, at the beginning of the article.
If someone can explain, it'd be appreciated.
FTA:
A post-classical compiler, on the other hand, might perform the following analysis:
The first four times through the loop, the function might return true.
When i is 4, the code performs undefined behavior. Since undefined behavior lets me do anything I want, I can totally ignore that case and proceed on the assumption that i is never 4. (If the assumption is violated, then something unpredictable happens, but that's okay, because undefined behavior grants me permission to be unpredictable.)
The case where i is 5 never occurs, because in order to get there, I first have to get through the case where i is 4, which I have already assumed cannot happen.
Therefore, all legal code paths return true.
As a result, a post-classical compiler can optimize the function to
bool exists_in_table(int v)
{
return true;
}
I see might return true. Ignored. And never happens.
I think the idea is that since i=4 is ignored, and the loop goes while i <= 4, you can never reach the return false statement? That's my understanding, I'm just not confident on it.
- dkersten 12y agoThe first example took me a few reads to get too. Basically, since i=4 causes undefined behaviour, the compiler assumes that it can't possibly happen[1] and the only way that it can't happen is if one of the prior (i < 4) checks were true. Therefore all legal code paths (ie all code paths that don't result in undefined behaviour) return true. So it optimises it to simply return true. Because otherwise i=4 would have happened, but that's undefined, so impossible[1] [1] but if it does happen, that's ok, because that would be undefined behaviour, which allows the compiler to do whatever it feels like anyway
- codyb 12y agoOkay, yea, that makes sense. Awesome. Thanks.
- deleted 12y ago[deleted]
- ben0x539 12y agoLook at it as the compiler unrolling the loop to: if (table[0] == v) return true; if (table[1] == v) return true; if (table[2] == v) return true; if (table[3] == v) return true; undefined_behavior(); return false; Since the compiler is allowed to assume undefined behavior never happens, and you certainly can't expect control to pass through undefined behavior and then do something reasonable like execute the next statement, the compiler can just assume that control exits the function before it gets to the undefined behavior, and the only way to do that is to take one of these `return true;` statements. It can't tell you which table element supposedly contains v, but no one asked for that, so all these `return`s serve equally well.
- codyb 12y agoBeautiful. That makes it very simple to understand. Cheers mate.
- aylons 12y agoThe loop searches for a true comparison until it reaches one, them stop. And, i=4 is not ignored by the compiler, it is declared as undefined behaviour. What the compiler MAY do is to always return true. In this cause, it will always return true, either because it reached the 5th value ([4]), or because there was a match in the first 4 values. As the result will always be true, the compiler may then simply return true and skip the loop.
- PeterisP 12y agoThe mental model I'm seeing there is simple - the compiler is allowed to assume a 'contract' of "The caller will ensure that the function is called only such argument values that the undefined condition is never reached". In this particular case, the 'contract' and the actual code imply that "The only allowed values of 'int v' are those that actually are found in the table"; for those values the function correctly returns true; and for all the possible 'illegal' arguments any and every possible behavior would be correct.