[tree-ssa-branch]: Boolean propagation

[Daniel Berlin <dberlin at dberlin dot org>]

Hey Diego, i've implemented boolean propagation.

Given code like:
int main(void)
{
        _Bool test;
        int e;
        if (0 != test )
        {
                int a;
                a = test + 5;
                printf ("%d\n", a);
        }
        else if (e == 3)
        {
                int a;
                a = test + 5;
                printf ("%d\n", a);
        }
}


the value of test is constant inside each arm of the if (since it can 
only have two values) , but since it's not said explicitly, const-prop 
never notices. 

Thus, without boolean propagation, you end up with runtime calculation of 
"test + 5" in both cases.

Boolean propagation is an incredibly simple optimization that takes the 
above source code, and turns it into:

int main(void)
{
        _Bool test;
        int e;
        if (0 != test )
        {
		test = 1;
                int a;
                a = test + 5;
                printf ("%d\n", a);
        }
        else if (e == 3)
        {
		test = 0;
                int a;
                a = test + 5;
                printf ("%d\n", a);
        }
}


Const prop will then prop the values for us where approriate, and we end 
up with "a" set to a constant (6 and 5, respectively) , rather than 
calculated at runtime.

This optimization actually applies a lot more than one would think, and 
also helps keep register pressure down when you use booleans (rather 
than the values they *must* have) in bodies of if/else's, etc.
like so:

bool test;

....
if (test != 0)
{
	<50 lines of code, none of which set test>
        
	afunction(test);
}

Here, test would normally be live over those 50 lines of code, and 
couldn't be rematerialized (since it's not set to a constant explicitly) 
but with boolean propagation, it won't be live past the condition.

With SIMPLE trees, it takes about 80 lines of code to implement 
boolean propagation.
(For those curious why we don't do it already, it's trickier to do at the 
RTL level, since we don't usually have type info (IE can't test for 
BOOLEAN_TYPE). And without the nice SIMPLE grammar, there are all 
kinds of special cases you would have to handle).

Rather than worry about propagating it to all the right statements on our 
own, we let const prop do it for us (either at the tree level, or the RTL level).
We just insert the assignment as the first statement in each arm.

My actual question is "should i bother to put this in a seperate file, and 
if so, what to name it".
The optimization is technically C/C++ specific in that IF_STMT exists in 
the c-*.h files, so putting it in tree-optimize.c would require pulling 
in some c-specific includes.  Although the IF_STMT is part of the SIMPLE 
grammar (IIRC), it would seem it should go into a separate file.
But it's also incredibily trivial.

Do we forsee more trivial SIMPLE specific optimizations? 
If so, I would imagine they should all go in the same file.
What to name it?
If not, where should I put the code?

As a side note, one could easily use the results of value-range 
propagation to do this, but probably not be able to implement it  in 80 
lines of code. 
:)
--Dan