4 ms·

Should loop-invariant code motion be an allowed optimization only when the compiler can statically prove that a for loop's increment won't overflow?

by kalkin 4y ago

dooglius 4y ago
If it would result in different behavior in the event of an overflow (which I think is generally not the case), then no. A typical for loop (using <) can easily been seen to not overflow, so this is a rare case anyway. Loops using signed comparison with <= where the compiler can't rule overflow out should result in a compiler or linter warning.
- kalkin 4y ago
  The inequality argument would seem to apply only to for loops with constant iteration counts, yeah? The compiler can't know that "i < n; i++" won't overflow if "i" could start out higher than "n". (wrong) I am not an expert on compiler optimization, but having reasoned through a few cases where a compiler is _unable_ to correctly make an obvious-seeming optimization, I tend to think that compiler writers have good reasons for the things they want to be able to assume.
  - dooglius 4y ago
    If "i" started out higher than "n", the loop would exit immediately and there would be no increment. More generally, if "n" is an int, then even if n is modified each iteration, the "i < n; i++" still can't overflow because it will always exit at INT_MAX if not before. If "n" is something else like a long then that's likely a mistake that falls under "the compiler should warn if you do this". If there were good reason for wanting to assume this, I would expect someone to have presented it; responses I hear just take the form of a single (usually contrived) example where more performant code is generated, then insisting that all other factors (e.g. being predictable/unsurprising, acting like the underlying architecture, mitigating bugs) are irrelevant. Just as GP did.
    - kalkin 4y ago
      Ah good point re the inequality, over thought it. If there weren't good reasons for making the assumptions that modern compilers do, I'd have expected users of C and C++ to have converged on a more conservative compiler, at least in some significant number.

Should loop-invariant code motion be an allowed optimization only when the compiler can statically prove that a for loop's increment won't overflow?

by kalkin 4y ago

Should loop-invariant code motion be an allowed optimization only when the compiler can statically prove that a for loop's increment won't overflow?

dooglius 4y ago

If it would result in different behavior in the event of an overflow (which I think is generally not the case), then no. A typical for loop (using <) can easily been seen to not overflow, so this is a rare case anyway. Loops using signed comparison with <= where the compiler can't rule overflow out should result in a compiler or linter warning.

kalkin 4y ago
The inequality argument would seem to apply only to for loops with constant iteration counts, yeah? The compiler can't know that "i < n; i++" won't overflow if "i" could start out higher than "n". (wrong) I am not an expert on compiler optimization, but having reasoned through a few cases where a compiler is _unable_ to correctly make an obvious-seeming optimization, I tend to think that compiler writers have good reasons for the things they want to be able to assume.
- dooglius 4y ago
  If "i" started out higher than "n", the loop would exit immediately and there would be no increment. More generally, if "n" is an int, then even if n is modified each iteration, the "i < n; i++" still can't overflow because it will always exit at INT_MAX if not before. If "n" is something else like a long then that's likely a mistake that falls under "the compiler should warn if you do this". If there were good reason for wanting to assume this, I would expect someone to have presented it; responses I hear just take the form of a single (usually contrived) example where more performant code is generated, then insisting that all other factors (e.g. being predictable/unsurprising, acting like the underlying architecture, mitigating bugs) are irrelevant. Just as GP did.
  - kalkin 4y ago
    Ah good point re the inequality, over thought it. If there weren't good reasons for making the assumptions that modern compilers do, I'd have expected users of C and C++ to have converged on a more conservative compiler, at least in some significant number.