EDDI Compiler 1.0 - Structures and Global Optimizations

Baptiste Wicht

I've the pleasure to announce the availability of version 1.0 of the EDDI Compiler (eddic).

This release adds one big enhancement to the language: Structures

Structures are used like in the C programming language:

struct Complex {
    int imag;
    int real;
}

void main(){
    Complex c;
    c.imag = 222;
    c.real = 666;

    println(c.imag);
    println(c.real);

    c.imag += 111;
    c.real += 222;

    println(c.imag);
    println(c.real);

    test(c);

    if(c.b){
        println(c.imag);
    } else {
        println(c.real);
    }
}

void test(Complex a){
    println(a.imag);
    println(a.real);
}

For now on, you can declare structures, use local variables of the struct type and pass them as parameter. But the usage of structure is still limited, there are no way to return a structure from a function and no way to pass a structure by reference. Another limitation is that a member of struct cannot be of a struct type. At least, the last limitation will be addressed in the next version of eddic.

Another main change is the use of a new low-level Intermediate Representation (LTAC). This change is describe more in details in this article.

The main other change is the use of a data-flow framework for global optimization in the optimization engine. An optimization is global if it takes into account all the basic blocks of the function being optimized. For that, it takes a Control-Flow graph of the function and follow the logical flow of the function to determine what can be optimized. Two old optimization have been transformed from local to global: Constant Propagation and Copy Propagation. They have also been merged for being more efficient, so they are done both in one pass of the flow. I also implemented a new technique: Common Subexpression Elimination. This optimization make sure that no computation is made when the result is still available. The control flow graph is handled with the Boost Graph Library.

I also fixed a performance issue on the Optimization Engine. Before, the optimization were done for the whole program and if one optimization was successful, all the optimization techniques were tried again on the whole program. Now, there are made one function at a time and restarted only for this function. It should prove faster on problem with a lot of functions.

In the side of the assembly generation, I changed the way the floats constants are handled. Before, a general purpose register was used to load the constant and then load it in the SSE register. To avoid having to use a GP Register, I used a constant float pool and loaded the float directly from memory to the SSE Register.

On the compiler side, I added several new unit test and fixed the old tests. They were lots of bugs in the tests itself that made that they were not working at all. The test suite is now much more robust and showed me lots of other bugs.

I removed the dependency to Boost Chrono by relying on the new std::chrono library.

Future work

The next version will be the 1.0.1 version. There will be several changes with this version.

I will improve the support of structures. I will add the support for struct inside structs and perhaps passing struct by reference (which would also means adding supports for references for other types as well).

I will also make more improvements to the optimization engine. I will add at least one new data-flow optimization and I will try to make the optimization pass faster.

Finally, as ever, I will certainly make some refactorings on some parts of the Compiler, but it starts looking good.