The explanation of the "Guess the language by the error"

[sassa_nf]

So last time there was the puzzle that

char isOdd(unsigned int n) {
   return n && isEven(n+1);
}

char isEven(unsigned int n) {
   return isOdd(n+1);
}

both functions get optimized away into return 0.

The explanation that I've heard was fairly handwavy along the lines of "there is just one finite return, the other return is infinite, so the compiler makes a decision that only finite return is possible". This is rather thin.

What really is happening, is very more likely this:

We can see that isEven can be inlined into isOdd:

char isOdd(unsigned int n) {
   return n && isOdd(n+2);
}

We can also see that isOdd is a tail call:

char isOdd(unsigned int n) {
   if (n) return isOdd(n+2);
   return 0;
}

Now, tail call optimization:

char isOdd(unsigned int n) {
   while (n) n+=2;
   return 0;
}

Now, there are no happens-before edges between the loop and any other part of the program: the changes happen to a local variable, the changed value does not escape, and the changed value is not accessed in program order, too. So the unused computation is eliminated:

char isOdd(unsigned int n) {
   return 0;
}

---

If it is hard to grasp why unused computations can be eliminated, think of the following valid transformation: spawn a new thread, and execute that computation there; replace all program order edges with synchronization order edges (eg CompletableFuture.complete(n) at the end of the loop, and CompletableFuture.join() at every use of n in the thread that wants to read the final value computed by the loop). Since here there are no program order edges (and no synchronization edges) between expressions in the loop and the rest of the function (and the rest of the program), suspending the newly spawned thread does not stop the rest of the program from making progress: no accesses to n - no one is waiting for CompletableFuture.join() to finish, consequently no one is waiting for the looping thread to enter CompletableFuture.complete(n) - in the end, no one is waiting for the thread to be spawned. If you can suspend the thread forever, you may just as well never spawn it, too.

---

A funny consequence of this optimization is that it works out that an infinite conjunction is always false: 1 && 1 && 1 && ... == 0.

Comments

[juan_gandhi]

Funny. Sounds pretty logical, but how to give it math-looking foundation, beats me.

[sassa_nf]

...and how to write programs that do use all the computation results...

At least Rust could have warned about unused computations, but it doesn't:

fn is_odd(mut x: u32) -> bool {
   while x != 0 {
      x += 2;
   }
   return false;
}

fn main() {
    println!("{}, {}, {}, {}", is_odd(0), is_odd(1), is_odd(2), is_odd(3));
}

$ ./target/release/is_odd 
false, false, false, false

