<p>Consider the following function:</p>
<pre><code>unsigned test(unsigned x, unsigned factor, unsigned mask)
{
  unsigned i=1;
  while((i &amp; mask) != x)
    i*=factor;
  return i;
}
</code></pre>
<p>Proving that in the absence of optimizations, the function would either return a value with no side effects, or not return at all, would be trivial.  Proving whether it will return for any particular combination of operands would be generally be impractical, however.</p>
<p>If one wanted to write a transpiler for a source language which would recognize both &quot;block program execution indefinitely&quot; and &quot;do nothing, with no side effects&quot; as valid treatments of an endless loop which has a statically reachable exit, and where no <em>individual operation</em> could affect the set of reachable program states, would there be any way such a transpiler that targets C could benefit from such flexibility without having to perform all optimizations itself, and add dummy side effects to any loops whose termination could not be proven?</p>
<p>Note that the C Standard, as interpreted by clang, and the C++ Standard as interpreted by clang and gcc, allow compilers to behave in <em>completely unbounded</em> arbitrary fashion if a program receives inputs that would cause a side-effect-free loop to fail to terminate, rather than merely allowing code which follows the loop but does not observe any state that changes within it to be hoisted ahead of the loop execution.  If e.g. clang or (when using C++) gcc were to observe that the loop executes with <code>mask</code> equal to 65535, and then after the loop code were to do something like <code>if (x &lt; 65536) array[x] = 1;</code>, both the <code>if</code> and the loop would be eliminated, turning what had been a bounds-checked store into an unconditional (non-bounds-checked) store.</p>

