Hi, All:
Is it legal to delete empty infinite loop like this : "while(1) {}"?
It is interesting that both llvm and gcc keep the loop, however Open64 delete it.
If it is safe to delete this loop, it would be lot easier to delete non-obvious
dead loop like following as compiler doesn't need to prove if the loop in question
is infinite or not. Currently llvm is not able to delete such dead loop.
while (a) { a = whatever } ; // no use of <a> after this point.
Thanks
Shuxin
I think it's illegal to delete such infinite loop, perhapes you should
file a bug report to open64. That's my 2 cents.
Regards,
chenwj
The reason I think it's illegal is because if you remove it, then the
behavior is different. One with infinite empty loop will run infinitely,
the other w/o infinite empty loop will exit immediately. That's my
point.
Regards,
chenwj
Hi Shuxin,
Is it legal to delete empty infinite loop like this : "while(1) {}"?
It is interesting that both llvm and gcc keep the loop, however Open64 delete it.
this is an endless source of discussion. I suggest you read the GCC and LLVM
mailing list archives if you want to find out more about it.
Ciao, Duncan.
Following loop (in asm) is often seen in embedded programs. It is used to delay for certain amount of time.
If it were not written in asm, compiler would blindly delete the entire loop. How can compiler know such DCE
betray program intention?
for (i = 0; i < N; i++) { nop; nop; nop }
I guess in the gray area, if programmer do not want compiler do something he doesn't expect,
he/she perhaps have to resort to some esoteric ways. Compiler would otherwise have hard time in
analyzing.
I do some google, I cannot find the answer...
I check C std, I cannot find answer either.
Delete infinite empty loop is boring, but if C/C++ lawyers could tell it is safe to to so,
it would obviate the need to prove a non-countable loop infinite or not before
DCE can delete it.
That is the answer I'm waiting for to delete a disgusting dead non-countable loop in my way.
Perhaps Duncan will give you a proper keyword to search in GCC/LLVM
ML archieve. I found a page [1], and iiuc, the C standard allow the
implementation (i.e., the compiler) to remove such empty infinite loop.
Regards,
chenwj
GCC's current policy is described in the GCC manual:
* Deleting "empty" loops.
Historically, GCC has not deleted "empty" loops under the
assumption that the most likely reason you would put one in a
program is to have a delay, so deleting them will not make real
programs run any faster.
However, the rationale here is that optimization of a nonempty loop
cannot produce an empty one. This held for carefully written C
compiled with less powerful optimizers but is not always the case
for carefully written C++ or with more powerful optimizers. Thus
GCC will remove operations from loops whenever it can determine
those operations are not externally visible (apart from the time
taken to execute them, of course). In case the loop can be proved
to be finite, GCC will also remove the loop itself.
Be aware of this when performing timing tests, for instance the
following loop can be completely removed, provided
`some_expression' can provably not change any global state.
{
int sum = 0;
int ix;
for (ix = 0; ix != 10000; ix++)
sum += some_expression;
}
Even though `sum' is accumulated in the loop, no use is made of
that summation, so the accumulation can be removed.
Ciao, Duncan.
Interestingly, their first example is explicitly not justified by the
paragraph they quote: the controlling expression *is* a constant
expression.
Tim.
The canonical example of doing this in a safe way is to touch a volatile
variable.
Joerg
Hi, dear Wenren:
Thank you so much for sharing this info. I really appreciate it.
Now I can move on deleting dead non-countable loops.
Thank you again!
Shuxin
If the loop was reachable, the program will not terminate. If you delete the loop, where is the execution going to go after this point? You can't arbitrarily insert a branch to somewhere or instructions to execute. If the loop was unreachable, then it doesn't matter if you delete it or not unless you want to reduce code size, but regardless of that, if you can prove that it's unreachable then you can delete it as such and then it doesn't matter what it does.
-Krzysztof
Indeed, replacing it with unreachable rather than simply removing it
may provide other optimization opportunities.
If the code is unreachable, such code is easy to be removed, and should be removed.
If it is reachable, that is bit difficult to tell. Now that C std already give compiler such permit,
perhaps we don't have to keep in sync with gcc. Otherwise, it is very difficult to delete dead
non-countable loop.
One might argue, do you see many dead non-countable loops?
I don't know the answer, but in the case I'm working on the loop was not dead at beginning,
but after I recognize some idiom and remove some statements out of the loop. Then the loop becomes dead.
I hope DCE to get rid of it.
The C++11 standard explicitly allows compilers to assume that all loops will eventually terminate:
[intro.multithread] 24:
The implementation may assume that any thread will eventually do one of the following:
— terminate,
— make a call to a library I/O function,
— access or modify a volatile object, or
— perform a synchronization operation or an atomic operation.
[ Note: This is intended to allow compiler transformations such as removal of empty loops, even when
termination cannot be proven. —end note ]
I don't know if C11 has a similar statement, but C99 has a statement which is ambiguous in this regard (it only refers to a requirement upon program termination).
There's a blog post by John Regehr on this topic: <http://blog.regehr.org/archives/161>\.
From the C standard (well, draft):
Thank you all for the input. Seems that I have to prove a non-countable loop is finite before I can delete it.
BTW, I think this draft is not clear as to what is "constant expr". The source code may use symbolic value,
but later on the symbolic value could be proved to be constant. However, compiler could mistakenly delete the loop before that
point.
Thank you all for the input again!
Shuxin
A "constant expression" in this context is defined by the C standard
to mean a literal value like "1", not a symbolic value.
-Eli
BTW, I think this draft is not clear as to what is "constant expr".
A "constant expression" in this context is defined by the C standard
to mean a literal value like "1", not a symbolic value.
And just to add one detail to that: the concept has its own section
(6.6) in the standard.
Tim.
Well, LLVM sometimes keeps infinite loops. Compile this with -O2, for example:
void bar(void) {
for (;
{}
}
void foo(void) {
bar();
}
Infinite loops really are special, and infinite loops containing no side effects really are especially special. People will probably say that LLVM and Open64 and other compilers have bugs here, and they’re probably right. There is room for sympathy though, both because of the unique havoc infinite loops play on compiler theory, and because of how rarely empty loops are actually an advisable idiom in the real world.
Dan