|
273
|
1
|
|
|
2
|
|
314
|
3 .. toctree::
|
|
|
4
|
|
|
5 ir
|
|
|
6
|
|
273
|
7 Compiler
|
|
|
8 ========
|
|
|
9
|
|
|
10 This chapter describes the design of the compiler.
|
|
|
11 The compiler consists a frontend, mid-end and back-end. The frontend deals with
|
|
|
12 source file parsing and semantics checking. The mid-end performs optimizations.
|
|
|
13 This is optional. The back-end generates machine code. The front-end produces
|
|
|
14 intermediate code. This is a simple representation of the source. The back-end
|
|
300
|
15 can accept this kind of representation.
|
|
273
|
16
|
|
|
17 .. graphviz::
|
|
|
18
|
|
|
19 digraph x {
|
|
|
20 rankdir="LR"
|
|
|
21 1 [label="c3 source file"]
|
|
|
22 10 [label="c3 front end" ]
|
|
|
23 11 [label="language X front end" ]
|
|
|
24 20 [label="mid end" ]
|
|
|
25 30 [label="back end for X86" ]
|
|
|
26 31 [label="back end for ARM" ]
|
|
|
27 40 [label="object file"]
|
|
|
28 1 -> 10
|
|
|
29 10 -> 20 [label="IR-code"]
|
|
|
30 11 -> 20 [label="IR-code"]
|
|
|
31 20 -> 30 [label="IR-code"]
|
|
|
32 20 -> 31 [label="IR-code"]
|
|
|
33 30 -> 40
|
|
|
34 }
|
|
|
35
|
|
299
|
36
|
|
273
|
37 IR-code
|
|
|
38 -------
|
|
300
|
39
|
|
299
|
40 The intermediate representation (IR) of a program de-couples the front end
|
|
|
41 from the backend of the compiler.
|
|
273
|
42
|
|
310
|
43 See :doc:`ir` for details about all the available instructions.
|
|
273
|
44
|
|
|
45
|
|
274
|
46 C3 Front-end
|
|
|
47 ------------
|
|
273
|
48
|
|
|
49 For the front-end a recursive descent parser is created for the c3 language.
|
|
|
50 This is a subset of the C language with some additional features.
|
|
|
51
|
|
274
|
52 .. graphviz::
|
|
|
53
|
|
|
54 digraph c3 {
|
|
300
|
55 rankdir="LR"
|
|
274
|
56 1 [label="source text"]
|
|
|
57 10 [label="lexer" ]
|
|
|
58 20 [label="parser" ]
|
|
|
59 40 [label="code generation"]
|
|
|
60 99 [label="IR-code object"]
|
|
299
|
61 1 -> 10
|
|
|
62 10 -> 20
|
|
310
|
63 20 -> 40
|
|
274
|
64 40 -> 99
|
|
|
65 }
|
|
|
66
|
|
305
|
67 .. autoclass:: ppci.c3.Lexer
|
|
|
68
|
|
301
|
69 .. autoclass:: ppci.c3.Parser
|
|
273
|
70
|
|
301
|
71 .. autoclass:: ppci.c3.CodeGenerator
|
|
273
|
72
|
|
306
|
73 .. autoclass:: ppci.c3.Builder
|
|
|
74
|
|
273
|
75 Back-end
|
|
|
76 --------
|
|
|
77
|
|
|
78 The back-end is more complicated. There are several steps to be taken here.
|
|
|
79
|
|
357
|
80 1. Canonicalization
|
|
|
81 2. Tree creation
|
|
|
82 3. Instruction selection
|
|
|
83 4. register allocation
|
|
|
84 5. Instruction emission
|
|
|
85 6. TODO: Peep hole optimization?
|
|
273
|
86
|
|
306
|
87 .. automodule:: ppci.codegen
|
|
273
|
88 :members:
|
|
|
89
|
|
357
|
90 Canonicalize
|
|
|
91 ~~~~~~~~~~~~
|
|
|
92
|
|
|
93 During this phase, the IR-code is made simpler. Function calls are pulled pulled
|
|
|
94 to top level and the frame pointer is introduced.
|
|
|
95
|
|
|
96 Tree building
|
|
|
97 ~~~~~~~~~~~~~
|
|
|
98
|
|
|
99 From IR-code a tree is generated which can be used to select instructions.
|
|
|
100
|
|
274
|
101 Instruction selection
|
|
|
102 ~~~~~~~~~~~~~~~~~~~~~
|
|
|
103
|
|
|
104 The instruction selection phase takes care of scheduling and instruction
|
|
|
105 selection. The output of this phase is a one frame per function with a flat
|
|
|
106 list of abstract machine instructions.
|
|
|
107
|
|
304
|
108 // .. autoclass:: ppci.irmach.Frame
|
|
274
|
109
|
|
304
|
110 // .. autoclass:: ppci.irmach.AbstractInstruction
|
|
274
|
111
|
|
366
|
112 To select instruction, a tree rewrite system is used. This is also called
|
|
|
113 bottom up rewrite generator (BURG). See pyburg.
|
|
|
114
|
|
274
|
115
|
|
357
|
116 Register allocation
|
|
|
117 ~~~~~~~~~~~~~~~~~~~
|
|
|
118
|
|
|
119 The selected instructions are used to select correct registers.
|
|
|
120
|
|
|
121
|
|
366
|
122 code emission
|
|
|
123 ~~~~~~~~~~~~~
|
|
|
124
|
|
|
125 Code is emitted using the outputstream class. The assembler and compiler use
|
|
|
126 this class to emit instructions to. The stream can output to object file
|
|
|
127 or to a logger.
|
|
|
128
|
|
|
129 .. autoclass:: ppci.outstream.OutputStream
|
|
|
130
|
