In Haskell
The following Haskell code is supposed to just output "hello".
main = print $ times 1000000000000 id "hello"
times 0 _ x = x
times n f x = times (n-1) f (f x)
The times function I defined applies the given function many times.
times 3 f xis...times 2 f (f x)times 1 f (f (f x))times 0 f (f (f (f x)))f (f (f x))
id, defined in Prelude, just returns the given argument. You may want to assume the GHC internal optimizer to eliminate any id call. In other words, the Haskell code in the very beginning is supposed to be transformed just to main = print "hello".
Unfortunately, no it doesn't, even with -O2 option.
$ ghc -O2 a.hs -o a
$ ./a
... (long long hours) ..
In C
I just translated the original Haskell code to C.
#include "stdio.h"
char *id(char *x) {
return x;
}
char *times(long long n, char *(*f)(char *), char *x) {
if (n == 0) {
return x;
} else {
return times(n-1, f, f(x));
}
}
int main(int argc, char const* argv[]) {
puts(times(1000000000000LL, id, "hello"));
return 0;
}
I tried it with GCC and Clang.
GCC on Mac:
i686-apple-darwin10-gcc-4.2.1 (GCC) 4.2.1 (Apple Inc. build 5666) (dot 3)
$ gcc -O2 a.c -o a $ ./a ... (long long hours) ..
The assembly code for the main function with -O2 -m32 option is the following.
_main:
pushl %ebp
movl %esp, %ebp
pushl %ebx
subl $20, %esp
call L13
"L00000000001$pb":
L13:
popl %ebx
leal LC0-"L00000000001$pb"(%ebx), %eax
movl %eax, 8(%esp)
leal _id-"L00000000001$pb"(%ebx), %eax
movl %eax, 4(%esp)
movl $-727379968, (%esp)
call _times
movl %eax, (%esp)
call _puts
xorl %eax, %eax
addl $20, %esp
popl %ebx
leave
ret
You see it's calling _times for sure.
Clang:
$ clang -O2 a.c -o a
$ ./a
hello
This gives you the message immediately!
The below is the generated LLVM IR. You can easily tell that it just calls puts function directly. Note that the @.str const is just "hello" ending with null.
define i32 @main(i32 %argc, i8** nocapture %argv) nounwind uwtable ssp {
entry:
%call1 = tail call i32 @puts(i8* getelementptr inbounds ([6 x i8]* @.str, i64 0, i64 0)) nounwind
ret i32 0
}
GCC on Linux:
gcc 4.4
main: pushl %ebp movl %esp, %ebp andl $-16, %esp subl $16, %esp movl $.LC0, (%esp) call puts xorl %eax, %eax leave ret
It ran like the one with Clang!
When the big number isn't long long
I wrote the first argument of times in C as int at first.
I got warning messages from both GCC and Clang that the value, 1000000000000, was too big for int. In the case, GCC on Linux made the following assembly code.
main:
pushl %ebp
movl %esp, %ebp
.L11:
jmp .L11
It's just an infinite loop! That actually makes sense because any int values never go to non-int value 1000000000000.
Summary
- GHC doesn't eliminate
idin optimization - GCC eliminates it except for Apple GCC 4.2
- Clang eliminates id
- Some optimizations can conflict if the code depends on undefined behaviour
