[cfe-dev] Startling optimization

[Andrew Trick]

On Jun 19, 2011, at 9:56 PM, Robert Purves wrote:
> $ cat test.c
> int foo( int n ) 
> { 
>  int  a = 0, b = 0, c = 0, j; 
> 
>  for ( j = 0; j < n; j++ ) 
>  { 
>    a++; 
>    b = a | c; 
>    c = a; 
>  } 
>  return b; 
> }  
> 
> $ clang -O -S test.c
> 
> 
> _foo:
> 	pushq	%rbp
> 	movq	%rsp, %rbp
> 	testl	%edi, %edi
> 	jle	LBB0_2
> 	leal	-1(%rdi), %eax
> 	orl	%edi, %eax
> 	popq	%rbp
> 	ret
> LBB0_2:
> 	xorl	%eax, %eax
> 	popq	%rbp
> 	ret
> 
> Which parts of clang/llvm source should I read to learn how the loop is magically optimized away?

Hi Robert,

Benjamin Kramer and Xi Wang are both right. The magic trick requires a few steps:

1. -mem2reg and -loop-rotate put the code in a canonical form for optimization
2. -instcombine moves 'b = a | c' below the loop, since 'b' has no use in the loop
3. -indvars recognizes 'a' and 'c' as recurrences within the loop (ScalarEvolution), identifies the loop exit condition, and substitutes each use of a recurrence outside the loop with its value at loop exit.
4. -loop-deletion recognizes that the loop has no side effects and no variables defined in the loop are used outside the loop.

-Andy