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
(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.
- 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.
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