Compiler design

Compiler design

This chapter describes the design of the compiler. The compiler consists a frontend, mid-end and back-end. The frontend deals with source file parsing and semantics checking. The mid-end performs optimizations. This is optional. The back-end generates machine code. The front-end produces intermediate code. This is a simple representation of the source. The back-end can accept this kind of representation.

digraph x {
rankdir="LR"
1 [label="c3 source file"]
10 [label="c3 front end" ]
11 [label="language X front end" ]
20 [label="mid end" ]
30 [label="back end for X86" ]
31 [label="back end for ARM" ]
40 [label="object file"]
1 -> 10
10 -> 20 [label="IR-code"]
11 -> 20 [label="IR-code"]
20 -> 30 [label="IR-code"]
20 -> 31 [label="IR-code"]
30 -> 40
}

C3 Front-end

For the front-end a recursive descent parser is created for the c3 language. This is a subset of the C language with some additional features.

digraph c3 {
rankdir="LR"
1 [label="source text"]
10 [label="lexer" ]
20 [label="parser" ]
40 [label="code generation"]
99 [label="IR-code object"]
1 -> 10
10 -> 20
20 -> 40
40 -> 99
}

class ppci.c3.Lexer(diag)

Generates a sequence of token from an input stream

class ppci.c3.Parser(diag)

Parses sourcecode into an abstract syntax tree (AST)

class ppci.c3.CodeGenerator(diag)

Generates intermediate (IR) code from a package. The entry function is ‘genModule’. The main task of this part is to rewrite complex control structures, such as while and for loops into simple conditional jump statements. Also complex conditional statements are simplified. Such as ‘and’ and ‘or’ statements are rewritten in conditional jumps. And structured datatypes are rewritten.

Type checking is done in one run with code generation.

class ppci.c3.Builder(diag, target)

Generates IR-code from c3 source. Reports errors to the diagnostics system.

Brainfuck frontend

The compiler has a front-end for the brainfuck language.

class ppci.bf.BrainFuckGenerator(target)

Brainfuck is a language that is so simple, the entire front-end can be implemented in one pass.

IR-code

The intermediate representation (IR) of a program de-couples the front end from the backend of the compiler.

See IR-code for details about all the available instructions.

Optimalization

The IR-code generated by the front-end can be optimized in many ways. The compiler does not have the best way to optimize code, but instead has a bag of tricks it can use.

class ppci.opt.transform.ModulePass

Base class of all optimizing passes. Subclass this class to implement your own optimization pass

class ppci.opt.mem2reg.Mem2RegPromotor

Tries to find alloc instructions only used by load and store instructions and replace them with values and phi nodes

class ppci.opt.transform.LoadAfterStorePass

Remove load after store to the same location.

[x] = a
b = [x]
c = b + 2

transforms into:

[x] = a
c = a + 2
class ppci.opt.transform.DeleteUnusedInstructionsPass

Remove unused variables from a block

class ppci.opt.transform.RemoveAddZeroPass

Replace additions with zero with the value itself. Replace multiplication by 1 with value itself.

class ppci.opt.transform.CommonSubexpressionEliminationPass

Replace common sub expressions with the previously defined one.

Back-end

The back-end is more complicated. There are several steps to be taken here.

  1. Canonicalization
  2. Tree creation
  3. Instruction selection
  4. register allocation
  5. Instruction emission
  6. TODO: Peep hole optimization?

Code generator

Target independent code generator part. The target is provided when the generator is created.

Canonicalize

During this phase, the IR-code is made simpler. Also unsupported operations are rewritten into function calls. For example soft floating point is introduced here.

Tree building

From IR-code a tree is generated which can be used to select instructions.

The process of instruction selection is preceeded by the creation of a selection dag (directed acyclic graph). The dagger take ir-code as input and produces such a dag for instruction selection.

A DAG represents the logic (computation) of a single basic block.

Instruction selection

The instruction selection phase takes care of scheduling and instruction selection. The output of this phase is a one frame per function with a flat list of abstract machine instructions.

To select instruction, a tree rewrite system is used. This is also called bottom up rewrite generator (BURG). See pyburg.

Register allocation

The selected instructions are used to select correct registers.

class ppci.codegen.registerallocator.RegisterAllocator

Target independent register allocator.

Algorithm is iterated register coalescing by Appel and George.

Chaitin’s algorithm: remove all nodes with less than K neighbours. These nodes can be colored when added back.

The process consists of the following steps:

  • build interference graph from the instruction list
  • remove low degree non move related nodes.
  • (optional) coalesc registers to remove redundant moves
  • (optional) spill registers
  • select registers

TODO: Implement different register classes

code emission

Code is emitted using the outputstream class. The assembler and compiler use this class to emit instructions to. The stream can output to object file or to a logger.

class ppci.binutils.outstream.OutputStream

Interface to generator code with.