eddic 1.2.3 - Better data-flow analysis

I finally finished the version 1.2.3 of eddic. I have been quite busy finishing my master thesis in february and then taking some vacations in United States, so this version came later than I wanted.

The main change is about the speed of the data-flow optimizations. I refactored a lot the data-flow to make it much faster. Some test cases are up to 10 times faster :)

There are still some work to do for speed of optimizations, but it is much better now. Dead Code Elimination and Constant Propagation still have to be made faster, but now the main bottleneck. In the next version of eddic, the parsing performance will be improved.

Inlining performance has also been greatly improved. The functions are considered in topological order of the call graph. This makes it much faster and moreover the resulting code is more efficient too.

There are also some improvements of the language. char and bool types now takes only one byte each. Copy constructors for structures containing field of structure type are now automatically generated. The grammar has been enhanced to support postfix operations in for loops.

Other improvements have been made to the optimization engine. A new optimization has been implemented: Loop Unswitching. This optimization transforms a code like that:

for(int i = 0; i < X; ++i){
    if(a){
        //Something
    } else {
        //Something else
    }
}

In some code like that:

if(a){
    for(int i = 0; i < X; ++i){
        //Something
    }
} else {
    for(int i = 0; i < X; ++i){
        //Something else
    }
}

when a doesn't depend on the loop body. The body of the loops is much faster in the second version.

The induction variable analysis is now able to handle loops with induction variable divided in each iteration. With that new feature, the call:

print(123);

is reduced to

print('1');
print('2');
print('3');

Another small optimization is that variables contributing only to themselves are now correctly identified as dead.

On the compiler side, the timing system has been greatly improved to contains almost all part of the compilation process. The timings for the complete compilation is available on the wiki.

Future Work

The next version of the EDDI compiler (eddic) will be the version 1.2.4.

Performances will stil be focused for this version. The first change will be to improve the performances of the parsing. Then, I'm gonna try to improve register allocation performances by improving handling of bound registers which I believe is a bottleneck.

There are also several refactorings that I think of doing to the code. I will probably also implement new minor language features, but I still don't know what.

Moreover, I have to serve in the army the next three weeks, so there won't be any progress these weeks.

Download

You can find the EDDI Compiler sources on the Github repository: https://github.com/wichtounet/eddic

The version is available in the v1.2.3 tag available in the GitHub or directly in the master branch.

Related articles