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