EDDI Compiler 1.1.4 – Graph Coloring Register Allocation

Baptiste Wicht

I'm proud to announce the release of the version 1.1.4 of the EDDI Compiler (eddic).

This version has taken me much more time than I thought but I also added much more features than I thought too.

There are few changes of the language itself, the main changes are in the optimization passes or in the compiler.

For the language, it is now possible to use dynamically allocated arrays. The this pointer is now implicit in member functions.

The standard library has been improved by the addition of a Doubly-Linked List. This list uses the templates so that it is generic. It is possible to add elements to the front and the back of the list. The list is iterable using iterators (bidirectional).

The template engine has been almost entirely rewritten. The previous version was too limited and there was code to handle the templates almost in the whole front-end. Now, the templates are handled recursively at each point where they can appear. For not the template instantiation depth is not limited, but this will be done in the next version of eddic.

The major change of this version is the use of a Graph Coloring Register Allocator ! This allocator is based on a Chaitin-style allocator. This greatly improves the quality of the generated assembly. The LTAC compilation is now made in two phase. In the first one, only pseudo registers are used. This first pass includes a first cleanup pass. Then, the register allocator replaces all the pseudo registers by actual registers. Finally, the LTAC IR is optimized like before. In the future, it will be improved further. The coalescing and renumbering passes are a bit limited for now and Chaitin-Briggs optimistic coloring will be used in the future.

The data-flow framework has been improved to support data-flow analysis of LTAC program. For now, the only analysis that does that is Live Registers Analysis. This analysis is used by the Register Allocator by the Dead Code Elimination that is run in LTAC code.

The MTAC optimization engine has been greatly improved by the use of a powerful pass manager that runs the optimization in the correct order and that gives them the necessary information. The Control Flow Graph is now updated by the different passes and never invalidated. The CFG is computed only once before the optimizations.

The MTAC optimization engine has also new optimization passes regarding to loops: Loop Invariant Code Motion, Loop Strength Reduction and Complete Loop Peeling. The loops are discovered by a dominance analysis implemented using the Lengauer-Tarjan's algorithm.

The inliner has also beeen greatly improved. The inlining decision is now taken at the call site level. It means that only some calls to a function can be inlined and not the whole function. The inliner now supports functions with string parameters. Moreover, the inliner heuristic takes the number of constant parameters at the call site into account to take its decision.

On the side of the Compiler, there are several improvements.

The whole compilation process has been made thread safe.
The Test Suite can be run in parallel
The Middle-End and Back-Ends have been clearly separated (More information on the Wiki).
The LTAC Intermediate Representation now keeps the Basic Blocks of the MTAC representation.
eddic can be compiled with CLang

Future Work

The next version of the EDDI compiler (eddic) will be the version 1.2.0. This version will add support for inheritance at least in a basic way. It will also add support for returning a structure by value. The structures can contains arrays of defined size. This version will also focus on removing the limitations that exists on some features (Function Call Left Values for instance). It will also contains several necessary cleanups to the files.