|
277
|
1 """
|
|
|
2 Intermediate representation (IR) code classes.
|
|
|
3 """
|
|
|
4
|
|
|
5
|
|
|
6 def dumpgv(m, outf):
|
|
|
7 print('digraph G ', file=outf)
|
|
|
8 print('{', file=outf)
|
|
|
9 for f in m.Functions:
|
|
|
10 print('{} [label="{}" shape=box3d]'.format(id(f), f),file=outf)
|
|
|
11 for bb in f.Blocks:
|
|
|
12 contents = str(bb) + '\n'
|
|
|
13 contents += '\n'.join([str(i) for i in bb.Instructions])
|
|
|
14 outf.write('{0} [shape=note label="{1}"];\n'.format(id(bb), contents))
|
|
|
15 for successor in bb.Successors:
|
|
|
16 print('"{}" -> "{}"\n'.format(id(bb), id(successor)), file=outf)
|
|
|
17
|
|
|
18 outf.write('"{}" -> "{}" [label="entry"]\n'.format(id(f), id(f.entry)))
|
|
|
19 print('}', file=outf)
|
|
|
20
|
|
|
21
|
|
|
22 class Module:
|
|
|
23 """ Main container of variables and functions. """
|
|
|
24 def __init__(self, name):
|
|
|
25 self.name = name
|
|
|
26 self.funcs = []
|
|
|
27 self.variables = []
|
|
|
28
|
|
|
29 def __repr__(self):
|
|
|
30 return 'IR-module [{0}]'.format(self.name)
|
|
|
31
|
|
|
32 def addFunc(self, f):
|
|
|
33 self.funcs.append(f)
|
|
|
34
|
|
|
35 addFunction = addFunc
|
|
|
36
|
|
|
37 def addVariable(self, v):
|
|
|
38 self.variables.append(v)
|
|
|
39
|
|
|
40 def getVariables(self):
|
|
|
41 return self.variables
|
|
|
42
|
|
|
43 Variables = property(getVariables)
|
|
|
44
|
|
|
45 def getFunctions(self):
|
|
|
46 return self.funcs
|
|
|
47
|
|
|
48 Functions = property(getFunctions)
|
|
|
49
|
|
|
50 def findFunction(self, name):
|
|
|
51 for f in self.funcs:
|
|
|
52 if f.name == name:
|
|
|
53 return f
|
|
|
54 raise KeyError(name)
|
|
|
55
|
|
|
56 getFunction = findFunction
|
|
|
57
|
|
|
58 def dump(self, indent=' '):
|
|
|
59 print(self)
|
|
|
60 for v in self.Variables:
|
|
|
61 print(indent, v)
|
|
|
62 for fn in self.Functions:
|
|
|
63 fn.dump(indent=indent+' ')
|
|
|
64
|
|
|
65 # Analysis functions:
|
|
|
66 def check(self):
|
|
|
67 """ Perform sanity check on module """
|
|
|
68 for f in self.Functions:
|
|
|
69 f.check()
|
|
|
70
|
|
|
71
|
|
|
72 class Function:
|
|
|
73 """
|
|
|
74 Function definition. Contains an entry block.
|
|
|
75 """
|
|
|
76 def __init__(self, name):
|
|
|
77 self.name = name
|
|
|
78 self.entry = Block('{}_entry'.format(name))
|
|
|
79 self.epiloog = Block('{}_epilog'.format(name))
|
|
|
80 self.epiloog.addInstruction(Terminator())
|
|
|
81 self.return_value = Temp('{}_retval'.format(name))
|
|
|
82 self.arguments = []
|
|
|
83 self.localvars = []
|
|
|
84
|
|
|
85 def __repr__(self):
|
|
|
86 args = ','.join(str(a) for a in self.arguments)
|
|
|
87 return 'Function {}({})'.format(self.name, args)
|
|
|
88
|
|
|
89 def addBB(self, bb):
|
|
|
90 self.bbs.append(bb)
|
|
|
91 bb.parent = self
|
|
|
92 addBlock = addBB
|
|
|
93
|
|
|
94 def removeBasicBlock(self, bb):
|
|
|
95 self.bbs.remove(bb)
|
|
|
96 bb.parent = None
|
|
|
97
|
|
|
98 def getBBs(self):
|
|
|
99 bbs = [self.entry]
|
|
|
100 worklist = [self.entry]
|
|
|
101 while worklist:
|
|
|
102 b = worklist.pop()
|
|
|
103 for sb in b.Successors:
|
|
|
104 if sb not in bbs:
|
|
|
105 bbs.append(sb)
|
|
|
106 worklist.append(sb)
|
|
|
107 bbs.remove(self.entry)
|
|
|
108 if self.epiloog in bbs:
|
|
|
109 bbs.remove(self.epiloog)
|
|
|
110 bbs.insert(0, self.entry)
|
|
|
111 bbs.append(self.epiloog)
|
|
|
112 return bbs
|
|
|
113
|
|
|
114 def findBasicBlock(self, name):
|
|
|
115 for bb in self.bbs:
|
|
|
116 if bb.name == name:
|
|
|
117 return bb
|
|
|
118 raise KeyError(name)
|
|
|
119
|
|
|
120 Blocks = property(getBBs)
|
|
|
121
|
|
|
122 @property
|
|
|
123 def Entry(self):
|
|
|
124 return self.entry
|
|
|
125
|
|
|
126 def check(self):
|
|
|
127 for b in self.Blocks:
|
|
|
128 b.check()
|
|
|
129
|
|
|
130 def addParameter(self, p):
|
|
|
131 assert type(p) is Parameter
|
|
|
132 p.num = len(self.arguments)
|
|
|
133 self.arguments.append(p)
|
|
|
134
|
|
|
135 def addLocal(self, l):
|
|
|
136 assert type(l) is LocalVariable
|
|
|
137 self.localvars.append(l)
|
|
|
138
|
|
|
139 def dump(self, indent=''):
|
|
|
140 print(indent+str(self))
|
|
|
141 for bb in self.Blocks:
|
|
|
142 print(indent+' '+str(bb))
|
|
|
143 for ins in bb.Instructions:
|
|
|
144 print(indent +' '*2 + str(ins))
|
|
|
145
|
|
|
146
|
|
|
147 class Block:
|
|
|
148 """
|
|
|
149 Uninterrupted sequence of instructions with a label at the start.
|
|
|
150 """
|
|
|
151 def __init__(self, name):
|
|
|
152 self.name = name
|
|
|
153 self.instructions = []
|
|
|
154
|
|
|
155 def __repr__(self):
|
|
|
156 return 'Block {0}'.format(self.name)
|
|
|
157
|
|
|
158 def addInstruction(self, i):
|
|
|
159 i.parent = self
|
|
|
160 assert not isinstance(self.LastInstruction, LastStatement)
|
|
|
161 self.instructions.append(i)
|
|
|
162
|
|
|
163 def replaceInstruction(self, i1, i2):
|
|
|
164 idx = self.instructions.index(i1)
|
|
|
165 i1.parent = None
|
|
|
166 i1.delete()
|
|
|
167 i2.parent = self
|
|
|
168 self.instructions[idx] = i2
|
|
|
169
|
|
|
170 def removeInstruction(self, i):
|
|
|
171 i.parent = None
|
|
|
172 i.delete()
|
|
|
173 self.instructions.remove(i)
|
|
|
174
|
|
|
175 def getInstructions(self):
|
|
|
176 return self.instructions
|
|
|
177 Instructions = property(getInstructions)
|
|
|
178
|
|
|
179 def getLastIns(self):
|
|
|
180 if not self.Empty:
|
|
|
181 return self.instructions[-1]
|
|
|
182 LastInstruction = property(getLastIns)
|
|
|
183
|
|
|
184 @property
|
|
|
185 def Empty(self):
|
|
|
186 return len(self.instructions) == 0
|
|
|
187
|
|
|
188 @property
|
|
|
189 def FirstInstruction(self):
|
|
|
190 return self.instructions[0]
|
|
|
191
|
|
|
192 def getSuccessors(self):
|
|
|
193 if not self.Empty:
|
|
|
194 return self.LastInstruction.Targets
|
|
|
195 return []
|
|
|
196 Successors = property(getSuccessors)
|
|
|
197
|
|
|
198 def getPredecessors(self):
|
|
|
199 preds = []
|
|
|
200 for bb in self.parent.BasicBlocks:
|
|
|
201 if self in bb.Successors:
|
|
|
202 preds.append(bb)
|
|
|
203 return preds
|
|
|
204 Predecessors = property(getPredecessors)
|
|
|
205
|
|
|
206 def precedes(self, other):
|
|
|
207 raise NotImplementedError()
|
|
|
208
|
|
|
209 def check(self):
|
|
|
210 assert isinstance(self.LastInstruction, LastStatement)
|
|
|
211 for i in self.instructions[:-1]:
|
|
|
212 assert not isinstance(i, LastStatement)
|
|
|
213
|
|
|
214
|
|
|
215 # Instructions:
|
|
|
216 class Term:
|
|
|
217 def __init__(self, x):
|
|
|
218 self.x = x
|
|
|
219
|
|
|
220 def match_tree(tree, pattern):
|
|
|
221 if type(pattern) is Term:
|
|
|
222 return True, {pattern: tree}
|
|
|
223 elif type(pattern) is Binop and type(tree) is Binop and tree.operation == pattern.operation:
|
|
|
224 res_a, mp_a = match_tree(tree.a, pattern.a)
|
|
|
225 res_b, mp_b = match_tree(tree.b, pattern.b)
|
|
|
226 assert not (mp_a.keys() & mp_b.keys())
|
|
|
227 mp_a.update(mp_b)
|
|
|
228 return res_a and res_b, mp_a
|
|
|
229 elif type(pattern) is Const and type(tree) is Const and pattern.value == tree.value:
|
|
|
230 return True, {}
|
|
|
231 else:
|
|
|
232 return False, {}
|
|
|
233
|
|
|
234
|
|
|
235 class Expression:
|
|
|
236 pass
|
|
|
237
|
|
|
238
|
|
|
239 class Const(Expression):
|
|
|
240 def __init__(self, value):
|
|
|
241 self.value = value
|
|
|
242
|
|
|
243 def __repr__(self):
|
|
|
244 return 'Const {}'.format(self.value)
|
|
|
245
|
|
|
246
|
|
|
247 # Function calling:
|
|
|
248 class Call(Expression):
|
|
|
249 def __init__(self, f, arguments):
|
|
|
250 self.f = f
|
|
|
251 assert type(f) is Function
|
|
|
252 self.arguments = arguments
|
|
|
253
|
|
|
254 def __repr__(self):
|
|
|
255 args = ', '.join([str(arg) for arg in self.arguments])
|
|
|
256 return '{}({})'.format(self.f.name, args)
|
|
|
257
|
|
|
258
|
|
|
259 # Data operations
|
|
|
260 class Binop(Expression):
|
|
|
261 ops = ['+', '-', '*', '/', '|', '&', '<<', '>>']
|
|
|
262 def __init__(self, value1, operation, value2):
|
|
|
263 assert operation in Binop.ops
|
|
|
264 self.a = value1
|
|
|
265 self.b = value2
|
|
|
266 self.operation = operation
|
|
|
267
|
|
|
268 def __repr__(self):
|
|
|
269 a, b = self.a, self.b
|
|
|
270 return '({} {} {})'.format(a, self.operation, b)
|
|
|
271
|
|
|
272
|
|
|
273 def Add(a, b):
|
|
|
274 """ Convenience call """
|
|
|
275 return Binop(a, '+', b)
|
|
|
276
|
|
279
|
277 def Sub(a, b):
|
|
|
278 return Binop(a, '-', b)
|
|
|
279
|
|
|
280 def Mul(a, b):
|
|
|
281 return Binop(a, '*', b)
|
|
|
282
|
|
|
283 def Div(a, b):
|
|
|
284 return Binop(a, '/', b)
|
|
277
|
285
|
|
|
286 class Eseq(Expression):
|
|
|
287 """ Sequence of instructions where the last is an expression """
|
|
|
288 def __init__(self, stmt, e):
|
|
|
289 self.stmt = stmt
|
|
|
290 self.e = e
|
|
|
291
|
|
|
292 def __repr__(self):
|
|
|
293 return '({}, {})'.format(self.stmt, self.e)
|
|
|
294
|
|
|
295
|
|
|
296 class Alloc(Expression):
|
|
|
297 """ Allocates space on the stack """
|
|
|
298 def __init__(self):
|
|
|
299 super().__init__()
|
|
|
300
|
|
|
301 def __repr__(self):
|
|
|
302 return 'Alloc'
|
|
|
303
|
|
|
304
|
|
|
305 class Variable(Expression):
|
|
|
306 def __init__(self, name):
|
|
|
307 self.name = name
|
|
|
308
|
|
|
309 def __repr__(self):
|
|
|
310 return 'Var {}'.format(self.name)
|
|
|
311
|
|
|
312
|
|
|
313 class LocalVariable(Variable):
|
|
|
314 def __repr__(self):
|
|
|
315 return 'Local {}'.format(self.name)
|
|
|
316
|
|
|
317
|
|
|
318 class Parameter(Variable):
|
|
|
319 def __repr__(self):
|
|
|
320 return 'Param {}'.format(self.name)
|
|
|
321
|
|
|
322
|
|
|
323 class Temp(Expression):
|
|
|
324 """ Temporary storage, same as register """
|
|
|
325 def __init__(self, name):
|
|
|
326 self.name = name
|
|
|
327
|
|
|
328 def __repr__(self):
|
|
|
329 return 'TMP_{}'.format(self.name)
|
|
|
330
|
|
|
331
|
|
|
332 class Mem(Expression):
|
|
|
333 def __init__(self, e):
|
|
|
334 self.e = e
|
|
|
335
|
|
|
336 def __repr__(self):
|
|
|
337 return '[{}]'.format(self.e)
|
|
|
338
|
|
|
339
|
|
|
340 class Statement:
|
|
|
341 """ Base class for all instructions. """
|
|
|
342 pass
|
|
|
343
|
|
|
344
|
|
|
345 class Move(Statement):
|
|
|
346 def __init__(self, dst, src):
|
|
|
347 self.dst = dst
|
|
|
348 self.src = src
|
|
|
349
|
|
|
350 def __repr__(self):
|
|
|
351 return '{} = {}'.format(self.dst, self.src)
|
|
|
352
|
|
|
353
|
|
|
354 class Exp(Statement):
|
|
|
355 def __init__(self, e):
|
|
|
356 self.e = e
|
|
|
357
|
|
|
358 def __repr__(self):
|
|
|
359 return '{}'.format(self.e)
|
|
|
360
|
|
|
361
|
|
|
362 class Label(Statement):
|
|
|
363 # TODO: is this duplicate with block?
|
|
|
364 def __init__(self, name):
|
|
|
365 self.name = name
|
|
|
366 self.statements = []
|
|
|
367
|
|
|
368 def __repr__(self):
|
|
|
369 return 'LABEL {}:'.format(self.name)
|
|
|
370
|
|
|
371
|
|
|
372 # Branching:
|
|
|
373 class LastStatement(Statement):
|
|
|
374 pass
|
|
|
375
|
|
|
376
|
|
|
377 class Terminator(LastStatement):
|
|
|
378 """ Instruction that terminates the terminal block """
|
|
|
379 Targets = []
|
|
|
380 def __repr__(self):
|
|
|
381 return 'Terminator'
|
|
|
382
|
|
|
383
|
|
|
384 class Jump(LastStatement):
|
|
|
385 def __init__(self, target):
|
|
|
386 self.target = target
|
|
|
387 self.Targets = [target]
|
|
|
388
|
|
|
389 def __repr__(self):
|
|
|
390 return 'BRANCH {}'.format(self.target.name)
|
|
|
391
|
|
|
392
|
|
|
393 class CJump(LastStatement):
|
|
|
394 conditions = ['==', '<', '>', '>=', '<=', '!=']
|
|
|
395 def __init__(self, a, cond, b, lab_yes, lab_no):
|
|
|
396 assert cond in CJump.conditions
|
|
|
397 self.a = a
|
|
|
398 self.cond = cond
|
|
|
399 self.b = b
|
|
|
400 self.lab_yes = lab_yes
|
|
|
401 self.lab_no = lab_no
|
|
|
402 self.Targets = [lab_yes, lab_no]
|
|
|
403
|
|
|
404 def __repr__(self):
|
|
|
405 return 'IF {} {} {} THEN {} ELSE {}'.format(self.a, self.cond, self.b, self.lab_yes, self.lab_no)
|
|
|
406
|
|
|
407
|
|
279
|
408 # Constructing IR:
|
|
|
409
|
|
277
|
410 class NamedClassGenerator:
|
|
|
411 def __init__(self, prefix, cls):
|
|
|
412 self.prefix = prefix
|
|
|
413 self.cls = cls
|
|
|
414 def NumGen():
|
|
|
415 a = 0
|
|
|
416 while True:
|
|
|
417 yield a
|
|
|
418 a = a + 1
|
|
|
419 self.nums = NumGen()
|
|
|
420
|
|
|
421 def gen(self, prefix=None):
|
|
|
422 if not prefix:
|
|
|
423 prefix = self.prefix
|
|
|
424 return self.cls('{0}{1}'.format(prefix, self.nums.__next__()))
|
|
|
425
|
|
|
426
|
|
|
427 class Builder:
|
|
|
428 """ Base class for ir code generators """
|
|
|
429 def __init__(self):
|
|
|
430 self.prepare()
|
|
|
431
|
|
|
432 def prepare(self):
|
|
|
433 self.newTemp = NamedClassGenerator('reg', Temp).gen
|
|
|
434 self.newBlock = NamedClassGenerator('block', Block).gen
|
|
|
435 self.bb = None
|
|
|
436 self.m = None
|
|
|
437 self.fn = None
|
|
|
438 self.loc = None
|
|
|
439
|
|
|
440 # Helpers:
|
|
|
441 def setModule(self, m):
|
|
|
442 self.m = m
|
|
|
443
|
|
|
444 def newFunction(self, name):
|
|
|
445 f = Function(name)
|
|
|
446 self.m.addFunc(f)
|
|
|
447 return f
|
|
|
448
|
|
|
449 def setFunction(self, f):
|
|
|
450 self.fn = f
|
|
|
451 self.bb = f.entry if f else None
|
|
|
452
|
|
|
453 def setBlock(self, b):
|
|
|
454 self.bb = b
|
|
|
455
|
|
|
456 def setLoc(self, l):
|
|
|
457 self.loc = l
|
|
|
458
|
|
|
459 def emit(self, i):
|
|
|
460 assert isinstance(i, Statement)
|
|
|
461 i.debugLoc = self.loc
|
|
|
462 if not self.bb:
|
|
|
463 raise Exception('No basic block')
|
|
|
464 self.bb.addInstruction(i)
|
|
|
465
|
|
|
466
|