<optimization><c><loops><transpilers>
How can transpilers benefit from compiler optimizations which are compatible with semantics, if other "optimizations" in the target language aren't?
CC BY-SA 4.0
2024-06-24T18:28:19.603Z
The parameter `x` seems to never be used. Also this loop doesn't terminate when `mask = 3` and `factor = 0`, for example, so proving termination here isn't merely impractical.
kaya3
CC BY-SA 4.0
2024-06-24T18:31:19.817Z
Regarding the actual question, you posit "do nothing with no side-effects" to be a valid treatment of infinite side-effect-free loops in the *source* language, then offer C as a *target* language, but isn't it the case that C allows exactly this treatment? So you would not need to do anything to take advantage of this, it comes free with the fact that you target C. But you also suggest one might need to *"add dummy side effects to any loops whose termination could not be proven"* ─ wouldn't this undermine precisely the feature you are trying to achieve?
kaya3
CC BY-SA 4.0
2024-06-24T19:18:56.143Z
@kaya3: C allows compilers to *artificially generate* arbitrary side effects in scenarios where a program would execute a side-effect-free loop, and clang will do precisely that.  GCC last I checked didn't seem to do that in C, but does so in C++.
supercat
CC BY-SA 4.0
2024-06-24T19:19:49.243Z
@kaya3: Slight mistake in the code I sketched.  Code should have tested `(i & mask)` against `x`.
supercat
CC BY-SA 4.0
2024-06-24T19:26:25.730Z
Adding dummy side effects would *achieve correct semantics*, which should be the first and foremost goal of any kind of compiler, transpiler, interpreter, or other such language tool.  It would undermine the usefulness of the potential optimization, but not as much as would having a compiler perform "optimizations" that break what would otherwise be easily verifiable memory-safety invariants.
supercat
CC BY-SA 4.0
2024-06-24T20:16:47.643Z
@kaya3: I've added another paragraph; are things clearer now?
supercat
CC BY-SA 4.0
2024-06-24T20:50:00.637Z
As far as I know, C compilers are not "allowed" to generate arbitrary side-effects (i.e. undefined behaviour) from side-effect-free infinite loops, as the spec only says *"An iteration statement whose controlling expression is not a constant expression, that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a `for` statement) its expression-3, **may be assumed by the implementation to terminate**."* (emphasis added)
kaya3
CC BY-SA 4.0
2024-06-24T20:54:56.060Z
@kaya3: Clang interprets the permission to "assume" that loops terminate as freedom to behave in arbitrary fashion if such assumption is violated, and gcc ignores that provision except in C++ mode.  Whether or not the authors of C11 intended such nonsense, no later standards have changed the text to unequivocally forbid it.
supercat
CC BY-SA 4.0
2024-06-24T21:00:21.023Z
So if I understand the question correctly, really the issue is that if you have a transpiler which targets C, how do you avoid the compiler treating non-terminating side-effect-free loops as UB, when this is not UB in the source language? Whether or not the source language semantically allows such loops to be skipped doesn't seem to matter, the problem is that the target language compiler treats them as UB but the source language doesn't.
kaya3
CC BY-SA 4.0
2024-06-24T21:15:45.440Z
@kaya3: If one weren't concerned about optimizations, the transpiler could ensure correctness by adding dummy side effects.  The question is whether one can avoid having loose semantics in the target language completely undermine any benefits that compiler "optimizations" in that language might otherwise be able to offer.
supercat
CC BY-SA 4.0
2024-06-24T21:17:43.510Z
I still don't see how it matters that the source language allows "do nothing, with no side effects", as stated in the question. This problem would occur regardless of that.
kaya3
CC BY-SA 4.0
2024-06-24T22:09:06.980Z
@kaya3: A compiler which inserts dummy side effects could not achieve all of the optimizations allowed by the source language unless it performed such optimizations by itself, but it could still process the program *correctly*.  The fact that an implementation doesn't achieve all possible optimizations isn't necessarily a "problem".  On the other hand, one of the supposed advantages of transpilers is that they can exploit optimizations in the back end.  I fail to see how that is possible unless the semantics of the source language are as severely constrained as those of the target.
supercat
CC BY-SA 4.0
2024-06-24T22:35:06.287Z
The problem is that the target language compiler can convert a loop which has defined behaviour in the source language into undefined behaviour. That is a problem regardless of optimisations, and regardless of what the source language's defined behaviour is.
kaya3
CC BY-SA 4.0
2024-06-24T23:02:58.823Z
@kaya3: If the transpiler adds a dummy side effect to the loop, then the loop would have defined behavior whether or not it terminates.  The resulting machine code would likely be less efficient than if semantics could have been achieved without the dummy side effect, but correctness would be achieved.
supercat
CC BY-SA 4.0
2024-06-25T00:39:33.667Z
I guess the Graal here would be to find dummy code that is known to be easily optimized away by the target compiler (when it can prove that doesn't introduce undefined behavior). Adding such effects unconditionally would give maximum performance when possible, without reimplementing any of the target compiler's logic in the transpiler.
Eldritch Conundrum
CC BY-SA 4.0
2024-06-25T14:53:15.120Z
@EldritchConundrum: What would really be most helpful would be if the Standard could draw a distinction between specialized optimizing dialects which are only suitable for a narrow range of tasks where "anything can happen" UB would be an acceptable response if some bit patterns are received as inputs, and general-purpose dialects which could be suitable for a wider range of tasks where "anything can happen UB" isn't an option, and transpiler writers could target the latter without having to add all sorts of junk code which blocks useful optimizing and maniacal "optimizing" transforms alike.
supercat
CC BY-SA 4.0
2024-06-25T16:14:48.613Z
Would you like to edit the title to focus on the particular question in the post, about possibly infinite loops?  Currently it seems over-broad.
Nate Eldredge
CC BY-SA 4.0
2024-06-25T16:17:08.143Z
So it seems to me that we ideally want to achieve three things: (1) if the loop always terminates and the C compiler can prove it, it's deleted; (2) if the loop does terminate but the compiler can't prove it, it executes without unnecessary overhead; (3) if the loop does not terminate, then an infinite loop is actually executed.  Adding a dummy side effect gives you (3), but breaks (1) and may add some overhead to (2).
Nate Eldredge
CC BY-SA 4.0
2024-06-25T16:22:48.917Z
One idea I had was to add (let's say) a 64-bit counter, incremented on every loop iteration, and have a dummy side effect (e.g. read a `volatile` variable) which only executes when the counter rolls over.  Then if the compiler can prove the loop terminates in less than 2^64 iterations, it can delete it, so we make some progress toward (1), and we still have (3).  But if the compiler can't prove termination, then it will have to actually generate code to increment and test the counter, which adds some overhead in case (2).
Nate Eldredge
CC BY-SA 4.0
2024-06-25T16:47:34.827Z
Another idea is to execute `atomic_store_explicit(&dummy, 0, memory_order_relaxed);` on each iteration.  This counts as a side effect, so an infinite loop is not UB.  But in theory, the compiler is allowed to hoist it out and just do the store once, since there's no
Nate Eldredge
CC BY-SA 4.0
2024-06-25T16:51:33.827Z
@EldritchConundrum: My actual interest is broader than infinite loops: can a transpiler for a language which would allow optimizing transforms to affect program behavior in cases that aren't characterized as "anything can happen" UB, receive any benefit from a back-end optimizer based on "anything can happen" UB.  I think the loop example best illustrates the concept of optimizing transforms yielding program behavior which is inconsistent with treating a program as a sequence of steps, but would not impede a program's ability to e.g. maintain statically-verifiable memory-safety invariants.
supercat
CC BY-SA 4.0
2024-06-25T17:02:06.317Z
@NateEldredge: Hmm... I'd like that atomic store idea, except for the facts that (1) it would only be usable on implementations that support atomics, and (2) I don't think Standard would *unambiguously* treat the store as a side effect that needed to be treated as occurring within the loop.  Neither clang nor gcc seems to be equipped to recognize situations where a "physical" operation may be hoisted but some semantic effects need to be treated as though they happened in proper execution order.  What makes the clang/gcc behavior objectionable is that they...
supercat
CC BY-SA 4.0
2024-06-25T17:13:37.560Z
...consolidate an `if` test which is performed after the loop with the test of the loop body condition, without recognizing that this creates a control dependency between evaluation of the loop's exit condition and the body of the `if`.  I suspect the reason clang and gcc don't keep track of such dependencies is that doing so would create phase order dependencies which compiler writers have spent the last 20ish years in a misguided quest to avoid.  Compiler theory has gotten attached to the idea that if T1(X) and T2(X) would both be valid ways of transforming program X, then...
supercat
CC BY-SA 4.0
2024-06-25T17:19:31.820Z
@supercat: The C and C++ standards are quite clear that "atomic operations" count as forward progress, so that a possibly infinite loop which performs an atomic operation can't be assumed to terminate and isn't UB.  This would even appear to include, e.g., an atomic load whose value is discarded, which could otherwise be optimized away (even though current compilers don't).  An interesting question is whether that also includes fences.  clang will optimize out an infinite loop containing a fence, but gcc won't.
Nate Eldredge
CC BY-SA 4.0
2024-06-25T17:20:19.587Z
...T1(T2(X)) and T2(T1(X)) should both be valid as well.  If T1(X) is "eliminate the loop" and T2(X) is "eliminate a conditional test which would always be true if the loop exit condition is satisfied" would mean that T1(X) and T2(X) to be valid, then T1(T2(X)) and T2(T1(X)) would eliminate both the loop and the 'if'.  As much as I'd like the idea of using the atomic store as described, I'd be skeptical as to whether clang or gcc could process it efficiently without reintroducing the problems it was added to solve.
supercat
CC BY-SA 4.0
2024-06-25T17:21:20.170Z
Oh, my earlier comment got truncated.  I was going to say that although in principle the compiler could hoist out an atomic store, in practice they don't, as you suspected.
Nate Eldredge
CC BY-SA 4.0
2024-06-25T17:39:38.490Z
@NateEldredge: I suspect that as soon as clang or gcc gains the ability to hoist the store instruction, it will cease to treat the store as representing "forward progress" *within the loop*.  Compiler philosophy has latched onto the idea that what rather than recognize that it should sometimes be hard for compilers to determine with certainty which of several *mutally exclusive* transforms is most useful, but that heuristics should be good enough for most practical purposes, it's better to characterize as "defective" any program that would require treating transforms as mutually exclusive.
supercat
CC BY-SA 4.0
2024-06-25T17:46:49.593Z
@supercat: If it does then that will be a clear violation of the standard, and should be unambiguously considered a bug.  But what seems to me more likely is that it would only hoist it out if the loop is provably terminating.
Nate Eldredge
CC BY-SA 4.0
2024-06-25T18:43:25.477Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/153825/discussion-between-supercat-and-nate-eldredge).
supercat
# How can transpilers benefit from compiler optimizations which are compatible with semantics, if other "optimizations" in the target language aren't?
Posted by: username_0 on 2024-06-24
Consider the following function:
unsigned test(unsigned x, unsigned factor, unsigned mask)
{
  unsigned i=1;
  while((i & mask) != x)
    i*=factor;
  return i;
}

Proving that in the absence of optimizations, the function would either return a value with no side effects, or not return at all, would be trivial.  Proving whether it will return for any particular combination of operands would be generally be impractical, however.
If one wanted to write a transpiler for a source language which would recognize both "block program execution indefinitely" and "do nothing, with no side effects" as valid treatments of an endless loop which has a statically reachable exit, and where no individual operation could affect the set of reachable program states, would there be any way such a transpiler that targets C could benefit from such flexibility without having to perform all optimizations itself, and add dummy side effects to any loops whose termination could not be proven?
Note that the C Standard, as interpreted by clang, and the C++ Standard as interpreted by clang and gcc, allow compilers to behave in completely unbounded arbitrary fashion if a program receives inputs that would cause a side-effect-free loop to fail to terminate, rather than merely allowing code which follows the loop but does not observe any state that changes within it to be hoisted ahead of the loop execution.  If e.g. clang or (when using C++) gcc were to observe that the loop executes with mask equal to 65535, and then after the loop code were to do something like if (x < 65536) array[x] = 1;, both the if and the loop would be eliminated, turning what had been a bounds-checked store into an unconditional (non-bounds-checked) store.
**Tags:** optimization c loops transpilers
> **Comments:**
> **username_1**: The parameter `x` seems to never be used. Also this loop doesn't terminate when `mask = 3` and `factor = 0`, for example, so proving termination here isn't merely impractical.  
> **username_1**: Regarding the actual question, you posit "do nothing with no side-effects" to be a valid treatment of infinite side-effect-free loops in the *source* language, then offer C as a *target* language, but isn't it the case that C allows exactly this treatment? So you would not need to do anything to take advantage of this, it comes free with the fact that you target C. But you also suggest one might need to *"add dummy side effects to any loops whose termination could not be proven"* ─ wouldn't this undermine precisely the feature you are trying to achieve?  
> **username_0**: @kaya3: C allows compilers to *artificially generate* arbitrary side effects in scenarios where a program would execute a side-effect-free loop, and clang will do precisely that.  GCC last I checked didn't seem to do that in C, but does so in C++.  
> **username_0**: @kaya3: Slight mistake in the code I sketched.  Code should have tested `(i & mask)` against `x`.  
> **username_0**: Adding dummy side effects would *achieve correct semantics*, which should be the first and foremost goal of any kind of compiler, transpiler, interpreter, or other such language tool.  It would undermine the usefulness of the potential optimization, but not as much as would having a compiler perform "optimizations" that break what would otherwise be easily verifiable memory-safety invariants.  
> **username_0**: @kaya3: I've added another paragraph; are things clearer now?  
> **username_1**: As far as I know, C compilers are not "allowed" to generate arbitrary side-effects (i.e. undefined behaviour) from side-effect-free infinite loops, as the spec only says *"An iteration statement whose controlling expression is not a constant expression, that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a `for` statement) its expression-3, **may be assumed by the implementation to terminate**."* (emphasis added)  
> **username_0**: @kaya3: Clang interprets the permission to "assume" that loops terminate as freedom to behave in arbitrary fashion if such assumption is violated, and gcc ignores that provision except in C++ mode.  Whether or not the authors of C11 intended such nonsense, no later standards have changed the text to unequivocally forbid it.  
> **username_1**: So if I understand the question correctly, really the issue is that if you have a transpiler which targets C, how do you avoid the compiler treating non-terminating side-effect-free loops as UB, when this is not UB in the source language? Whether or not the source language semantically allows such loops to be skipped doesn't seem to matter, the problem is that the target language compiler treats them as UB but the source language doesn't.  
> **username_0**: @kaya3: If one weren't concerned about optimizations, the transpiler could ensure correctness by adding dummy side effects.  The question is whether one can avoid having loose semantics in the target language completely undermine any benefits that compiler "optimizations" in that language might otherwise be able to offer.  
> **username_1**: I still don't see how it matters that the source language allows "do nothing, with no side effects", as stated in the question. This problem would occur regardless of that.  
> **username_0**: @kaya3: A compiler which inserts dummy side effects could not achieve all of the optimizations allowed by the source language unless it performed such optimizations by itself, but it could still process the program *correctly*.  The fact that an implementation doesn't achieve all possible optimizations isn't necessarily a "problem".  On the other hand, one of the supposed advantages of transpilers is that they can exploit optimizations in the back end.  I fail to see how that is possible unless the semantics of the source language are as severely constrained as those of the target.  
> **username_1**: The problem is that the target language compiler can convert a loop which has defined behaviour in the source language into undefined behaviour. That is a problem regardless of optimisations, and regardless of what the source language's defined behaviour is.  
> **username_0**: @kaya3: If the transpiler adds a dummy side effect to the loop, then the loop would have defined behavior whether or not it terminates.  The resulting machine code would likely be less efficient than if semantics could have been achieved without the dummy side effect, but correctness would be achieved.  
> **username_2**: I guess the Graal here would be to find dummy code that is known to be easily optimized away by the target compiler (when it can prove that doesn't introduce undefined behavior). Adding such effects unconditionally would give maximum performance when possible, without reimplementing any of the target compiler's logic in the transpiler.  
> **username_0**: @EldritchConundrum: What would really be most helpful would be if the Standard could draw a distinction between specialized optimizing dialects which are only suitable for a narrow range of tasks where "anything can happen" UB would be an acceptable response if some bit patterns are received as inputs, and general-purpose dialects which could be suitable for a wider range of tasks where "anything can happen UB" isn't an option, and transpiler writers could target the latter without having to add all sorts of junk code which blocks useful optimizing and maniacal "optimizing" transforms alike.  
> **username_3**: Would you like to edit the title to focus on the particular question in the post, about possibly infinite loops?  Currently it seems over-broad.  
> **username_3**: So it seems to me that we ideally want to achieve three things: (1) if the loop always terminates and the C compiler can prove it, it's deleted; (2) if the loop does terminate but the compiler can't prove it, it executes without unnecessary overhead; (3) if the loop does not terminate, then an infinite loop is actually executed.  Adding a dummy side effect gives you (3), but breaks (1) and may add some overhead to (2).  
> **username_3**: One idea I had was to add (let's say) a 64-bit counter, incremented on every loop iteration, and have a dummy side effect (e.g. read a `volatile` variable) which only executes when the counter rolls over.  Then if the compiler can prove the loop terminates in less than 2^64 iterations, it can delete it, so we make some progress toward (1), and we still have (3).  But if the compiler can't prove termination, then it will have to actually generate code to increment and test the counter, which adds some overhead in case (2).  
> **username_3**: Another idea is to execute `atomic_store_explicit(&dummy, 0, memory_order_relaxed);` on each iteration.  This counts as a side effect, so an infinite loop is not UB.  But in theory, the compiler is allowed to hoist it out and just do the store once, since there's no  
> **username_0**: @EldritchConundrum: My actual interest is broader than infinite loops: can a transpiler for a language which would allow optimizing transforms to affect program behavior in cases that aren't characterized as "anything can happen" UB, receive any benefit from a back-end optimizer based on "anything can happen" UB.  I think the loop example best illustrates the concept of optimizing transforms yielding program behavior which is inconsistent with treating a program as a sequence of steps, but would not impede a program's ability to e.g. maintain statically-verifiable memory-safety invariants.  
> **username_0**: @NateEldredge: Hmm... I'd like that atomic store idea, except for the facts that (1) it would only be usable on implementations that support atomics, and (2) I don't think Standard would *unambiguously* treat the store as a side effect that needed to be treated as occurring within the loop.  Neither clang nor gcc seems to be equipped to recognize situations where a "physical" operation may be hoisted but some semantic effects need to be treated as though they happened in proper execution order.  What makes the clang/gcc behavior objectionable is that they...  
> **username_0**: ...consolidate an `if` test which is performed after the loop with the test of the loop body condition, without recognizing that this creates a control dependency between evaluation of the loop's exit condition and the body of the `if`.  I suspect the reason clang and gcc don't keep track of such dependencies is that doing so would create phase order dependencies which compiler writers have spent the last 20ish years in a misguided quest to avoid.  Compiler theory has gotten attached to the idea that if T1(X) and T2(X) would both be valid ways of transforming program X, then...  
> **username_3**: @supercat: The C and C++ standards are quite clear that "atomic operations" count as forward progress, so that a possibly infinite loop which performs an atomic operation can't be assumed to terminate and isn't UB.  This would even appear to include, e.g., an atomic load whose value is discarded, which could otherwise be optimized away (even though current compilers don't).  An interesting question is whether that also includes fences.  clang will optimize out an infinite loop containing a fence, but gcc won't.  
> **username_0**: ...T1(T2(X)) and T2(T1(X)) should both be valid as well.  If T1(X) is "eliminate the loop" and T2(X) is "eliminate a conditional test which would always be true if the loop exit condition is satisfied" would mean that T1(X) and T2(X) to be valid, then T1(T2(X)) and T2(T1(X)) would eliminate both the loop and the 'if'.  As much as I'd like the idea of using the atomic store as described, I'd be skeptical as to whether clang or gcc could process it efficiently without reintroducing the problems it was added to solve.  
> **username_3**: Oh, my earlier comment got truncated.  I was going to say that although in principle the compiler could hoist out an atomic store, in practice they don't, as you suspected.  
> **username_0**: @NateEldredge: I suspect that as soon as clang or gcc gains the ability to hoist the store instruction, it will cease to treat the store as representing "forward progress" *within the loop*.  Compiler philosophy has latched onto the idea that what rather than recognize that it should sometimes be hard for compilers to determine with certainty which of several *mutally exclusive* transforms is most useful, but that heuristics should be good enough for most practical purposes, it's better to characterize as "defective" any program that would require treating transforms as mutually exclusive.  
> **username_3**: @supercat: If it does then that will be a clear violation of the standard, and should be unambiguously considered a bug.  But what seems to me more likely is that it would only hoist it out if the loop is provably terminating.  
> **username_0**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/153825/discussion-between-supercat-and-nate-eldredge).  
---
## 0 answers
