[LLVMdev] C infinite recursion mis-optimized?

[Conrado Miranda]

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