I tried the LLVM demo with unmodified settings
http://llvm.org/demo/index.cgi
(same results from llvm 2.6 with clang, `clang-cc -emit-llvm -O2
test.c`, on my Linux x86_64)
For fun, I made a recursive function, but LLVM optimized it wrong (if
I'm understanding C standards correctly).
"void f() { f(); }"[see llvm-code in footnote 1]
was optimized to be equivalent to "void f() {}"[also 1]. I believe it
should either be equivalent in effect to "void f() { while(1){} }"[2],
which produces an infinite loop, or perhaps lead to a stack overflow (as
GCC might produce)... it's alright if the infinite loop is written using
tail-calls. All I expect is that it never actually return when you run it.
Adding a store to a global volatile variable fixes it, as does a
puts("hi");
"volatile int g; void f() { g = 1; f(); }"[3], or even the version
that
never actually gets to the volatile store at all,
"volatile int g; void f() { f(); g = 1; }"[4]
However, a local volatile variable gets quite strange treatment
"void f() { volatile int h; h = 1; f(); }"[5]
(it looks to me like one iteration of the function is inlined -- as I
guess happens in [3] and [4] -- but the recursive call deleted, as
happens in [1]). This is worse than just a non-terminating function
returning, as it also does not write to volatile stack variables the
requisite infinite number of times.
(I could not discover any obviously-*useful* code that gets
mis-optimized, luckily, although problems persist when I add function
arguments and return-values to the infinite recursive function.)
And here are the LLVM code emitted from each C code:
[1] "void f() { f(); }", or "void f() {}"
define void @f() nounwind readnone {
entry:
ret void
}
[2] "void f() { while(1){} }"
define void @f() nounwind readnone {
entry:
br label %bb
bb: ; preds = %bb, %entry
br label %bb
}
[3] "volatile int g; void f() { g = 1; f(); }"
@g = common global i32 0 ; <i32*> [#uses=2]
define void @f() nounwind {
entry:
volatile store i32 1, i32* @g, align 4
volatile store i32 1, i32* @g, align 4
tail call void @f() nounwind
ret void
}
[4] "volatile int g; void f() { f(); g = 1; }"
@g = common global i32 0 ; <i32*> [#uses=2]
define void @f() nounwind {
entry:
tail call void @f() nounwind
volatile store i32 1, i32* @g, align 4
volatile store i32 1, i32* @g, align 4
ret void
}
[5] "void f() { volatile int h; h = 1; f(); }"
define void @f() nounwind readnone {
entry:
%h.i = alloca i32, align 4 ; <i32*> [#uses=1]
%h = alloca i32, align 4 ; <i32*> [#uses=1]
volatile store i32 1, i32* %h, align 4
volatile store i32 1, i32* %h.i, align 4
ret void
}
In [1], if you try without optimizations, your get the result
expected. I'm not C standards specialist, but AFAIK you can just
delete function f. There's a pass that sees that f doesn't have side
effects (no stores) and maybe there's one that sees that it doesn't
depend on the machine state (no loads), so it must depend only on the
arguments to run. As it doesn't return anything, it's incapable of
having results and can be deleted.
If you try [6], you get f call deleted from g. On [2], you clearly ask
for a infinite loop. If you try [2] without optimizations, it's shown
that the return block doesn't have any predecessors [7], so it is
deleted by DCE.
Of course, I can just be wrong :)
[6] "void f() { f(); } void g() { f(); }"
define void @f() nounwind readnone {
entry:
ret void
}
define void @g() nounwind readnone {
entry:
ret void
}
[7] "void f() { while(1){}; }"
define void @f() nounwind {
entry:
br label %bb
bb: ; preds = %bb, %entry
br label %bb
return: ; No predecessors!
ret void
}
On Sun, Feb 28, 2010 at 2:54 AM, Isaac Dupree
<ml at isaac.cedarswampstudios.org> wrote:>
> I tried the LLVM demo with unmodified settings
> http://llvm.org/demo/index.cgi
> (same results from llvm 2.6 with clang, `clang-cc -emit-llvm -O2
> test.c`, on my Linux x86_64)
>
> For fun, I made a recursive function, but LLVM optimized it wrong (if
> I'm understanding C standards correctly).
>
> "void f() { f(); }"[see llvm-code in footnote 1]
> was optimized to be equivalent to "void f() {}"[also 1]. I
believe it
> should either be equivalent in effect to "void f() { while(1){}
}"[2],
> which produces an infinite loop, or perhaps lead to a stack overflow (as
> GCC might produce)... it's alright if the infinite loop is written
using
> tail-calls. All I expect is that it never actually return when you run it.
>
> Adding a store to a global volatile variable fixes it, as does a
puts("hi");
> "volatile int g; void f() { g = 1; f(); }"[3], or even the
version that
> never actually gets to the volatile store at all,
> "volatile int g; void f() { f(); g = 1; }"[4]
>
> However, a local volatile variable gets quite strange treatment
> "void f() { volatile int h; h = 1; f(); }"[5]
> (it looks to me like one iteration of the function is inlined -- as I
> guess happens in [3] and [4] -- but the recursive call deleted, as
> happens in [1]). This is worse than just a non-terminating function
> returning, as it also does not write to volatile stack variables the
> requisite infinite number of times.
>
> (I could not discover any obviously-*useful* code that gets
> mis-optimized, luckily, although problems persist when I add function
> arguments and return-values to the infinite recursive function.)
>
> And here are the LLVM code emitted from each C code:
>
> [1] "void f() { f(); }", or "void f() {}"
>
> define void @f() nounwind readnone {
> entry:
> ret void
> }
>
>
> [2] "void f() { while(1){} }"
>
> define void @f() nounwind readnone {
> entry:
> br label %bb
>
> bb: ; preds = %bb, %entry
> br label %bb
> }
>
>
> [3] "volatile int g; void f() { g = 1; f(); }"
>
> @g = common global i32 0 ; <i32*> [#uses=2]
>
> define void @f() nounwind {
> entry:
> volatile store i32 1, i32* @g, align 4
> volatile store i32 1, i32* @g, align 4
> tail call void @f() nounwind
> ret void
> }
>
>
> [4] "volatile int g; void f() { f(); g = 1; }"
>
> @g = common global i32 0 ; <i32*> [#uses=2]
>
> define void @f() nounwind {
> entry:
> tail call void @f() nounwind
> volatile store i32 1, i32* @g, align 4
> volatile store i32 1, i32* @g, align 4
> ret void
> }
>
>
> [5] "void f() { volatile int h; h = 1; f(); }"
>
> define void @f() nounwind readnone {
> entry:
> %h.i = alloca i32, align 4 ; <i32*> [#uses=1]
> %h = alloca i32, align 4 ; <i32*> [#uses=1]
> volatile store i32 1, i32* %h, align 4
> volatile store i32 1, i32* %h.i, align 4
> ret void
> }
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Hi Isaac,> For fun, I made a recursive function, but LLVM optimized it wrong (if > I'm understanding C standards correctly). > > "void f() { f(); }"[see llvm-code in footnote 1] > was optimized to be equivalent to "void f() {}"[also 1]. I believe it > should either be equivalent in effect to "void f() { while(1){} }"[2], > which produces an infinite loop, or perhaps lead to a stack overflow (as > GCC might produce)... it's alright if the infinite loop is written using > tail-calls. All I expect is that it never actually return when you run it.this sounds like a manifestation of bug 965, see http://llvm.org/PR965 Ciao, Duncan.
On 02/28/10 07:39, Duncan Sands wrote:> Hi Isaac, > >> For fun, I made a recursive function, but LLVM optimized it wrong (if >> I'm understanding C standards correctly). >> >> "void f() { f(); }"[see llvm-code in footnote 1] >> was optimized to be equivalent to "void f() {}"[also 1]. I believe it >> should either be equivalent in effect to "void f() { while(1){} }"[2], >> which produces an infinite loop, or perhaps lead to a stack overflow (as >> GCC might produce)... it's alright if the infinite loop is written using >> tail-calls. All I expect is that it never actually return when you run it. > > this sounds like a manifestation of bug 965, see http://llvm.org/PR965ah, you are quite right! I'd searched "recursion" to look for bugs, but the problem (as described in #965) is more general than that. (I'm quite familiar with Haskell, in which termination vs. nontermination is discussed much more than it is in C.) The optimization and the "willreturn" suggestion make sense to me. (Is it worth commenting on the bug-report? I guess not, since I don't actually have anything to add: it's already a clear bug with a clear solution: though perhaps having more test-cases for a testsuite is useful to LLVM?) -Isaac