(GCC can't do this)

same for the recursive function - it can do TCO, too:

fn is_even(x: u32) -> bool {
   is_odd(x + 1)
}

fn is_odd(x: u32) -> bool {
   x != 0 && is_even(x + 1)
}

fn main() {
    println!("{}, {}, {}, {}", is_odd(0), is_odd(1), is_odd(2), is_odd(3));
}


$ ./target/release/is_odd 
false, false, false, false

Re: both functions get optimized away into return 0

[dememax]

As we know, that may be of use to remind the compiler which does it.
Otherwise, your judgement is too wide.

[juan_gandhi]

So, ok, the optimization of the original c program is buggy. Bottom is being ignored. Ok, a typical OOP programmer's feature, assuming every function is total.

[sassa_nf]

That's what I thought originally, but now I am not so sure.

Is the bottom ignored, if its computation is postponed to the future? Can we postpone it forever? If not, why not?

The absence of the happens-before edges allows us to move it into the future with no ill-effect.


What about foldr over an infinite list? Are we ignoring the bottom? No, we don't compute the tail, if the computation does not depend on the tail. So we get Weak Head Normal Form without computing the tail.

Same here. If while(...)... is pure, then its outcome is return $ .... If the remainder of the function ignores the value computed by while, it is return $ ... >>= λ _ -> return 0. So the loop is also not computed.

[juan_gandhi]

Before getting there, all this discussion is only good if we (strangely) assume that we iterate over natural numbers. Then the answer 0 is as good as Ramanujan's 1/12. But since we actually deal with a ring of numbers Z/(2^32) or something, the transformation is definitely buggy; not sure about the code.

[sassa_nf]

The code is buggy, because the recursion is not well-founded.

But the transformation is not buggy, and it does not depend on whether it is a ring of integers mod 2^32 or whatever.

1. Assuming we agree that tail call can be replaced by an update of the input arguments and a goto to the beginning of a function. Which in this case is as good as a while loop.

2. Can you not replace every use of n by a call to the function that loops the loop? That function, naturally, does not terminate, because of a bug in the original code. But if there are no uses of n, there are no calls of the function computing that n.

[juan_gandhi]

I'm almost convinced.

Simplifying odd&even example

[dememax]

It looks like this problem bothers people already a while. I've changed that example to:

static int foo(int i)
{
    return foo(i + 1);
}

int main(int argc, const char * argv[])
{
    return foo(argc);
}

Fortunately, clang says what he really does:

$ clang-10 -Wall -Wextra -S -fverbose-asm main.c -O2 -o - 
main.c:49:1: warning: all paths through this function will call itself [-Winfinite-recursion]
{
^
main.c:53:33: warning: unused parameter 'argv' [-Wunused-parameter]
int main(int argc, const char * argv[])
                                ^
	.text
	.file	"main.c"
	.globl	main                    # -- Begin function main
	.p2align	4, 0x90
	.type	main,@function
main:                                   # @main
	.cfi_startproc
# %bb.0:
	retq
.Lfunc_end0:
	.size	main, .Lfunc_end0-main
	.cfi_endproc
                                        # -- End function
	.ident	"clang version 10.0.0 "
	.section	".note.GNU-stack","",@progbits
2 warnings generated.

And gcc does infinite recursion:

$ gcc-11.0.0 -Wall -Wextra -S -fverbose-asm main.c -O2 -o - 
	.file	"main.c"
# GNU C17 (Gentoo 11.0.0_pre9999 p2, commit a8b522311beef5e02de15427e924752ea02def2a) version 11.0.0 20200708 (experimental) (x86_64-pc-linux-gnu)
#	compiled by GNU C version 11.0.0 20200708 (experimental), GMP version 6.2.0, MPFR version 4.0.2, MPC version 1.1.0, isl version isl-0.22.1-GMP

# GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
# options passed:  main.c -mtune=generic -march=x86-64 -O2 -Wall -Wextra
# ...<...cut...>...

main.c: In function ‘main’:
main.c:53:33: warning: unused parameter ‘argv’ [-Wunused-parameter]
   53 | int main(int argc, const char * argv[])
      |                    ~~~~~~~~~~~~~^~~~~~
	.text
	.section	.text.startup,"ax",@progbits
	.p2align 4
	.globl	main
	.type	main, @function
main:
.LFB1:
	.cfi_startproc
	.p2align 4,,10
	.p2align 3
.L2:
	jmp	.L2	#
	.cfi_endproc
.LFE1:
	.size	main, .-main
	.ident	"GCC: (Gentoo 11.0.0_pre9999 p2, commit a8b522311beef5e02de15427e924752ea02def2a) 11.0.0 20200708 (experimental)"
	.section	.note.GNU-stack,"",@progbits

LLVM loop optimization can make safe programs crash #28728

[dememax]

Open RalfJung opened this issue on Sep 29, 2015 · 83 comments
https://github.com/rust-lang/rust/issues/28728

Bug 965 - Infinite loops are optimized out in languages without forward progress guarantees (C, Rust

[dememax]

Status: NEW
Product: libraries
Component: Interprocedural Analyses
Version: trunk
Hardware: All All
Importance: P normal
Assignee: Unassigned LLVM Bugs
Reported: 2006-10-22 19:33 PDT by Nikhil Patil
Modified: 2020-07-07 02:39 PDT
https://bugs.llvm.org/show_bug.cgi?id=965

Re: LLVM loop optimization can make safe programs crash #28728

[sassa_nf]

I am not convinced progress guarantees have anything to do with it.

Re: not convinced progress guarantees

[dememax]

Talking about my last three comments on this page...

No, my point isn't to convince someone on the progress, but to find the reason, and judgements by the authors of building blocks which drive to this particular behaviour:

1. LLVM project (which is a base for rust, clang, ...) considers this as a bug since 2006-10-22 with status "NEW"
2. Rust project considers this as a bug since Sep 29, 2015 with status "Open"
3. The comment https://bugs.llvm.org/show_bug.cgi?id=965#c29 tells me that Clang project considers this as a problem too

That's why, as I sad in my first comment on this page, it is so important to point out that the context is clang compiler or the family of compilers build on LLVM.

P.S. Trying to play with my simplified example on https://godbolt.org/ I do the conclusion: clang is one and only one compiler which does the optimisation this way.

Re: not convinced progress guarantees

[sassa_nf]

Yes, thanks.

Java (HotSpot JVM and Graal compiler) also do this. There are no progress guarantees.

I think progress guarantees were brought up by someone, and now everyone dances around that statement.