by nayuki | 2025-04-02 03:30:20+00:00
Reference: https://c9x.me/compile/bib/ubc.pdf#page=4

Both the parent comment and the referenced paper fail to mention the out-of-bounds access of d[16]. At best, the paper says:

> The compiler assumed that no out-of-bounds access to d would happen, and from that derived that k is at most 15 after the access

Here is my analysis. By unrolling the loop and tracing the statements and values, we get:

k = 0; dd = d[k]; k is 0; k < 16 is true; loop body; ++k; k is 1; dd = d[k]; k is 1; k < 16 is true; loop body; ++k; k is 2; dd = d[k]; k is 2; k < 16 is true; loop body; ++k; k is 3; dd = d[k]; k is 3; k < 16 is true; loop body; ++k; k is 4; dd = d[k]; k is 4; k < 16 is true; loop body; ++k; k is 5; dd = d[k]; k is 5; k < 16 is true; loop body; ++k; k is 6; dd = d[k]; k is 6; k < 16 is true; loop body; ++k; k is 7; dd = d[k]; k is 7; k < 16 is true; loop body; ++k; k is 8; dd = d[k]; k is 8; k < 16 is true; loop body; ++k; k is 9; dd = d[k]; k is 9; k < 16 is true; loop body; ++k; k is 10; dd = d[k]; k is 10; k < 16 is true; loop body; ++k; k is 11; dd = d[k]; k is 11; k < 16 is true; loop body; ++k; k is 12; dd = d[k]; k is 12; k < 16 is true; loop body; ++k; k is 13; dd = d[k]; k is 13; k < 16 is true; loop body; ++k; k is 14; dd = d[k]; k is 14; k < 16 is true; loop body; ++k; k is 15; dd = d[k]; k is 15; k < 16 is true; loop body; ++k; k is 16; dd = d[k]; OUT OF BOUNDS!

As long as we enter the loop, the loop must eventually execute undefined behavior. Furthermore, every instance of testing `k < 16` is true before we hit UB. Therefore it can be simplified to true without loss of functionality, because after we hit UB, we are allowed to do absolutely anything. In my ancestor post where I said that any mistake, no matter how small, can have unbounded consequences, I fully mean it and believe it.

Please stop blaming the compiler. The problem is buggy code. Either fix the code, or fix the language specification so that wild reads either return an arbitrary value or crashes cleanly at that instruction.

Note that we cannot change the spec to give definite behavior to writing out of bounds, because it is always possible to overwrite something critical like a return address or an instruction, and then it is literally undefined behavior and anything can happen.

> I mean thats just sort of nuts, how do you loop over an array then in an UB free manner?

The code is significantly transformed, but the nasty behavior can be prevented by designing code that does not read out of bounds! The trick is that the test `k < 16` must be false before any attempt to read/write `d[k]`. Which 99.99% of programmers get right, especially by writing a loop in the standard way and not in the obtuse way demonstrated in the referenced code. The obvious and correct implementation is:

for (int k = 0; k < 16; k++) { int dd = d[k]; satd += dd < 0 ? -dd : dd; }

The fact that the SPEC code chose to load `d[k]` before checking that `k` is still in bounds is an overly clever, counterproductive "jumping the gun" tactic. Putting assignment statements into indexing expressions is also needless obfuscation (which I untangled in the unrolled analysis).