Mercurial > lcfOS
annotate python/ppci/ir.py @ 307:e609d5296ee9
Massive rewrite of codegenerator
author | Windel Bouwman |
---|---|
date | Thu, 12 Dec 2013 20:42:56 +0100 |
parents | 0615b5308710 |
children | 68b01c8abf8a |
rev | line source |
---|---|
277 | 1 """ |
2 Intermediate representation (IR) code classes. | |
3 """ | |
4 | |
5 class Module: | |
305 | 6 """ Container unit for variables and functions. """ |
277 | 7 def __init__(self, name): |
8 self.name = name | |
9 self.funcs = [] | |
10 self.variables = [] | |
11 | |
12 def __repr__(self): | |
13 return 'IR-module [{0}]'.format(self.name) | |
14 | |
15 def addFunc(self, f): | |
16 self.funcs.append(f) | |
17 | |
18 addFunction = addFunc | |
19 | |
20 def addVariable(self, v): | |
21 self.variables.append(v) | |
22 | |
23 def getVariables(self): | |
24 return self.variables | |
25 | |
26 Variables = property(getVariables) | |
27 | |
28 def getFunctions(self): | |
29 return self.funcs | |
30 | |
31 Functions = property(getFunctions) | |
32 | |
33 def findFunction(self, name): | |
34 for f in self.funcs: | |
35 if f.name == name: | |
36 return f | |
37 raise KeyError(name) | |
38 | |
39 getFunction = findFunction | |
40 | |
41 def dump(self, indent=' '): | |
42 print(self) | |
43 for v in self.Variables: | |
44 print(indent, v) | |
45 for fn in self.Functions: | |
46 fn.dump(indent=indent+' ') | |
47 | |
48 # Analysis functions: | |
49 def check(self): | |
50 """ Perform sanity check on module """ | |
51 for f in self.Functions: | |
52 f.check() | |
53 | |
54 | |
55 class Function: | |
305 | 56 """ Represents a function. """ |
277 | 57 def __init__(self, name): |
58 self.name = name | |
59 self.entry = Block('{}_entry'.format(name)) | |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
60 self.entry.function = self |
277 | 61 self.epiloog = Block('{}_epilog'.format(name)) |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
62 self.epiloog.function = self |
277 | 63 self.epiloog.addInstruction(Terminator()) |
64 self.return_value = Temp('{}_retval'.format(name)) | |
65 self.arguments = [] | |
66 self.localvars = [] | |
67 | |
68 def __repr__(self): | |
69 args = ','.join(str(a) for a in self.arguments) | |
70 return 'Function {}({})'.format(self.name, args) | |
71 | |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
72 def addBlock(self, bb): |
277 | 73 self.bbs.append(bb) |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
74 bb.function = self |
277 | 75 |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
76 def removeBlock(self, bb): |
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
77 #self.bbs.remove(bb) |
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
78 bb.function = None |
277 | 79 |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
80 def getBlocks(self): |
277 | 81 bbs = [self.entry] |
82 worklist = [self.entry] | |
83 while worklist: | |
84 b = worklist.pop() | |
85 for sb in b.Successors: | |
86 if sb not in bbs: | |
87 bbs.append(sb) | |
88 worklist.append(sb) | |
89 bbs.remove(self.entry) | |
90 if self.epiloog in bbs: | |
91 bbs.remove(self.epiloog) | |
92 bbs.insert(0, self.entry) | |
93 bbs.append(self.epiloog) | |
94 return bbs | |
95 | |
96 def findBasicBlock(self, name): | |
97 for bb in self.bbs: | |
98 if bb.name == name: | |
99 return bb | |
100 raise KeyError(name) | |
101 | |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
102 Blocks = property(getBlocks) |
277 | 103 |
104 @property | |
105 def Entry(self): | |
106 return self.entry | |
107 | |
108 def check(self): | |
109 for b in self.Blocks: | |
110 b.check() | |
111 | |
112 def addParameter(self, p): | |
113 assert type(p) is Parameter | |
114 p.num = len(self.arguments) | |
115 self.arguments.append(p) | |
116 | |
117 def addLocal(self, l): | |
118 assert type(l) is LocalVariable | |
119 self.localvars.append(l) | |
120 | |
121 def dump(self, indent=''): | |
122 print(indent+str(self)) | |
123 for bb in self.Blocks: | |
305 | 124 print(indent+' ' + str(bb)) |
277 | 125 for ins in bb.Instructions: |
305 | 126 print(indent + ' ' * 2 + str(ins)) |
277 | 127 |
128 | |
129 class Block: | |
305 | 130 """ |
277 | 131 Uninterrupted sequence of instructions with a label at the start. |
132 """ | |
133 def __init__(self, name): | |
134 self.name = name | |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
135 self.function = None |
277 | 136 self.instructions = [] |
137 | |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
138 parent = property(lambda s: s.function) |
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
139 |
277 | 140 def __repr__(self): |
141 return 'Block {0}'.format(self.name) | |
142 | |
143 def addInstruction(self, i): | |
144 i.parent = self | |
145 assert not isinstance(self.LastInstruction, LastStatement) | |
146 self.instructions.append(i) | |
147 | |
148 def replaceInstruction(self, i1, i2): | |
149 idx = self.instructions.index(i1) | |
150 i1.parent = None | |
151 i1.delete() | |
152 i2.parent = self | |
153 self.instructions[idx] = i2 | |
154 | |
155 def removeInstruction(self, i): | |
156 i.parent = None | |
157 i.delete() | |
158 self.instructions.remove(i) | |
159 | |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
160 @property |
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
161 def Instructions(self): |
277 | 162 return self.instructions |
163 | |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
164 @property |
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
165 def LastInstruction(self): |
277 | 166 if not self.Empty: |
167 return self.instructions[-1] | |
168 | |
169 @property | |
170 def Empty(self): | |
171 return len(self.instructions) == 0 | |
172 | |
173 @property | |
174 def FirstInstruction(self): | |
175 return self.instructions[0] | |
176 | |
177 def getSuccessors(self): | |
178 if not self.Empty: | |
179 return self.LastInstruction.Targets | |
180 return [] | |
181 Successors = property(getSuccessors) | |
182 | |
183 def getPredecessors(self): | |
184 preds = [] | |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
185 for bb in self.parent.Blocks: |
277 | 186 if self in bb.Successors: |
187 preds.append(bb) | |
188 return preds | |
189 Predecessors = property(getPredecessors) | |
190 | |
191 def precedes(self, other): | |
192 raise NotImplementedError() | |
193 | |
194 def check(self): | |
195 assert isinstance(self.LastInstruction, LastStatement) | |
196 for i in self.instructions[:-1]: | |
197 assert not isinstance(i, LastStatement) | |
198 | |
199 | |
200 # Instructions: | |
201 class Term: | |
202 def __init__(self, x): | |
203 self.x = x | |
204 | |
305 | 205 |
277 | 206 def match_tree(tree, pattern): |
207 if type(pattern) is Term: | |
208 return True, {pattern: tree} | |
305 | 209 elif type(pattern) is Binop and type(tree) is Binop and \ |
210 tree.operation == pattern.operation: | |
277 | 211 res_a, mp_a = match_tree(tree.a, pattern.a) |
212 res_b, mp_b = match_tree(tree.b, pattern.b) | |
213 assert not (mp_a.keys() & mp_b.keys()) | |
214 mp_a.update(mp_b) | |
215 return res_a and res_b, mp_a | |
305 | 216 elif type(pattern) is Const and type(tree) is Const and \ |
217 pattern.value == tree.value: | |
277 | 218 return True, {} |
219 else: | |
220 return False, {} | |
221 | |
222 | |
223 class Expression: | |
304 | 224 """ Base class for an expression """ |
277 | 225 pass |
226 | |
227 | |
228 class Const(Expression): | |
304 | 229 """ Represents a constant value """ |
277 | 230 def __init__(self, value): |
231 self.value = value | |
232 | |
233 def __repr__(self): | |
234 return 'Const {}'.format(self.value) | |
235 | |
236 | |
237 class Call(Expression): | |
305 | 238 """ Call a function with some arguments """ |
277 | 239 def __init__(self, f, arguments): |
240 self.f = f | |
241 self.arguments = arguments | |
242 | |
243 def __repr__(self): | |
244 args = ', '.join([str(arg) for arg in self.arguments]) | |
305 | 245 return '{}({})'.format(self.f, args) |
277 | 246 |
247 | |
248 # Data operations | |
249 class Binop(Expression): | |
304 | 250 """ Generic binary operation """ |
277 | 251 ops = ['+', '-', '*', '/', '|', '&', '<<', '>>'] |
305 | 252 |
277 | 253 def __init__(self, value1, operation, value2): |
254 assert operation in Binop.ops | |
255 self.a = value1 | |
256 self.b = value2 | |
257 self.operation = operation | |
258 | |
259 def __repr__(self): | |
260 a, b = self.a, self.b | |
261 return '({} {} {})'.format(a, self.operation, b) | |
262 | |
263 | |
264 def Add(a, b): | |
305 | 265 """ Add a and b """ |
277 | 266 return Binop(a, '+', b) |
267 | |
292 | 268 |
279 | 269 def Sub(a, b): |
305 | 270 """ Substract b from a """ |
279 | 271 return Binop(a, '-', b) |
272 | |
292 | 273 |
279 | 274 def Mul(a, b): |
275 return Binop(a, '*', b) | |
276 | |
292 | 277 |
279 | 278 def Div(a, b): |
279 return Binop(a, '/', b) | |
277 | 280 |
303 | 281 |
277 | 282 class Eseq(Expression): |
283 """ Sequence of instructions where the last is an expression """ | |
284 def __init__(self, stmt, e): | |
285 self.stmt = stmt | |
286 self.e = e | |
287 | |
288 def __repr__(self): | |
289 return '({}, {})'.format(self.stmt, self.e) | |
290 | |
291 | |
292 class Alloc(Expression): | |
293 """ Allocates space on the stack """ | |
294 def __init__(self): | |
295 super().__init__() | |
296 | |
297 def __repr__(self): | |
298 return 'Alloc' | |
299 | |
300 | |
301 class Variable(Expression): | |
302 def __init__(self, name): | |
303 self.name = name | |
304 | |
305 def __repr__(self): | |
306 return 'Var {}'.format(self.name) | |
307 | |
308 | |
309 class LocalVariable(Variable): | |
310 def __repr__(self): | |
311 return 'Local {}'.format(self.name) | |
312 | |
313 | |
314 class Parameter(Variable): | |
315 def __repr__(self): | |
316 return 'Param {}'.format(self.name) | |
317 | |
318 | |
319 class Temp(Expression): | |
320 """ Temporary storage, same as register """ | |
321 def __init__(self, name): | |
322 self.name = name | |
323 | |
324 def __repr__(self): | |
325 return 'TMP_{}'.format(self.name) | |
326 | |
327 | |
328 class Mem(Expression): | |
305 | 329 """ Memory access """ |
277 | 330 def __init__(self, e): |
331 self.e = e | |
332 | |
333 def __repr__(self): | |
334 return '[{}]'.format(self.e) | |
335 | |
336 | |
337 class Statement: | |
338 """ Base class for all instructions. """ | |
339 pass | |
340 | |
341 | |
342 class Move(Statement): | |
305 | 343 """ Move source to destination """ |
277 | 344 def __init__(self, dst, src): |
345 self.dst = dst | |
346 self.src = src | |
347 | |
348 def __repr__(self): | |
349 return '{} = {}'.format(self.dst, self.src) | |
350 | |
351 | |
352 class Exp(Statement): | |
353 def __init__(self, e): | |
354 self.e = e | |
355 | |
356 def __repr__(self): | |
357 return '{}'.format(self.e) | |
358 | |
359 | |
360 # Branching: | |
361 class LastStatement(Statement): | |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
362 def changeTarget(self, old, new): |
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
363 idx = self.Targets.index(old) |
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
364 self.Targets[idx] = new |
277 | 365 |
366 | |
367 class Terminator(LastStatement): | |
368 """ Instruction that terminates the terminal block """ | |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
369 def __init__(self): |
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
370 self.Targets = [] |
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
371 |
277 | 372 def __repr__(self): |
373 return 'Terminator' | |
374 | |
375 | |
376 class Jump(LastStatement): | |
304 | 377 """ Jump statement to some target location """ |
277 | 378 def __init__(self, target): |
379 self.Targets = [target] | |
380 | |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
381 def setTarget(self, t): |
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
382 self.Targets[0] = t |
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
383 target = property(lambda s: s.Targets[0], setTarget) |
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
384 |
277 | 385 def __repr__(self): |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
386 return 'JUMP {}'.format(self.target.name) |
277 | 387 |
388 | |
389 class CJump(LastStatement): | |
305 | 390 """ Conditional jump to true or false labels. """ |
277 | 391 conditions = ['==', '<', '>', '>=', '<=', '!='] |
305 | 392 |
277 | 393 def __init__(self, a, cond, b, lab_yes, lab_no): |
305 | 394 assert cond in CJump.conditions |
277 | 395 self.a = a |
396 self.cond = cond | |
397 self.b = b | |
398 self.Targets = [lab_yes, lab_no] | |
399 | |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
400 lab_yes = property(lambda s: s.Targets[0]) |
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
401 lab_no = property(lambda s: s.Targets[1]) |
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
402 |
277 | 403 def __repr__(self): |
305 | 404 return 'IF {} {} {} THEN {} ELSE {}'\ |
405 .format(self.a, self.cond, self.b, self.lab_yes, self.lab_no) |