5 ms·

Thanks for the example. But again I can't see a problem. The compiler does not actually prove UB in this case, so I suppose this doesn't qualify as applying (mi

Thanks for the example. But again I can't see a problem. The compiler does not actually prove UB in this case, so I suppose this doesn't qualify as applying (mis-) optimizations silently based on UB. Or what did I miss?

kazinator 2y ago
Compilers don't prove UB; they assume absence of UB. That, plus a modicum of reasoning like "if this were to be evaluated, it would be UB" (therefore, let's assume that is not evaluated).
- deleted 2y ago
  [deleted]
- jstimpfle 2y ago
  Let's not get pedantic about what "proving UB" actually means -- that might lead to philosophic discussions about sentient compilers. Fact is that in this instance, the compiler did not remove a basic black of code (including or excluding "observeable side-effects" leading up to the point of UB happening). It would not be valid for the compiler to assume that the path is never taken in this case, even assuming that UB never happens, because depending on the the value of the variables, there are possible paths through the code that do not exhibit UB. In other words, "the compiler wasn't able to prove UB". So this is not an instance of the situation that we are discussing. The emitted code is just fine, unless a division by zero occurs. Handling division by zero is responsibility of the programmer. Nobody is arguing that UB can lead to weird runtime effects -- just dereference an invalid pointer or whatever. The issue discussed is that based on assumptions about UB, the compiler emits code that does not correspond to the source in an intuitive way, for example a branch of code is entirely removed, including any observeable side-effects that logically happened before the UB. Now the point of the GGP poster is probably that the observeable side-effect (the volatile access) does not happen at all because the UB happens first. But I would classify this case differently -- the volatile access is not elided from the branch. Further more, it might well be that (and let me assume so) the order of the volatile access and the division operation that causes the UB are probably not defined as happening in a strict sequence (because, I'm assuming again as any reasonable standards layman would, UB is not considered a side-effect (that would kinda defeat the point, disallowing optimizations)). So it's entirely valid for the compiler to order the operation that causes the (potential) UB before the volatile access.
  - jstimpfle 2y ago
    Btw. you literally said "If a compiler determines that some statement has undefined behavior, it can treat it as unreachable".
  - gpderetta 2y ago
    > The issue discussed is that based on assumptions about UB, the compiler emits code that does not correspond to the source in an intuitive way, for example a branch of code is entirely removed, including any observeable side-effects that logically happened before the UB. That's literally what happens in my example: the div is hoisted above the volatile read which is an observable side effect. The practical effect is that the expected side effect is not executed even if it should have happened-before the SIGFPE. uecker claims that the UB should still respect happens-before, and I'm inclined to agree that's an useful property to preserve. And I don't see any significant difference between my example and what you are arguing.
    - jstimpfle 2y ago
      See my other comments. I don't even think your example has an observeable side-effect.
gpderetta 2y ago
The compiler is moving a potentially UB operation above a side effect. This contradicts uecker non-time-traveling-ub and it is potentially a GCC bug. If you want an example of GCC removing a side effect that happens-before provable subsequent UB: https://godbolt.org/z/PfoT8E8PP https://godbolt.org/z/PfoT8E8PP but I don't find it terribly interesting as the compiler warns here.
- jstimpfle 2y ago
  In your godbolt extern volatile int x; int ub() { int r = x; r += 1/0; return r; } and the output is ub: mov eax, DWORD PTR x[rip] ud2 I don't see what is the side effect that you say is removed here? As for the earlier example (hoisting the division out of the loop), I was going to write a wall of text explaining why I find the behaviour totally intuitive and in line with what I'd expect. But we can make it simpler: The code doesn't even have any observeable side effect (at least I think so), because it only reads the volatile, never writes it! The observeable behaviour is exactly the same as if the hoist hadn't happened. I believe it's a totally valid transformation, at least I don't have any concerns with it.
  - jstimpfle 2y ago
    I think this one better illutrates the point you were making: https://godbolt.org/z/qbfhb6dKo https://godbolt.org/z/qbfhb6dKo Here I've inserted an increment of the volatile (i.e. a write access) at the start of the loop. If the divisor is 0, in the optimized version with the division hoisted out of the loop, the increment will never actually happen, not even once. Whereas it should in fact happen 1x at the beginning of the first loop iteration with "unoptimized" code. I don't find this offputting: First, the incrementing code is still in the output binary. I think what is understood by "time travel", and what would be offputting to most programmers, is if the compiler was making static inferences and was removing entire code branches based on that -- without telling the user. If that was the case, I would consider it a compiler usability bug. But that's not what's happening here. Second, I think everybody can agree that the compiler should be able to reorder a division operation before a write access, especially when hoisting the division out of a loop. So while maybe an interesting study, I think the behaviour here is entirely reasonable -- irrespective of standards. (But again, I don't think uecker, nor anyone else, said that the compiler may never reorder divisions around side-effecting operations just because the division "could" be UB).

