[LLVMdev] C infinite recursion mis-optimized?

[Isaac Dupree]

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
}