|
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
|
|
|
277
|
|
|
278 class Eseq(Expression):
|
|
|
279 """ Sequence of instructions where the last is an expression """
|
|
|
280 def __init__(self, stmt, e):
|
|
|
281 self.stmt = stmt
|
|
|
282 self.e = e
|
|
|
283
|
|
|
284 def __repr__(self):
|
|
|
285 return '({}, {})'.format(self.stmt, self.e)
|
|
|
286
|
|
|
287
|
|
|
288 class Alloc(Expression):
|
|
|
289 """ Allocates space on the stack """
|
|
|
290 def __init__(self):
|
|
|
291 super().__init__()
|
|
|
292
|
|
|
293 def __repr__(self):
|
|
|
294 return 'Alloc'
|
|
|
295
|
|
|
296
|
|
|
297 class Variable(Expression):
|
|
|
298 def __init__(self, name):
|
|
|
299 self.name = name
|
|
|
300
|
|
|
301 def __repr__(self):
|
|
|
302 return 'Var {}'.format(self.name)
|
|
|
303
|
|
|
304
|
|
|
305 class LocalVariable(Variable):
|
|
|
306 def __repr__(self):
|
|
|
307 return 'Local {}'.format(self.name)
|
|
|
308
|
|
|
309
|
|
|
310 class Parameter(Variable):
|
|
|
311 def __repr__(self):
|
|
|
312 return 'Param {}'.format(self.name)
|
|
|
313
|
|
|
314
|
|
|
315 class Temp(Expression):
|
|
|
316 """ Temporary storage, same as register """
|
|
|
317 def __init__(self, name):
|
|
|
318 self.name = name
|
|
|
319
|
|
|
320 def __repr__(self):
|
|
|
321 return 'TMP_{}'.format(self.name)
|
|
|
322
|
|
|
323
|
|
|
324 class Mem(Expression):
|
|
|
325 def __init__(self, e):
|
|
|
326 self.e = e
|
|
|
327
|
|
|
328 def __repr__(self):
|
|
|
329 return '[{}]'.format(self.e)
|
|
|
330
|
|
|
331
|
|
|
332 class Statement:
|
|
|
333 """ Base class for all instructions. """
|
|
|
334 pass
|
|
|
335
|
|
|
336
|
|
|
337 class Move(Statement):
|
|
|
338 def __init__(self, dst, src):
|
|
|
339 self.dst = dst
|
|
|
340 self.src = src
|
|
|
341
|
|
|
342 def __repr__(self):
|
|
|
343 return '{} = {}'.format(self.dst, self.src)
|
|
|
344
|
|
|
345
|
|
|
346 class Exp(Statement):
|
|
|
347 def __init__(self, e):
|
|
|
348 self.e = e
|
|
|
349
|
|
|
350 def __repr__(self):
|
|
|
351 return '{}'.format(self.e)
|
|
|
352
|
|
|
353
|
|
|
354 class Label(Statement):
|
|
|
355 # TODO: is this duplicate with block?
|
|
|
356 def __init__(self, name):
|
|
|
357 self.name = name
|
|
|
358 self.statements = []
|
|
|
359
|
|
|
360 def __repr__(self):
|
|
|
361 return 'LABEL {}:'.format(self.name)
|
|
|
362
|
|
|
363
|
|
|
364 # Branching:
|
|
|
365 class LastStatement(Statement):
|
|
|
366 pass
|
|
|
367
|
|
|
368
|
|
|
369 class Terminator(LastStatement):
|
|
|
370 """ Instruction that terminates the terminal block """
|
|
|
371 Targets = []
|
|
|
372 def __repr__(self):
|
|
|
373 return 'Terminator'
|
|
|
374
|
|
|
375
|
|
|
376 class Jump(LastStatement):
|
|
|
377 def __init__(self, target):
|
|
|
378 self.target = target
|
|
|
379 self.Targets = [target]
|
|
|
380
|
|
|
381 def __repr__(self):
|
|
|
382 return 'BRANCH {}'.format(self.target.name)
|
|
|
383
|
|
|
384
|
|
|
385 class CJump(LastStatement):
|
|
|
386 conditions = ['==', '<', '>', '>=', '<=', '!=']
|
|
|
387 def __init__(self, a, cond, b, lab_yes, lab_no):
|
|
|
388 assert cond in CJump.conditions
|
|
|
389 self.a = a
|
|
|
390 self.cond = cond
|
|
|
391 self.b = b
|
|
|
392 self.lab_yes = lab_yes
|
|
|
393 self.lab_no = lab_no
|
|
|
394 self.Targets = [lab_yes, lab_no]
|
|
|
395
|
|
|
396 def __repr__(self):
|
|
|
397 return 'IF {} {} {} THEN {} ELSE {}'.format(self.a, self.cond, self.b, self.lab_yes, self.lab_no)
|
|
|
398
|
|
|
399
|
|
|
400 class NamedClassGenerator:
|
|
|
401 def __init__(self, prefix, cls):
|
|
|
402 self.prefix = prefix
|
|
|
403 self.cls = cls
|
|
|
404 def NumGen():
|
|
|
405 a = 0
|
|
|
406 while True:
|
|
|
407 yield a
|
|
|
408 a = a + 1
|
|
|
409 self.nums = NumGen()
|
|
|
410
|
|
|
411 def gen(self, prefix=None):
|
|
|
412 if not prefix:
|
|
|
413 prefix = self.prefix
|
|
|
414 return self.cls('{0}{1}'.format(prefix, self.nums.__next__()))
|
|
|
415
|
|
|
416
|
|
|
417 class Builder:
|
|
|
418 """ Base class for ir code generators """
|
|
|
419 def __init__(self):
|
|
|
420 self.prepare()
|
|
|
421
|
|
|
422 def prepare(self):
|
|
|
423 self.newTemp = NamedClassGenerator('reg', Temp).gen
|
|
|
424 self.newBlock = NamedClassGenerator('block', Block).gen
|
|
|
425 self.bb = None
|
|
|
426 self.m = None
|
|
|
427 self.fn = None
|
|
|
428 self.loc = None
|
|
|
429
|
|
|
430 # Helpers:
|
|
|
431 def setModule(self, m):
|
|
|
432 self.m = m
|
|
|
433
|
|
|
434 def newFunction(self, name):
|
|
|
435 f = Function(name)
|
|
|
436 self.m.addFunc(f)
|
|
|
437 return f
|
|
|
438
|
|
|
439 def setFunction(self, f):
|
|
|
440 self.fn = f
|
|
|
441 self.bb = f.entry if f else None
|
|
|
442
|
|
|
443 def setBlock(self, b):
|
|
|
444 self.bb = b
|
|
|
445
|
|
|
446 def setLoc(self, l):
|
|
|
447 self.loc = l
|
|
|
448
|
|
|
449 def emit(self, i):
|
|
|
450 assert isinstance(i, Statement)
|
|
|
451 i.debugLoc = self.loc
|
|
|
452 if not self.bb:
|
|
|
453 raise Exception('No basic block')
|
|
|
454 self.bb.addInstruction(i)
|
|
|
455
|
|
|
456
|
