Guess the language by the error
Aug. 6th, 2020 04:54 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sassa_nfchar isEven(unsigned int n);
char isOdd(unsigned int n) {
return n && isEven(n+1);
}
char isEven(unsigned int n) {
return isOdd(n+1);
}
int main(int argc, char** argv) {
printf("%d %d\n", argc, isEven(argc));
return 0;
}This program decides all integers are not even, if compiled with gcc -O2.
The cause of this is that both isOdd and isEven were replaced by a constant 0. Apparently, because http://eel.is/c++draft/intro.progress allows the compiler to assume that isOdd can only return 0, without proving that it terminates.
Basically, if it terminates, then it can only return through "n && ..." evaluating to 0. But now it is ok to assume it always returns 0 - because that's the only way it could have terminated.
All it took to solve Entscheidungsproblem, was a committee of clever engineers: all C programs terminate. Give Gödel some slack! He couldn't have known that, could he?
Re: isEven&isOdd - compiled with gcc -O2
Date: 2020-08-06 04:47 pm (UTC)Re: isEven&isOdd - compiled with gcc -O2
Date: 2020-08-06 05:08 pm (UTC)I am on Mac,
and I get the body of isOdd compiled essentially into
(But I think I also have an explanation why such an optimization is valid!)
Re: isEven&isOdd - compiled with gcc -O2 - gcc 11
Date: 2020-08-06 06:09 pm (UTC)With my stable gcc 9.3.0 version, the stack looks like this:
And now with gcc 11 (Gentoo 11.0.0_pre9999 p2, commit a8b522311beef5e02de15427e924752ea02def2a) it's different:
And with clang 10.0.0, it's executes normally:clang version 9.0.1 gives the same result.
Re: isEven&isOdd - compiled with gcc -O2 - gcc 11
Date: 2020-08-06 06:44 pm (UTC)Re: isEven&isOdd - compiled with gcc -O2 - clang
Date: 2020-08-06 06:57 pm (UTC)$ for j in "" "2" "_ 3" "_ _ 4" ; do for i in ./main-clang-* ; do echo "${i##./main-} $j:" ; $i $j ; done ; done clang-10 : 1 0 clang-9 : 1 0 clang-10 2: 2 0 clang-9 2: 2 0 clang-10 _ 3: 3 0 clang-9 _ 3: 3 0 clang-10 _ _ 4: 4 0 clang-9 _ _ 4: 4 0 $ clang-9 -S -fverbose-asm main.c -O2 -o - .text .file "main.c" .globl isOdd # -- Begin function isOdd .p2align 4, 0x90 .type isOdd,@function isOdd: # @isOdd .cfi_startproc # %bb.0: xorl %eax, %eax retq .Lfunc_end0: .size isOdd, .Lfunc_end0-isOdd .cfi_endproc # -- End function .globl isEven # -- Begin function isEven .p2align 4, 0x90 .type isEven,@function isEven: # @isEven .cfi_startproc # %bb.0: xorl %eax, %eax retq .Lfunc_end1: .size isEven, .Lfunc_end1-isEven .cfi_endproc # -- End function .globl main # -- Begin function main .p2align 4, 0x90 .type main,@function main: # @main .cfi_startproc # %bb.0: pushq %rax .cfi_def_cfa_offset 16 movl %edi, %esi movl $.L.str, %edi xorl %edx, %edx xorl %eax, %eax callq printf xorl %eax, %eax popq %rcx .cfi_def_cfa_offset 8 retq .Lfunc_end2: .size main, .Lfunc_end2-main .cfi_endproc # -- End function .type .L.str,@object # @.str .section .rodata.str1.1,"aMS",@progbits,1 .L.str: .asciz "%d %d\n" .size .L.str, 7 .ident "clang version 9.0.1 " .section ".note.GNU-stack","",@progbitsRe: isEven&isOdd - compiled with gcc -O2 - clang
Date: 2020-08-06 07:51 pm (UTC)Thanks!
Re: isEven&isOdd - static funcs
Date: 2020-08-06 07:08 pm (UTC)#include <stdio.h> static char isEven(unsigned int n); static char isOdd(unsigned int n) { return n && isEven(n+1); } static char isEven(unsigned int n) { return isOdd(n+1); } int main(int argc, char** argv) { printf("%d %d\n", argc, isEven(argc)); return 0; } $ clang-9 -S -fverbose-asm main.c -O2 -o - .text .file "main.c" .globl main # -- Begin function main .p2align 4, 0x90 .type main,@function main: # @main .cfi_startproc # %bb.0: pushq %rax .cfi_def_cfa_offset 16 movl %edi, %esi movl $.L.str, %edi xorl %edx, %edx xorl %eax, %eax callq printf xorl %eax, %eax popq %rcx .cfi_def_cfa_offset 8 retq .Lfunc_end0: .size main, .Lfunc_end0-main .cfi_endproc # -- End function .type .L.str,@object # @.str .section .rodata.str1.1,"aMS",@progbits,1 .L.str: .asciz "%d %d\n" .size .L.str, 7 .ident "clang version 9.0.1 " .section ".note.GNU-stack","",@progbits $ gcc -S -fverbose-asm main.c -O2 -o - .file "main.c" # GNU C17 (Gentoo 9.3.0-r1 p3) version 9.3.0 (x86_64-pc-linux-gnu) # compiled by GNU C version 9.3.0, 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 -auxbase-strip - -O2 # -fverbose-asm # options enabled: -fPIC -fPIE -faggressive-loop-optimizations # -falign-functions -falign-jumps -falign-labels -falign-loops # -fassume-phsa -fasynchronous-unwind-tables -fauto-inc-dec # -fbranch-count-reg -fcaller-saves -fcode-hoisting # -fcombine-stack-adjustments -fcommon -fcompare-elim -fcprop-registers # -fcrossjumping -fcse-follow-jumps -fdefer-pop # -fdelete-null-pointer-checks -fdevirtualize -fdevirtualize-speculatively # -fdwarf2-cfi-asm -fearly-inlining -feliminate-unused-debug-types # -fexpensive-optimizations -fforward-propagate -ffp-int-builtin-inexact # -ffunction-cse -fgcse -fgcse-lm -fgnu-runtime -fgnu-unique # -fguess-branch-probability -fhoist-adjacent-loads -fident -fif-conversion # -fif-conversion2 -findirect-inlining -finline -finline-atomics # -finline-functions-called-once -finline-small-functions -fipa-bit-cp # -fipa-cp -fipa-icf -fipa-icf-functions -fipa-icf-variables -fipa-profile # -fipa-pure-const -fipa-ra -fipa-reference -fipa-reference-addressable # -fipa-sra -fipa-stack-alignment -fipa-vrp -fira-hoist-pressure # -fira-share-save-slots -fira-share-spill-slots # -fisolate-erroneous-paths-dereference -fivopts -fkeep-static-consts # -fleading-underscore -flifetime-dse -flra-remat -flto-odr-type-merging # -fmath-errno -fmerge-constants -fmerge-debug-strings # -fmove-loop-invariants -fomit-frame-pointer -foptimize-sibling-calls # -foptimize-strlen -fpartial-inlining -fpeephole -fpeephole2 -fplt # -fprefetch-loop-arrays -free -freg-struct-return -freorder-blocks # -freorder-blocks-and-partition -freorder-functions -frerun-cse-after-loop # -fsched-critical-path-heuristic -fsched-dep-count-heuristic # -fsched-group-heuristic -fsched-interblock -fsched-last-insn-heuristic # -fsched-rank-heuristic -fsched-spec -fsched-spec-insn-heuristic # -fsched-stalled-insns-dep -fschedule-fusion -fschedule-insns2 # -fsemantic-interposition -fshow-column -fshrink-wrap # -fshrink-wrap-separate -fsigned-zeros -fsplit-ivs-in-unroller # -fsplit-wide-types -fssa-backprop -fssa-phiopt -fstack-protector-strong # -fstdarg-opt -fstore-merging -fstrict-aliasing # -fstrict-volatile-bitfields -fsync-libcalls -fthread-jumps # -ftoplevel-reorder -ftrapping-math -ftree-bit-ccp -ftree-builtin-call-dce # -ftree-ccp -ftree-ch -ftree-coalesce-vars -ftree-copy-prop -ftree-cselim # -ftree-dce -ftree-dominator-opts -ftree-dse -ftree-forwprop -ftree-fre # -ftree-loop-if-convert -ftree-loop-im -ftree-loop-ivcanon # -ftree-loop-optimize -ftree-parallelize-loops= -ftree-phiprop -ftree-pre # -ftree-pta -ftree-reassoc -ftree-scev-cprop -ftree-sink -ftree-slsr # -ftree-sra -ftree-switch-conversion -ftree-tail-merge -ftree-ter # -ftree-vrp -funit-at-a-time -funwind-tables -fverbose-asm # -fzero-initialized-in-bss -m128bit-long-double -m64 -m80387 # -malign-stringops -mavx256-split-unaligned-load # -mavx256-split-unaligned-store -mfancy-math-387 -mfp-ret-in-387 -mfxsr # -mglibc -mieee-fp -mlong-double-80 -mmmx -mno-sse4 -mpush-args -mred-zone # -msse -msse2 -mstv -mtls-direct-seg-refs -mvzeroupper .text .p2align 4 .type isOdd, @function isOdd: .LFB23: .cfi_startproc # main.c:27: return n && isEven(n+1); testl %edi, %edi # n jne .L11 #, xorl %eax, %eax # # main.c:28: } ret .p2align 4,,10 .p2align 3 .L11: # main.c:26: static char isOdd(unsigned int n) { subq $8, %rsp #, .cfi_def_cfa_offset 16 # main.c:31: return isOdd(n+1); addl $2, %edi #, tmp87 call isOdd # # main.c:27: return n && isEven(n+1); testb %al, %al # tmp91 setne %al #, # main.c:28: } addq $8, %rsp #, .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE23: .size isOdd, .-isOdd .section .rodata.str1.1,"aMS",@progbits,1 .LC0: .string "%d %d\n" .section .text.startup,"ax",@progbits .p2align 4 .globl main .type main, @function main: .LFB25: .cfi_startproc subq $8, %rsp #, .cfi_def_cfa_offset 16 # main.c:34: int main(int argc, char** argv) { movl %edi, %edx # tmp92, argc # main.c:31: return isOdd(n+1); leal 1(%rdi), %edi #, tmp89 call isOdd # # /usr/include/bits/stdio2.h:107: return __printf_chk (__USE_FORTIFY_LEVEL - 1, __fmt, __va_arg_pack ()); leaq .LC0(%rip), %rsi #, movl $1, %edi #, # main.c:35: printf("%d %d\n", argc, isEven(argc)); movsbl %al, %ecx # tmp93, _6 # /usr/include/bits/stdio2.h:107: return __printf_chk (__USE_FORTIFY_LEVEL - 1, __fmt, __va_arg_pack ()); xorl %eax, %eax # call __printf_chk@PLT # # main.c:37: } xorl %eax, %eax # addq $8, %rsp #, .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE25: .size main, .-main .ident "GCC: (Gentoo 9.3.0-r1 p3) 9.3.0" .section .note.GNU-stack,"",@progbits $ gcc-11.0.0 -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 -fverbose-asm # options enabled: -fPIC -fPIE -faggressive-loop-optimizations # -falign-functions -falign-jumps -falign-labels -falign-loops # -fallocation-dce -fasynchronous-unwind-tables -fauto-inc-dec # -fbranch-count-reg -fcaller-saves -fcode-hoisting # -fcombine-stack-adjustments -fcompare-elim -fcprop-registers # -fcrossjumping -fcse-follow-jumps -fdefer-pop # -fdelete-null-pointer-checks -fdevirtualize -fdevirtualize-speculatively # -fdwarf2-cfi-asm -fearly-inlining -feliminate-unused-debug-symbols # -feliminate-unused-debug-types -fexpensive-optimizations # -fforward-propagate -ffp-int-builtin-inexact -ffunction-cse -fgcse # -fgcse-lm -fgnu-unique -fguess-branch-probability -fhoist-adjacent-loads # -fident -fif-conversion -fif-conversion2 -findirect-inlining -finline # -finline-atomics -finline-functions -finline-functions-called-once # -finline-small-functions -fipa-bit-cp -fipa-cp -fipa-icf # -fipa-icf-functions -fipa-icf-variables -fipa-profile -fipa-pure-const # -fipa-ra -fipa-reference -fipa-reference-addressable -fipa-sra # -fipa-stack-alignment -fipa-vrp -fira-hoist-pressure # -fira-share-save-slots -fira-share-spill-slots # -fisolate-erroneous-paths-dereference -fivopts -fkeep-static-consts # -fleading-underscore -flifetime-dse -flra-remat -fmath-errno # -fmerge-constants -fmerge-debug-strings -fmove-loop-invariants # -fomit-frame-pointer -foptimize-sibling-calls -foptimize-strlen # -fpartial-inlining -fpeephole -fpeephole2 -fplt -fprefetch-loop-arrays # -free -freg-struct-return -freorder-blocks -freorder-blocks-and-partition # -freorder-functions -frerun-cse-after-loop # -fsched-critical-path-heuristic -fsched-dep-count-heuristic # -fsched-group-heuristic -fsched-interblock -fsched-last-insn-heuristic # -fsched-rank-heuristic -fsched-spec -fsched-spec-insn-heuristic # -fsched-stalled-insns-dep -fschedule-fusion -fschedule-insns2 # -fsemantic-interposition -fshow-column -fshrink-wrap # -fshrink-wrap-separate -fsigned-zeros -fsplit-ivs-in-unroller # -fsplit-wide-types -fssa-backprop -fssa-phiopt -fstack-protector-strong # -fstdarg-opt -fstore-merging -fstrict-aliasing # -fstrict-volatile-bitfields -fsync-libcalls -fthread-jumps # -ftoplevel-reorder -ftrapping-math -ftree-bit-ccp -ftree-builtin-call-dce # -ftree-ccp -ftree-ch -ftree-coalesce-vars -ftree-copy-prop -ftree-cselim # -ftree-dce -ftree-dominator-opts -ftree-dse -ftree-forwprop -ftree-fre # -ftree-loop-distribute-patterns -ftree-loop-if-convert -ftree-loop-im # -ftree-loop-ivcanon -ftree-loop-optimize -ftree-parallelize-loops= # -ftree-phiprop -ftree-pre -ftree-pta -ftree-reassoc -ftree-scev-cprop # -ftree-sink -ftree-slsr -ftree-sra -ftree-switch-conversion # -ftree-tail-merge -ftree-ter -ftree-vrp -funit-at-a-time -funwind-tables # -fverbose-asm -fzero-initialized-in-bss -m128bit-long-double -m64 -m80387 # -malign-stringops -mavx256-split-unaligned-load # -mavx256-split-unaligned-store -mfancy-math-387 -mfp-ret-in-387 -mfxsr # -mglibc -mieee-fp -mlong-double-80 -mmmx -mno-sse4 -mpush-args -mred-zone # -msse -msse2 -mstv -mtls-direct-seg-refs -mvzeroupper .text .p2align 4 .type isOdd, @function isOdd: .LFB23: .cfi_startproc # main.c:27: return n && isEven(n+1); movl %edi, %eax # n, tmp91 andl $-3, %eax #, tmp91 cmpl $-4, %eax #, tmp91 je .L3 #, testl %edi, %edi # n jne .L15 #, .L3: xorl %eax, %eax # # main.c:28: } ret .p2align 4,,10 .p2align 3 .L15: # main.c:26: static char isOdd(unsigned int n) { subq $8, %rsp #, .cfi_def_cfa_offset 16 # main.c:31: return isOdd(n+1); addl $6, %edi #, tmp96 call isOdd # # main.c:27: return n && isEven(n+1); testb %al, %al # tmp100 setne %al #, # main.c:28: } addq $8, %rsp #, .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE23: .size isOdd, .-isOdd .section .rodata.str1.1,"aMS",@progbits,1 .LC0: .string "%d %d\n" .section .text.startup,"ax",@progbits .p2align 4 .globl main .type main, @function main: .LFB25: .cfi_startproc subq $8, %rsp #, .cfi_def_cfa_offset 16 # main.c:34: int main(int argc, char** argv) { movl %edi, %edx # tmp92, argc # main.c:31: return isOdd(n+1); leal 1(%rdi), %edi #, tmp89 call isOdd # # /usr/include/bits/stdio2.h:107: return __printf_chk (__USE_FORTIFY_LEVEL - 1, __fmt, __va_arg_pack ()); leaq .LC0(%rip), %rsi #, movl $1, %edi #, # main.c:35: printf("%d %d\n", argc, isEven(argc)); movsbl %al, %ecx # tmp93, _6 # /usr/include/bits/stdio2.h:107: return __printf_chk (__USE_FORTIFY_LEVEL - 1, __fmt, __va_arg_pack ()); xorl %eax, %eax # call __printf_chk@PLT # # main.c:37: } xorl %eax, %eax # addq $8, %rsp #, .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE25: .size main, .-main .ident "GCC: (Gentoo 11.0.0_pre9999 p2, commit a8b522311beef5e02de15427e924752ea02def2a) 11.0.0 20200708 (experimental)" .section .note.GNU-stack,"",@progbits