Register Coalescing

I added a Register Allocator to my compiler for optimizing code:

The coalescing happens in a loop making changes to the interference graph directly which are not good,

and complete interference graph reconstruction on the outer loop which happens less frequently but which is the best.

Using this map we can look at the right and middle columns in the next image to see which operands are coalesced.

On the right is the original instructions in the middle is register coalescing which removes several instructions, and on the left is the rest of the register allocator with graph coloring.

Graph Coloring:

After coalescing graph coloring happens, at this stage some nodes are removed by coalescing. So it is faster:

Finally you can look at the graph coloring on the left column:

If you want to look into the code:

Register Allocation Code

Copy Propagation

I made an Optimizing Compiler for C. It has multiple passes for generating assembly code x86 architecture.

It is an Ahead of time Compiler.

I made the Intermediate Representation where optimizations are made. I convert the AST into Intermediate Representation then apply optimizations to the code.

This is an example of copy propagation:

I have a map of instructions and reaching copies:

The reaching copies analysis annotates each instructions with its reaching copy if any.

The replacement is made after the map is made.

The call has the same arguments and the copy propagation pass knows about it, so it replaces arguments repectively.

If you want to look at the code:

optimizations code

Dynamic Memory Allocation

I made a Linux C Compiler. It is a software compiler, it compiles C code into GAS assembly language.

I followed ISO C17 standard to make the compiler following the rules of the standard.

I also followed system V ABI calling conventions. You can call other libraries compiled with other compilers and call them in your code.

I also followed Intel x64 ISA for writing assembly code.

It has dynamic memory allocation. You can use malloc, free, calloc, realloc in your programs and the compiler will handle void pointers and void types.

The compiler supports static memory allocation, automatic memory allocation and dynamic memory allocation.

I tested my compiler against C tests for making sure it works, the testing is incremental so it works with past tests as well.

If you want to look at the code:

Compiler Code

Testing my compiler against Test Suite of compiling C tests

I added Multidimensional Arrays in C and Pointers to my Compiler. I added Subscripting, pointer arithmetic, Derefencing and Addressing, Compound Initializers and Static Arrays.

I tested the Compiler against C tests for validating correct assembly code.

The tests run from the beginning to the end, so every feature is tested and validated.

This is one of the tests of the compiler, pointer difference validation:

This is the final assembly language file, it is real x86 code and when it runs it produces correct results.

If you want to look at the code:

Compiler Code

Code Generation of Floating point numbers

I made a Code Generator, The code generator supports floating point numbers. 

I used SSE2 instructions for generating assembly code for instructions that use doubles.

It translates from the Intermediate Representation into assembly for x86 architectures.

I also kept System V Calling conventions. In this way I can call functions from the math.h library and they work.

The code generator supports type conversions between floating point numbers and integers.

If you want to look at the code:

Compiler Code

Type System Part 2

I made a Type System for C in Python. It has unsigned integers and signed integers (longs and ints).

It has a symbol table that is generated at type checking pass and it has a constant propagation system. The static type checker looks for and annotates all the types in expressions. Checks for errors.

In assembly all the types are converted to assembly types for x86, and instructions are selected for each type.

If you want to look at the code:

Compiler Code  

Type System

I added a Type System to my C Compiler. It has support for adding multiple types to the compiler and make static type checking.

I added support for long integer types. 

Type conversions between longs and ints, It converts implicit casts into explicit casts.

It annotates each expression with its corresponding return type and uses it to know the corresponding intermediate representation.

In the back end I added support for multiple operand sizes.

If you want to look at the code:

Compiler Code