kazinator 2y ago

Compilers don't prove UB; they assume absence of UB. That, plus a modicum of reasoning like "if this were to be evaluated, it would be UB" (therefore, let's assume that is not evaluated).

deleted 2y ago
[deleted]
jstimpfle 2y ago
Let's not get pedantic about what "proving UB" actually means -- that might lead to philosophic discussions about sentient compilers. Fact is that in this instance, the compiler did not remove a basic black of code (including or excluding "observeable side-effects" leading up to the point of UB happening). It would not be valid for the compiler to assume that the path is never taken in this case, even assuming that UB never happens, because depending on the the value of the variables, there are possible paths through the code that do not exhibit UB. In other words, "the compiler wasn't able to prove UB". So this is not an instance of the situation that we are discussing. The emitted code is just fine, unless a division by zero occurs. Handling division by zero is responsibility of the programmer. Nobody is arguing that UB can lead to weird runtime effects -- just dereference an invalid pointer or whatever. The issue discussed is that based on assumptions about UB, the compiler emits code that does not correspond to the source in an intuitive way, for example a branch of code is entirely removed, including any observeable side-effects that logically happened before the UB. Now the point of the GGP poster is probably that the observeable side-effect (the volatile access) does not happen at all because the UB happens first. But I would classify this case differently -- the volatile access is not elided from the branch. Further more, it might well be that (and let me assume so) the order of the volatile access and the division operation that causes the UB are probably not defined as happening in a strict sequence (because, I'm assuming again as any reasonable standards layman would, UB is not considered a side-effect (that would kinda defeat the point, disallowing optimizations)). So it's entirely valid for the compiler to order the operation that causes the (potential) UB before the volatile access.
- jstimpfle 2y ago
  Btw. you literally said "If a compiler determines that some statement has undefined behavior, it can treat it as unreachable".
- gpderetta 2y ago
  > The issue discussed is that based on assumptions about UB, the compiler emits code that does not correspond to the source in an intuitive way, for example a branch of code is entirely removed, including any observeable side-effects that logically happened before the UB. That's literally what happens in my example: the div is hoisted above the volatile read which is an observable side effect. The practical effect is that the expected side effect is not executed even if it should have happened-before the SIGFPE. uecker claims that the UB should still respect happens-before, and I'm inclined to agree that's an useful property to preserve. And I don't see any significant difference between my example and what you are arguing.
  - jstimpfle 2y ago
    See my other comments. I don't even think your example has an observeable side-effect.

gpderetta 2y ago

The compiler is moving a potentially UB operation above a side effect. This contradicts uecker non-time-traveling-ub and it is potentially a GCC bug. If you want an example of GCC removing a side effect that happens-before provable subsequent UB: https://godbolt.org/z/PfoT8E8PP https://godbolt.org/z/PfoT8E8PP but I don't find it terribly interesting as the compiler warns here.

jstimpfle 2y ago
In your godbolt extern volatile int x; int ub() { int r = x; r += 1/0; return r; } and the output is ub: mov eax, DWORD PTR x[rip] ud2 I don't see what is the side effect that you say is removed here? As for the earlier example (hoisting the division out of the loop), I was going to write a wall of text explaining why I find the behaviour totally intuitive and in line with what I'd expect. But we can make it simpler: The code doesn't even have any observeable side effect (at least I think so), because it only reads the volatile, never writes it! The observeable behaviour is exactly the same as if the hoist hadn't happened. I believe it's a totally valid transformation, at least I don't have any concerns with it.
- jstimpfle 2y ago
  I think this one better illutrates the point you were making: https://godbolt.org/z/qbfhb6dKo https://godbolt.org/z/qbfhb6dKo Here I've inserted an increment of the volatile (i.e. a write access) at the start of the loop. If the divisor is 0, in the optimized version with the division hoisted out of the loop, the increment will never actually happen, not even once. Whereas it should in fact happen 1x at the beginning of the first loop iteration with "unoptimized" code. I don't find this offputting: First, the incrementing code is still in the output binary. I think what is understood by "time travel", and what would be offputting to most programmers, is if the compiler was making static inferences and was removing entire code branches based on that -- without telling the user. If that was the case, I would consider it a compiler usability bug. But that's not what's happening here. Second, I think everybody can agree that the compiler should be able to reorder a division operation before a write access, especially when hoisting the division out of a loop. So while maybe an interesting study, I think the behaviour here is entirely reasonable -- irrespective of standards. (But again, I don't think uecker, nor anyone else, said that the compiler may never reorder divisions around side-effecting operations just because the division "could" be UB).