4 ms·

That an optimizer assumes without proof a solution to the halting problem for some sub-program would mean that it's an unreliable translator The optimizer does

by neilc 16y ago

That an optimizer assumes without proof a solution to the halting problem for some sub-program would mean that it's an unreliable translator The optimizer doesn't need to solve the halting problem for this example. It merely needs to prove that any iteration of the loop has no side effects; hence, an unbounded number of loop iterations also has no side effects, and the loop can be removed. The real issue is whether termination is considered a side effect. The canon is the C spec; if you can point to some language in the spec that would prevent the optimization, I'd love to see it. Update: on reflection, I think you're right. The point isn't that the loop has side-effects (it obviously doesn't); but by changing the termination behavior of the loop, the compiler is likely to induce additional side effects (when it runs the subsequent code).

barrkel 16y ago
But a loop that never exits will never continue on to the rest of the program, which will never have its side-effects. This loop has no side-effects: for (;;) /* do nothing */; So the compiler, according to the spec, can remove it, right? for (;;) /* do nothing */; destroy_the_world(); /* has side-effects */ So will the world be destroyed? Or is the following code dead? In which case, it's not OK for the compiler to remove loops that have no side-effects.
- Rexxar 16y ago
  Every optimization can potentially have a side-effect : { time ta0 = getTime(); for (;;) { /* do something 1*/ } time ta1 = getTime(); time tb0 = getTime(); for (;;) { /* do something 2*/ } time tb1 = getTime(); if(ta1-ta0 < tb1-tb0) destroy_the_world(); /* has side-effects */ } The result depends of the speed of execution of each loops. Should optimizations really be allowed only if they don't have any side effect ?
- dkersten 16y ago
  The C spec states[1] that code without side-effects may be removed. The C spec does not list non-termination as a side-effect. The C spec also states that anything not explicitly stated is undefined behaviour. That means that in the abstract machine that the C spec defines, it is valid to remove the loop. If you don't want the loop to be removed, then you are working outside of the defined abstract machine, which means that its up to you to make sure it operates as desired. The embedded systems guys mentioned in the article (on the llvm bug tracker, they also said it "wasn't much of an issue" for them, because they did, in fact, tell the compiler to do what they wanted, wheras the author stated that it was) did this by compiling the necessary code without optimisations. Other valid approaches would be to tell the compiler that the loop may, in fact, have side-effects which cannot be known in the context of the code by declaring the variables volatile (the C spec defines reading volatile varibales as side-effects). If you see non-termination as side-effects, then you should tell your compiler somehow. The C programming language runs in a well defined abstract machine. Anything a compiler does which is not defined by the abstract machine (so long as it doesn't contradict the abstract machine, ie the abstract machine functions as stated) is not a bug, but is considered undefined behaviour and cannot be relied upon - therefore relying on an infinite loop which does not contain side-effects is undefined behaviour. -- As for if a programming language in general (rather than specifically C) should remove infinite loops.. I think its up to each language to define this. If a language states that non-termination is a side-effect, then compilers cannot optimise away code which may not terminate, unless the user invokes undefined compiler-specific behaviour by telling it to (eg compiler options) or by changing the code to make your intent obvious to the compiler. Or by solving the halting problem. So, in summary: The C compilers are NOT wrong to elliminate the side-effect free infinite loops. Other languages MAY be wrong to do so - it depends on what the language specs state. You CAN get around this by telling the compiler what your intent is, by either changing the code (eg by introducing side-effects) or by invoking non-standard behavour (eg, through compiler switches). [1] 5.1.2.3 (Execution Environment), paragraphs 2 and 3.
Confusion 16y ago
if you can point to some language in the spec that would prevent the optimization, I'd love to see it. The author added an update that says, among other things: In contrast, the Java language definition is quite clear that infinite loops may not be terminated by the JVM. (with a link to the JLS)

by neilc 16y ago

barrkel 16y ago

But a loop that never exits will never continue on to the rest of the program, which will never have its side-effects. This loop has no side-effects: for (;;) /* do nothing */; So the compiler, according to the spec, can remove it, right? for (;;) /* do nothing */; destroy_the_world(); /* has side-effects */ So will the world be destroyed? Or is the following code dead? In which case, it's not OK for the compiler to remove loops that have no side-effects.

Rexxar 16y ago
Every optimization can potentially have a side-effect : { time ta0 = getTime(); for (;;) { /* do something 1*/ } time ta1 = getTime(); time tb0 = getTime(); for (;;) { /* do something 2*/ } time tb1 = getTime(); if(ta1-ta0 < tb1-tb0) destroy_the_world(); /* has side-effects */ } The result depends of the speed of execution of each loops. Should optimizations really be allowed only if they don't have any side effect ?
dkersten 16y ago
The C spec states[1] that code without side-effects may be removed. The C spec does not list non-termination as a side-effect. The C spec also states that anything not explicitly stated is undefined behaviour. That means that in the abstract machine that the C spec defines, it is valid to remove the loop. If you don't want the loop to be removed, then you are working outside of the defined abstract machine, which means that its up to you to make sure it operates as desired. The embedded systems guys mentioned in the article (on the llvm bug tracker, they also said it "wasn't much of an issue" for them, because they did, in fact, tell the compiler to do what they wanted, wheras the author stated that it was) did this by compiling the necessary code without optimisations. Other valid approaches would be to tell the compiler that the loop may, in fact, have side-effects which cannot be known in the context of the code by declaring the variables volatile (the C spec defines reading volatile varibales as side-effects). If you see non-termination as side-effects, then you should tell your compiler somehow. The C programming language runs in a well defined abstract machine. Anything a compiler does which is not defined by the abstract machine (so long as it doesn't contradict the abstract machine, ie the abstract machine functions as stated) is not a bug, but is considered undefined behaviour and cannot be relied upon - therefore relying on an infinite loop which does not contain side-effects is undefined behaviour. -- As for if a programming language in general (rather than specifically C) should remove infinite loops.. I think its up to each language to define this. If a language states that non-termination is a side-effect, then compilers cannot optimise away code which may not terminate, unless the user invokes undefined compiler-specific behaviour by telling it to (eg compiler options) or by changing the code to make your intent obvious to the compiler. Or by solving the halting problem. So, in summary: The C compilers are NOT wrong to elliminate the side-effect free infinite loops. Other languages MAY be wrong to do so - it depends on what the language specs state. You CAN get around this by telling the compiler what your intent is, by either changing the code (eg by introducing side-effects) or by invoking non-standard behavour (eg, through compiler switches). [1] 5.1.2.3 (Execution Environment), paragraphs 2 and 3.

Confusion 16y ago

if you can point to some language in the spec that would prevent the optimization, I'd love to see it. The author added an update that says, among other things: In contrast, the Java language definition is quite clear that infinite loops may not be terminated by the JVM. (with a link to the JLS)