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