Compiler loop optimizations

Hi Christian,


in the paper referenced below, I proposed a technique called loop nest
splitting (LNS) to optimize such code. LNS models loops and conditions
of it-statements depending on loop index variables using polytopes,
i.e. systems of linear inequations. Using these polytopes, I'm able to
see that the if-statement of foo10 is never true. The condition 'i ==
15' of foo10 is replaced by the truth value '0' so that constant
propagation, constant folding and dead code elimination have a true
chance to remove the entire if-statement from the loop.


Principally, LNS is also able to optimize foo100. However, my tool is
3 years old and not maintained any more - I have some technical
problems with the '==' operator in the if-statement of
foo100. However, if you replace 'if ( i == 15 )' by 'if ( i >= 15 )'
in foo100, my tool still works and performs the optimization.


LNS is implemented as source-to-source optimizer - it reads in an
ANSI-C program, analyzes and optimizes it and writes out the optimized
ANSI-C code. If you invoke LNS with the following piece of code
(which basically is your code except the '==' in foo100):


void foo10( )
{
    int a = 0;
    int i;


    for ( i = 0; i < 10; ++i )
    {
        if( i == 15 ) { a = 42; }
    }
}


void foo100( )
{
    int a = 42;
    int i;


    for ( i = 0; i < 100; ++i )
    {
        if ( i >= 15 ) { a = 0; }
    }
}


int main( void )
{
    foo10( );
    foo100( );
    return 0;
}


you get this code as result:


void foo10(void)
{
    int a;
    int i;


    a = 0;
    for (i = 0; i < 10; i++)
    {
    }
    return;
}


void foo100(void)
{
    int a;
    int i;


    a = 42;
    for (i = 0; i < 100; i++)
    {
        if (-i <= -15)
        {
            for (i = i; i <= 99; i++)
            {
                a = 0;
            }
            i -= 1;
        }
        else
        {
            if (15 <= i)
            {
                a = 0;
            }
        }
    }
    return;
}


int main(void)
{
    foo10();
    foo100();
    return 0;
}


The optimization of foo100 looks weird at first glance - have a look at the
paper to see what's going on there:


Heiko Falk and Peter Marwedel,
"Control Flow driven Splitting of Loop Nests at the Source Code Level",
In Proceedings of Design, Automation and Test in Europe Conference (DATE)
Munich / Germany, March 2003


_______________________________________________________________________


Heiko Falk


University of Dortmund
Department of Computer Science 12 (Embedded Systems Group)
Otto-Hahn-Strasse 16, Room E-19


44221 Dortmund
Germany


WWW: http://ls12-www.cs.uni-dortmund.de/~falk
_______________________________________________________________________

Return to the comp.compilers page.
Search the comp.compilers archives again.