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.
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.
- 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¶
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.transform.ModulePass¶
Base class of all optimizing passes. Subclass this class to implement your own optimization pass
- class ppci.mem2reg.Mem2RegPromotor¶
Tries to find alloc instructions only used by load and store instructions and replace them with values and phi nodes
- class ppci.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.transform.DeleteUnusedInstructionsPass¶
Remove unused variables from a block
- class ppci.transform.RemoveAddZeroPass¶
Replace additions with zero with the value itself. Replace multiplication by 1 with value itself.
- class ppci.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.
- Canonicalization
- Tree creation
- Instruction selection
- register allocation
- Instruction emission
- 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.
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.
- class ppci.irmach.Frame(name)¶
Activation record abstraction. This class contains a flattened function. Instructions are selected and scheduled at this stage. Frames differ per machine. The only thing left to do for a frame is register allocation.
- class ppci.irmach.AbstractInstruction(cls, ops=(), src=(), dst=(), jumps=(), others=(), ismove=False)¶
Abstract machine instruction class. This is a very simple abstraction of 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