-
Notifications
You must be signed in to change notification settings - Fork 1
/
gocode.py
412 lines (342 loc) · 12.8 KB
/
gocode.py
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
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
# coding: utf-8
'''
Proyecto 4 - Parte 1
====================
La generación de código para MiniGo. En este proyecto, se va a convertir
el AST en código de maquina intermedio conocido como Asignación estática
única (SSA - Single Static Assignment).
Hay algunas partes importantes que usted necesita hacer para este
trabajo. Por favor, lea cuidadosamente antes de empezar:
Asignación Estática ünica
=========================
El primer problema es como descomponer expresiones complejas en algo que
se pueda manejar mas simplemente. Una forma de hacer esto es descomponer
todas las expresiones en una secuencia de asignaciones sencillas que
involucre operaciones binarias o unarias.
Como un ejemplo, supongase que se tiene una expresión matemática igual a
esto:
2 + 3*4 - 5
Esto es una manera posible de descomponer la expresión en operaciones
simples:
int_1 = 2
int_2 = 3
int_3 = 4
int_4 = int_2 * int_3
int_5 = int_1 + int_4
int_6 = 5
int_7 = int_5 - int_6
En este código, las variables int_n son simplemente temporales
utilizadas en el ejercicio del cálculo. Una característica crítica de
SSA es que tales varibles temporales son solamente asignadas una sola
vez (asignación única) y nunca reutilizadas. Por lo tanto, si se fuera
a evaluar otra expresión, sólo tendría que seguir incrementando los
números. Por ejemplo, si se evaluara 10+20+30, se tendría código como
este:
int_8 = 10
int_9 = 20
int_10 = int_8 + int_9
int_11 = 30
int_12 = int_11 + int_11
SSA tiene la intensión de imitar las instrucciones de bajo-nivel que se
podría llevar a cabo en una CPU. Por ejemplo, las instrucciones
anteriores pueden ser traducidas a instrucciones de máquina de
bajo-nivel (para una CPU hipotética) de esta manera:
MOVI #2, R1
MOVI #3, R2
MOVI #4, R3
MUL R2, R3, R4
ADD R4, R1, R5
MOVI #5, R6
SUB R5, R6, R7
Otro beneficio de SSA es que es muy fácil de codificar y manipular
usando estrusturas de datos simples como tuplas. Por ejemplo, se podría
codifica la secuencia anterior de operaciones como una lista como esto:
[
('movi', 2, 'int_1'),
('movi', 3, 'int_2'),
('movi', 4, 'int_3'),
('mul', 'int_2', 'int_3', 'int_4'),
('add', 'int_1', 'int_4', 'int_5'),
('movi', 5, 'int_6'),
('sub', 'int_5','int_6','int_7'),
]
Tratando con Variables
======================
En su programa, probablemente va a tener algunas variables que usará y
le asignará diferentes valores. Por ejemplo:
a = 10 + 20;
b = 2 * a;
a = a + 1;
En "SSA puro", todas las variables en realidad serán versionadas como
las temporales en las anteriores expresiones. Por ejemplo, tendía que
emitir código como este:
int_1 = 10
int_2 = 20
a_1 = int_1 + int_2
int_3 = 2
b_1 = int_3 * a_1
int_4 = 1
a_2 = a_1 + int_4
...
Por razones que tendrá sentido más adelante, vamos a tratar las
variables declaradas como localizaciones de memoria y acceder a ellas
usando las instrucciones load/store. Por ejemplo:
int_1 = 10
int_2 = 20
int_3 = int_1 + int_2
store(int_3, "a")
int_4 = 2
int_5 = load("a")
int_6 = int_4 * int_5
store(int_6,"b")
int_7 = load("a")
int_8 = 1
int_9 = int_7 + int_8
store(int_9, "a")
Una Palabra a cerca de Tipos
============================
A bajo nivel, las CPUs solamente pueden operar con unos pocos tipos
de datos tales como ints y floats. Debido a que la semántica de los
tipos de bajo-nivel pueden variar un poco, se tendrá que tomar algunas
medidas para manejarlos por separado.
En nuestro código intermedio, simplemente se etiquetará los nombres
de variables temporales y las instrucciones con un tipo asociado de
bajo-nivel. Por ejemplo:
2 + 3*4 (ints)
2.0 + 3.0*4.0 (floats)
El código intermedio generado podría lucir como esto:
('literal_int', 2, 'int_1')
('literal_int', 3, 'int_2')
('literal_int', 4, 'int_3')
('mul_int', 'int_2', 'int_3', 'int_4')
('add_int', 'int_1', 'int_4', 'int_5')
('literal_float', 2.0, 'float_1')
('literal_float', 3.0, 'float_2')
('literal_float', 4.0, 'float_3')
('mul_float', 'float_2', 'float_3', 'float_4')
('add_float', 'float_1', 'float_4', 'float_5')
Nota: Estos tipos pueden o no corresponder directamente a los nombres
de tipos usados en el programa de entrada. Por ejemplo, durante la
traducción, las estructuras de datos de nivel superior se reducirán
a unas operaciones de bajo-nivel.
Su Tarea
========
Su tarea es la siguiente: Escriba una clase Visitor() de AST que tome
un programa MiniGo y lo aplane a una secuencia única de instrucciones
de código SSA representado como tuplas de la forma
(operacion, operandos, ..., destinacion)
Para empezar, su código SSA sólo debe contener las siguientes
operaciones:
('alloc_type',varname) # Allocate a variable of a given type
('literal_type', value, target) # Load a literal value into target
('load_type', varname, target) # Load the value of a variable into target
('store_type',source, varname) # Store the value of source into varname
('add_type', left, right, target ) # target = left + right
('sub_type',left,right,target) # target = left - right
('mul_type',left,right,target) # target = left * right
('div_type',left,right,target) # target = left / right (integer truncation)
('uadd_type',source,target) # target = +source
('uneg_type',source,target) # target = -source
('print_type',source) # Print value of source
'''
import goast#from goast import * # se cambió a mgoast
#import mgoblock
from collections import defaultdict
# PASO 1: Mapee los nombres de los operadores símbolos tales
# como +, -, *, / a los nombres actuales de opcode 'add', 'sub',
# 'mul', 'div' a ser emitidos en el código SSA. Esto es fácil de hacer
# usando diccionarios:
binary_ops = {
'+' : 'add',
'-' : 'sub',
'*' : 'mul',
'/' : 'div',
}
unary_ops = {
'+' : 'uadd',
'-' : 'usub'
}
# paso 2: Implemente la siguiente clase Node Visitor para que cree una
# secuencia de instrucciones SSA en forma de tuplas. Utilice la
# descripción anterior de los op-codes permitidos como una guía.
class GenerateCode(goast.NodeVisitor): # se cambia goast.NodeVisitor por NodeVisitor
'''
Clase Node visitor que crea secuencia de instrucciones codificadas
3-direcciones.
'''
def __init__(self):
super(GenerateCode, self).__init__()
# diccionario de versiones para temporales
self.versions = defaultdict(int)
# El código generado (lista de tuplas)
self.code = []
# Una lista de declaraciones externas (y tipos)
self.externs = []
def new_temp(self, typeobj):
'''
Crea una variable temporal del tipo dado
'''
name = "%s_%d" % (typeobj.name, self.versions[typeobj.name])
self.versions[typeobj.name] += 1
return name
# Debe implementar métodos visit_Nodename para todos los otros
# nodos AST. En su código, tendrá que crear las instrucciones
# y agregarlas a la lista self.code.
# Siguen algunos métodos de muestra. Deberá de ajustarlos dependiendo
# de los nombres de los nodos AST que haya definido.
def visit_Literal(self, node):
# Crea un nuevo nombre de variable temporal
target = self.new_temp(node.type)
# Cree opcode SSA y agregelo a lista de instrucciones generadas
inst = ('literal_'+node.type.name, node.value, target)
self.code.append(inst)
# Grabe nombre de variable temporal donde el valor fue colocado
node.gen_location = target
def visit_BinaryOp(self, node):
# Visite las expresiones izquierda y derecha
self.visit(node.left)
self.visit(node.right)
# Cree una nueva temporal para guardar el resultado
target = self.new_temp(node.type)
# Cree el opcode y agregelo a la lista
opcode = binary_ops[node.op] + "_" + node.left.type.name
inst = (opcode, node.left.gen_location, node.right.gen_location, target)
self.code.append(inst)
# Almacene la localización del resultado en el node
node.gen_location = target
def visit_PrintStatement(self, node):
# Visite la expresión impresa
self.visit(node.expr)
# Cree el opcode y agregelo a la lista
inst = ('print_'+node.expr.type.name, node.expr.gen_location)
self.code.append(inst)
def visit_Program(self,node):
self.visit(node.program)
#def visit_Statements(self,node):
# self.visit(node.expr)
# inst = ('print_'+node.expr.type.name, node.expr.gen_location)
# self.code.append(inst)
#def visit_Statement(self,node):
# self.visit(node.expr)
# inst = ('print_'+node.expr.type.name, node.expr.gen_location)
# self.code.append(inst)
def visit_ConstDeclaration(self,node):
# localice en memoria
inst = ('alloc_'+node.type.name, node.id)
self.code.append(inst)
# almacene el val inicial
self.visit(node.value)
inst = ('store_'+node.type.name,
node.value.gen_location, node.id)
self.code.append(inst)
def visit_VarDeclaration(self,node):
# localice en memoria
inst = ('alloc_'+node.type.name, node.id)
self.code.append(inst)
# almacene pot. val inicial
if node.value:
self.visit(node.value)
inst = ('store_'+node.type.name, node.value.gen_location, node.id)
self.code.append(inst)
def visit_LoadLocation(self,node):
target = self.new_temp(node.type)
inst = ('load_'+node.type.name, node.name.id, target)
self.code.append(inst)
node.gen_location = target
#def visit_Extern(self,node):
# self.visit(node.expr)
# inst = ('print_'+node.expr.type.name, node.expr.gen_location)
# self.code.append(inst)
#def visit_FuncPrototype(self,node):
# self.visit(node.expr)
# inst = ('print_'+node.expr.type.name, node.expr.gen_location)
# self.code.append(inst)
#def visit_Parameters(self,node):
# self.visit(node.expr)
# inst = ('print_'+node.expr.type.name, node.expr.gen_location)
# self.code.append(inst)
# node.gen_location = target
#def visit_ParamDecl(self,node):
# self.visit(node.expr)
# inst = ('print_'+node.expr.type.name, node.expr.gen_location)
# self.code.append(inst)
def visit_AssignmentStatement(self,node):
self.visit(node.value)
inst = ('store_'+node.value.type.name, node.value.gen_location, node.location.id)
self.code.append(inst)
def visit_UnaryOp(self,node):
self.visit(node.left)
target = self.new_temp(node.type)
opcode = unary_ops[node.op] + "_" + node.left.type.name
inst = (opcode,node.left.gen_location,target) # se agregó target como tercer argumento
self.code.append(inst)
node.gen_location = target
# se implementó el nodo if
def visit_IfStatement(self,node):
self.visit(node.condition)
self.visit(node.then_b)
if node.else_b:
self.visit(node.else_b)
# se habilitó nodo visit_Group, anexó y modificó algunas instrucciones
def visit_Group(self,node):
self.visit(node.expression)
# inst = ('print_'+node.expression.type.name, node.expression.gen_location)
# self.code.append(inst)
node.gen_location = node.expression.gen_location
# se habilitó nodo visit_FunCall, anexó y modificó algunas instrucciones
def visit_FunCall(self,node):
self.visit(node.params)
if node.type:
target = self.new_temp(node.type)
inst = ('function_call_'+node.type.name, target)
#inst = ('print_'+node.type.name, target)
self.code.append(inst)
node.gen_location = target
# se habilitó nodo visit_ExprList, anexó y modificó algunas instrucciones
def visit_ExprList(self,node):
for expr in node.expressions:
if not isinstance(expr,goast.Empty):
self.visit(expr)
# inst = ('print_'+expr.type.name, expr.gen_location)
# self.code.append(inst)
# PASO 3: Pruebas
#
# Trate de correr este programa con el archivo de entrada
# Project4/Tests/good.g y vea el resultado de la secuencia de
# código SSA.
#
# bash % python mgocode.py good.g
# ... mire la salida ...
#
#
# Salidas de ejemplo pueden encontrarse en Project4/Tests/good.out.
# Mientras esté codificando, podrá desear romper el código en partes
# mas manejables. Piense en pruebas unitarias.
# ---------------------------------------------------------------------
# NO MODIFIQUE NADA DE LO DE ABAJO
# ---------------------------------------------------------------------
def generate_code(node):
'''
Genera código SSA desde el nodo AST suministrados
'''
gen = GenerateCode()
gen.visit(node)
return gen
if __name__ == '__main__':
import golex
import goparser
import gocheck
import sys
from errors import subscribe_errors, errors_reported
lexer = golex.make_lexer()
parser = goparser.make_parser()
with subscribe_errors(lambda msg: sys.stdout.write(msg+"\n")):
program = parser.parse(open(sys.argv[1]).read())
# Comprueba el programa
gocheck.check_program(program)
# Si no se han producido errores, genere código
if not errors_reported():
code = generate_code(program)
# Emitir la secuencia de código
for inst in code.code:
print(inst)