-
Notifications
You must be signed in to change notification settings - Fork 3
/
compilerInfo.txt
228 lines (168 loc) · 12.6 KB
/
compilerInfo.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
Tiger Compiler Reference
________________________
__,,,,_
_ __..-;''`--/'/ /.',-`-.
(`/' ` | \ \ \\ / / / / .-'/`,_
/'`\ \ | \ | \| // // / -.,/_,'-,
/<7' ; \ \ | ; ||/ /| | \/ |`-/,'-.,_,/')
/ _.-, `,-\,__| _-| / \ \/|_/ | '-/.;.\'
`-` f/ ; / __/ \__ `/ |__/ |
`-' | -| =|\_ \ |-' |
__/ /_..-' ` ),' //
((__.-'((___..-'' \__.'
**************************************************************
***************************Overview***************************
**************************************************************
Front-end -> IR -> Back-end
where:
Front-end <-> analysis
- lexical analysis (string -> tokens)
- syntax analysis (tokens -> AST)
- semantic analysis (AST -> IR)
IR <-> independent from source language & machine language
Back-end <-> synthesis
- optimization of IR (IR -> IR)
- instruction selection (IR -> instructions)
- control flow analysis (instructions -> flowgraph)
- liveness (flowgraph -> interferencegraph)
- register allocation
- code emission
**************************************************************
****************************Phases****************************
**************************************************************
Lex & Parse (FRONT-END - ENTREGA 0)
-----------
The lexical analyzer takes a stream of characters (a program) and produces a stream of tokens.
The parse take a stream of tokens corresponding to a program and produces the abstract syntac tree associated with it.
tigerlex.lex Lexer para Tiger
tigergrm.y Parser para Tiger
tigernlin.sml Nro de línea
tigerabs.sml Sintaxis abstracta para Tiger
- FunctionDec es lista de funciones porque contempla el caso de las definiciones recursivas.
- Idem para TypeDec, pues están permitido los tipos recursivos, pero no puede haber ciclos.
- No hay sintaxis abstracta para & y | (se traducen al AST como if then else).
- No hay sintaxis abstracta para el - unario (se traduce como 0 - x).
- Un statement vacío se representa como SeqExp [].
- escape se usará para saber cuáles variables son locales en el caso de anidamiento de funciones o loops.
- El campo escape de field sólo tiene sentido en FunctionDec (en RecordTy es ignorado).
Semantic Analysis - Type Checking (FRONT-END - ENTREGA 1)
---------------------------------
Semantic Analysis connects variable definitions to their uses, checks that each expression has a correct type and translate AST into a simpler representation suitable for generating machine code.
First we will handle type checking. This phase is characterized by the maintenance of two symbol tables or environments, mapping identifiers to their types, locations and other information that will be used later.
tigerseman.sml Semántica de Tiger
- Por ahora, nos ocupamos del tipado.
- Dos entornos, tab_tipos y tab_vars (two separate name spaces):
+ Entorno de tipo: string -> Tipo
+ Entorno de valores (variables + funciones): string -> EnvEntry (ver tigersres)
- transProg toma el AST del programa y lo transforma en {trans.exp, tips.Tipo} (por ahora exp=(), completar sólo tipo).
tigertips.sml Tipos de Tiger
- TNil es un tipo inventado para que la expresión nil sea de cualquier tipo record.
- TUnit es un tipo inventado para las expresiones que no devuelven valor.
tigersres.sml Entorno de valores
- VIntro si es una variable readonly (sólo en for)
- Var si es una variable -> tipo
- Func si es una función -> nivel, label, tipo params formales, tipo rdo, bool externa
tigerescap.sml Cálculo de escapes
- Una variable escapa cuando es accedida desde un marco de activación distinto del que la alocó.
- escEnv es una tabla que para cada variable nos dice cuál es su profundidad y si escapa o no.
tigertab.sml Tablas
tigertopsort.sml Sort topológico
tigerinclude.sml Maneja los includes
Semantic Analysis - Intermediate Representation (FRONT-END - ENTREGA 2)
-----------------------------------------------
An intermediate representation (IR) is a kind of abstract machine language that can express the target-machine operations without committing to too much machine-specific detail, and which is independent from source language.
The tigerframe and tigertemp interfaces provide (to tigertrans) machine-independent views of memory-resident and register-resident variables. The tigertrans module augments this by handling the notion of nested scopes (via static links) and generate the intermediate code.
tigerseman.sml Semántica de Tiger
- Ahora nos ocupamos del código intermedio, completando el campo exp que antes era (). Usamos tigertrans.
tigertree.sml Árboles de código intermedio
- Debe tener componentes individuales que describan solamente cosas extremadamente simples (comparables a assembler).
- Diferenciamos dos tipos:
+ Expresiones - computación de algún valor, posiblemente con efectos laterales:
constantes enteras (CONST)
constantes simbólicas (NAME), se corresponden con labels de assembler.
temporarios (TEMP), se corresponden con registros de una máquina real (la máquina abstracta tiene infinitos temporarios, la real tiene finitos registros)
operaciones binarias básicas aritméticas y lógicas (BINOP)
contenidos en memoria (MEM)
llamada a procedimiento (CALL)
secuencia que produce valor (ESEQ)
+ Sentencias - producen efectos laterales y controlan el flujo:
mover a registro o memoria (MOVE)
evaluar una expresión y descartar el resultado (EXP)
salto - transferir control del lugar actual a una dirección determinada (JUMP)
salto condicional (CJUMP)
secuencia (SEQ)
etiqueta (LABEL)
- Observación: en este lenguaje tree, no hay constructores para definición de procedimientos y funciones (sólo se puede especificar el cuerpo de cada función). Las secuencias de entradas y salidas de procedimientos las vemos después (as special "glue" that is different for each target machine).
tigertrans.sml Generación de código intermedio
- Cómo traducir un AST a código intermedio? Tres casos:
Expresión que computa un valor -> Ex of tigertree.exp (expression)
Expresión que no retorna valor -> Nx of tigertree.stm (no result)
Condicional o salto -> Cx of label * label -> tigertree.stm (conditional)
Ver tipo de datos: tigertrans.exp.
- Todas las variables y l-values en Tiger ocupan una palabra en memoria y entran en un registro :)
tigerframe.sml Marcos de activación
- Tiger no tiene funciones de alto orden => con un stack nos alcanza para las variables locales.
- Tiger tiene funciones anidadas: una función necesita tener acceso no sólo a su FP, sino al de funcs que la llaman.
- Cómo se logra? Usaremos Static Links.
- Las variables que escapan van en el frame, las que no escapan pueden ir en registros.
A variable escapes if it is passed by reference, its address is taken or it is accessed from a nested function.
- En tigerframe.sig tenemos la interfaz para marcos de activación que oculta los detalles de la implementación específica que elijamos después para tigerframe.sml.
tigerescap.sml Cálculo de escapes
- Una variable escapa cuando es accedida desde un marco de activación distinto del que la alocó.
- escEnv es una tabla que para cada variable nos dice cuál es su profundidad y si escapa o no.
tigertemp.sml Temporarios y etiquetas
- temporary -> a value that is temporary held in a register.
- label -> some machine-language location whose exact address is yet to be determined.
- Por ahora, tendremos infinitos temporarios y etiquetas.
Canonicalize (BACK-END - ENTREGA 2)
------------
Rewrite the IR for convenience:
1st: A tree is rewritten into a list of canonical trees without SEQ or ESEQ nodes.
2nd: This list is grouped into a set of basic blocks, which contain no internal jumps or labels.
3rd: The basic blocks are ordered into a set of traces in which every CJUMP is immediately followed by its false label.
tigercanon.sml Canonizador
tigerinterp.sml Intérprete de código intermedio canonizado
Instruction Selection (BACK-END - ENTREGA 3)
---------------------
The IR expresses only one operation in each tree node, but a real machine instruction can often perform several.
The job of the instruction selection phase is to find the appropiate machine instructions for the IR.
We have chosen the architecture i386.
tigerassem.sml Abstract assembly-language instructions
- Each instruction is either an OPER, LABEL or MOVE.
tigercodegen.sml Code generation
- The maximal munch algorithm is used to transform an IR into a list of assembler instructions.
Control Flow & Liveness (BACK-END - ENTREGA 3)
-----------------------
We have used an unbounded number of temporaries, but the real machine has a bounded number of registers. Two temporaries a and b can fit into the same register if a and b are never in use at the same time. If they don't all fit, the excess temporaries can be kept in memory.
A variable is live if it holds a value that may be needed in the future.
To perform liveness analysis on a program it is useful to make a control-flow graph.
The flow analysis for the Tiger compiler is done in two stages:
1st: the control flow of the Assem program is analysed, producing a control-flow graph.
2nd: the liveness of variables in the control-flow graph is analysed, producing an interference graph.
tigergraph.sml Tipo abstracto de datos para grafos dirigidos
tigerflow.sml Grafos de control de flujo
- Transforma una lista de instrucciones assembler en un grafo de flujo.
- En un grafo de flujo (dirigido):
+ node x -> statement x
+ edge xy -> statement x can be followed by statement y
- Se separa la información de los nodos: se usan tablas (uso Splaymap) para def, use e ismove.
tigerliveness.sml Cálculo de liveness y grafo de interferencia
- Para el cálculo de liveness, transforma un grafo de flujo en un grafo de interferencia.
- En un grafo de interferencia (no dirigido):
+ node a -> temporary a
+ edge ab -> a and b cannot be allocated to the same register (a and b interfere)
- Para el cálculo de liveness, implemento el algoritmo de ecuaciones de liveness (iterativo).
- Uso el módulo Splayset para representar los conjuntos.
- Considero el tratamiento especial para MOVE (páginas 221,222).
Register Allocation (BACK-END - ENTREGA 3)
-------------------
We use the interference graph to assign temporaries to registers (coloring).
tigerregalloc.sml Register Allocation
tigercolor.sml Coloring Algorithm
tigerset Abstract Data Type for sets
Other modules:
tigermain.sml Main
tigerutils.sml Utils
tigerpp.sml Pretty printer
tigerpila.sml Pilas
tigerit.sml