order of passes (was: importing code in IR (GIMPLE and/or RTL))

[Luchezar Belev <l_belev at yahoo dot com>]

--- Jim Wilson <wilson@specifixinc.com> wrote:
> [...]
> The RTL is only a partial representation of a function.  Much of the 
> info is in various global variables which are only created or maintained 
> in certain optimization passes.  Some of the info is RTL annotatations 
> that are only created or maintained in certain optimization passes. 
> Most passes make assumptions that certain optimizations have or have not 
> been performed yet.  The result is that usually the location of an RTL 
> [...]

This doesn't sound good.

Here is one concrete example where the order is suboptimal:
The Ackermann function; the c code is:

int A(int m, int n)
{
	if (m == 0) return n + 1;
	if (n == 0) return A(m - 1, 1);
	return A(m - 1, A(m, n - 1));
}

the generated code with -O3 -fno-reorder-blocks looks like:
(i give the c equivalent)

int A(int m, int n)
{
	_beginning:
	if (m == 0) goto _end;
	if (n != 0) goto _common_case;
	m = m - 1;
	n = 1;
	goto _beginning;

	_common_case:
	n = A(m, n - 1);
	m = m - 1;
	goto _beginning;

	_end:
	return n + 1;
}

the generated code with basic block reordering enabled is:

int A(int m, int n)
{
	_beginning:
	if (m == 0) goto _end;

	_partial_beginning:
	if (n != 0) goto _common_case;
	m = m - 1;
	n = 1;
	if (m != 0) goto _partial_beginning;

	_end:
	return n + 1;

	_common_case:
	n = A(m, n - 1);
	m = m - 1;
	goto _beginning;
}

Look at the part after the _partial_beginning label;
n is being set to 1 (which is non-zero) and then
if m==0 the control is directed to the now superfluous
examination whether n==0. Instead it could go directly
to _common_case.
It seems that this problam is caused by the fact that
the GSCE, which would optimize away this superfluous branch,
is ran before the basic block reordering, and at the moment
when it ran, the code still looked more like the first
case (with -fno-reorder-blocks), so it couldn't do much.

Lucho.




	
		
__________________________________
Do you Yahoo!?
SBC Yahoo! - Internet access at a great low price.
http://promo.yahoo.com/sbc/