[IPOL discuss] Fast DCT using FFTW3

[Pascal Monasse]

Hi Miguel,

Yes, your example works according to your analysis, but only because your 
function f is simple enough and the compiler can inline it instead of doing a 
function call. But I think if f is complex enough, even it has no side effect 
(no printf, independent of any global variable), the compiler would not be 
able to inline it and it would still be called 3 times, even though the result 
is the same at each call.

Best,
Pascal

On Tuesday, February 28, 2012 10:57:36 PM Miguel Colom wrote:
> Hi Pascal,
> 
> > Hi Miguel,
> > 
> >> It even analyzes the numerical expressions and tries to compute it the
> >> shorter and faster way.
> >> For example, if y = f(y) + 2*f(y) + 3*f(y), it doesn't call f(y) three
> >> times.
> > 
> > I doubt that the compiler would dare such an aggressive optimization. f
> > may
> > have side effects that the compiler is not able to analyze, therefore it
> > may
> > think it is safer to call f(y) three times...
> 
> GCC is really smart doing optimizations. Of course, it can be configured
> with the -O flag to set the level of optimization.
> 
> To prove it, I wrote this small program:
> 
> #include <stdio.h>
> 
> int f(int x) {
>   return x*x*x;
> }
> 
> int main(int argc, char *argv[]) {
>  int result;
>  int x = 23;
> 
>  result = 2*f(x) + 3*f(x) + 4*f(x);
> 
>  printf("The result is %d\n", result);
>  return 0;
> }
> 
> That is, f(x) is the x^3 function and then the program just computes
> 2*f(x) + 3*f(x) + 4*f(x) and prints the result.
> 
> If no optimization is set, the intermediate assembly GCC produces is the
> following:
> 
> ------------------------------------
> 	.file	"main.c"
> 	.text
> 	.globl	f
> 	.type	f, @function
> f:
> .LFB0:
> 	.cfi_startproc
> 	pushl	%ebp
> 	.cfi_def_cfa_offset 8
> 	.cfi_offset 5, -8
> 	movl	%esp, %ebp
> 	.cfi_def_cfa_register 5
> 	movl	8(%ebp), %eax
> 	imull	8(%ebp), %eax
> 	imull	8(%ebp), %eax
> 	popl	%ebp
> 	.cfi_def_cfa 4, 4
> 	.cfi_restore 5
> 	ret
> 	.cfi_endproc
> .LFE0:
> 	.size	f, .-f
> 	.section	.rodata
> .LC0:
> 	.string	"The result is %d\n"
> 	.text
> 	.globl	main
> 	.type	main, @function
> main:
> .LFB1:
> 	.cfi_startproc
> 	pushl	%ebp
> 	.cfi_def_cfa_offset 8
> 	.cfi_offset 5, -8
> 	movl	%esp, %ebp
> 	.cfi_def_cfa_register 5
> 	pushl	%ebx
> 	andl	$-16, %esp
> 	subl	$32, %esp
> 	movl	$23, 24(%esp)
> 	movl	24(%esp), %eax
> 	movl	%eax, (%esp)
> 	.cfi_offset 3, -12
> 	call	f
> 	leal	(%eax,%eax), %ebx
> 	movl	24(%esp), %eax
> 	movl	%eax, (%esp)
> 	call	f
> 	movl	%eax, %edx
> 	movl	%edx, %eax
> 	addl	%eax, %eax
> 	addl	%edx, %eax
> 	addl	%eax, %ebx
> 	movl	24(%esp), %eax
> 	movl	%eax, (%esp)
> 	call	f
> 	sall	$2, %eax
> 	addl	%ebx, %eax
> 	movl	%eax, 28(%esp)
> 	movl	$.LC0, %eax
> 	movl	28(%esp), %edx
> 	movl	%edx, 4(%esp)
> 	movl	%eax, (%esp)
> 	call	printf
> 	movl	$0, %eax
> 	movl	-4(%ebp), %ebx
> 	leave
> 	.cfi_restore 5
> 	.cfi_def_cfa 4, 4
> 	.cfi_restore 3
> 	ret
> 	.cfi_endproc
> .LFE1:
> 	.size	main, .-main
> 	.ident	"GCC: (Ubuntu/Linaro 4.6.1-9ubuntu3) 4.6.1"
> 	.section	.note.GNU-stack,"", at progbits
> ------------------------------------
> The compiler defines the function f and then calls it three times.
> 
> 
> Nevertheless, if we compile it with "gcc -O99 -S main.c" the output is the
> following:
> ------------------------------------
> 	.file	"main.c"
> 	.text
> 	.p2align 4,,15
> 	.globl	f
> 	.type	f, @function
> f:
> .LFB22:
> 	.cfi_startproc
> 	movl	4(%esp), %edx
> 	movl	%edx, %eax
> 	imull	%edx, %eax
> 	imull	%edx, %eax
> 	ret
> 	.cfi_endproc
> .LFE22:
> 	.size	f, .-f
> 	.section	.rodata.str1.1,"aMS", at progbits,1
> .LC0:
> 	.string	"The result is %d\n"
> 	.section	.text.startup,"ax", at progbits
> 	.p2align 4,,15
> 	.globl	main
> 	.type	main, @function
> main:
> .LFB23:
> 	.cfi_startproc
> 	pushl	%ebp
> 	.cfi_def_cfa_offset 8
> 	.cfi_offset 5, -8
> 	movl	%esp, %ebp
> 	.cfi_def_cfa_register 5
> 	andl	$-16, %esp
> 	subl	$16, %esp
> 	movl	$109503, 8(%esp)
> 	movl	$.LC0, 4(%esp)
> 	movl	$1, (%esp)
> 	call	__printf_chk
> 	xorl	%eax, %eax
> 	leave
> 	.cfi_restore 5
> 	.cfi_def_cfa 4, 4
> 	ret
> 	.cfi_endproc
> .LFE23:
> 	.size	main, .-main
> 	.ident	"GCC: (Ubuntu/Linaro 4.6.1-9ubuntu3) 4.6.1"
> 	.section	.note.GNU-stack,"", at progbits
> ------------------------------------
> 
> The difference is clear: now the function f is NEVER called.
> The compiler analyzes the expression, computes the result at compile-time
> if it's possible and substitutes the call f(x) with its result (109503)
> with the instruction "movl	$109503, 8(%esp)"
> 
> However, if the compiler detects that the function does something else
> that the program needs, the function is called three times.
> 
> int f(int x) {
>   printf("Do something\n");
>   return x*x*x;
> }
> 
> Best,
> Miguel
> 
> 
> _______________________________________________
> discuss mailing list
> discuss at list.ipol.im
> http://tools.ipol.im/mailman/listinfo/discuss
-- 
Pascal Monasse
IMAGINE, Ecole des Ponts ParisTech
Tel: 01 64 15 21 76