Mercurial > lcfOS
annotate python/ppci/ir.py @ 304:fa99f36fabb5
Fix docs
| author | Windel Bouwman |
|---|---|
| date | Fri, 06 Dec 2013 12:45:02 +0100 |
| parents | be7f60545368 |
| children | 0615b5308710 |
| rev | line source |
|---|---|
| 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)) | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
79 self.entry.function = self |
| 277 | 80 self.epiloog = Block('{}_epilog'.format(name)) |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
81 self.epiloog.function = self |
| 277 | 82 self.epiloog.addInstruction(Terminator()) |
| 83 self.return_value = Temp('{}_retval'.format(name)) | |
| 84 self.arguments = [] | |
| 85 self.localvars = [] | |
| 86 | |
| 87 def __repr__(self): | |
| 88 args = ','.join(str(a) for a in self.arguments) | |
| 89 return 'Function {}({})'.format(self.name, args) | |
| 90 | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
91 def addBlock(self, bb): |
| 277 | 92 self.bbs.append(bb) |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
93 bb.function = self |
| 277 | 94 |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
95 def removeBlock(self, bb): |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
96 #self.bbs.remove(bb) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
97 bb.function = None |
| 277 | 98 |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
99 def getBlocks(self): |
| 277 | 100 bbs = [self.entry] |
| 101 worklist = [self.entry] | |
| 102 while worklist: | |
| 103 b = worklist.pop() | |
| 104 for sb in b.Successors: | |
| 105 if sb not in bbs: | |
| 106 bbs.append(sb) | |
| 107 worklist.append(sb) | |
| 108 bbs.remove(self.entry) | |
| 109 if self.epiloog in bbs: | |
| 110 bbs.remove(self.epiloog) | |
| 111 bbs.insert(0, self.entry) | |
| 112 bbs.append(self.epiloog) | |
| 113 return bbs | |
| 114 | |
| 115 def findBasicBlock(self, name): | |
| 116 for bb in self.bbs: | |
| 117 if bb.name == name: | |
| 118 return bb | |
| 119 raise KeyError(name) | |
| 120 | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
121 Blocks = property(getBlocks) |
| 277 | 122 |
| 123 @property | |
| 124 def Entry(self): | |
| 125 return self.entry | |
| 126 | |
| 127 def check(self): | |
| 128 for b in self.Blocks: | |
| 129 b.check() | |
| 130 | |
| 131 def addParameter(self, p): | |
| 132 assert type(p) is Parameter | |
| 133 p.num = len(self.arguments) | |
| 134 self.arguments.append(p) | |
| 135 | |
| 136 def addLocal(self, l): | |
| 137 assert type(l) is LocalVariable | |
| 138 self.localvars.append(l) | |
| 139 | |
| 140 def dump(self, indent=''): | |
| 141 print(indent+str(self)) | |
| 142 for bb in self.Blocks: | |
| 143 print(indent+' '+str(bb)) | |
| 144 for ins in bb.Instructions: | |
| 145 print(indent +' '*2 + str(ins)) | |
| 146 | |
| 147 | |
| 148 class Block: | |
| 149 """ | |
| 150 Uninterrupted sequence of instructions with a label at the start. | |
| 151 """ | |
| 152 def __init__(self, name): | |
| 153 self.name = name | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
154 self.function = None |
| 277 | 155 self.instructions = [] |
| 156 | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
157 parent = property(lambda s: s.function) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
158 |
| 277 | 159 def __repr__(self): |
| 160 return 'Block {0}'.format(self.name) | |
| 161 | |
| 162 def addInstruction(self, i): | |
| 163 i.parent = self | |
| 164 assert not isinstance(self.LastInstruction, LastStatement) | |
| 165 self.instructions.append(i) | |
| 166 | |
| 167 def replaceInstruction(self, i1, i2): | |
| 168 idx = self.instructions.index(i1) | |
| 169 i1.parent = None | |
| 170 i1.delete() | |
| 171 i2.parent = self | |
| 172 self.instructions[idx] = i2 | |
| 173 | |
| 174 def removeInstruction(self, i): | |
| 175 i.parent = None | |
| 176 i.delete() | |
| 177 self.instructions.remove(i) | |
| 178 | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
179 @property |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
180 def Instructions(self): |
| 277 | 181 return self.instructions |
| 182 | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
183 @property |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
184 def LastInstruction(self): |
| 277 | 185 if not self.Empty: |
| 186 return self.instructions[-1] | |
| 187 | |
| 188 @property | |
| 189 def Empty(self): | |
| 190 return len(self.instructions) == 0 | |
| 191 | |
| 192 @property | |
| 193 def FirstInstruction(self): | |
| 194 return self.instructions[0] | |
| 195 | |
| 196 def getSuccessors(self): | |
| 197 if not self.Empty: | |
| 198 return self.LastInstruction.Targets | |
| 199 return [] | |
| 200 Successors = property(getSuccessors) | |
| 201 | |
| 202 def getPredecessors(self): | |
| 203 preds = [] | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
204 for bb in self.parent.Blocks: |
| 277 | 205 if self in bb.Successors: |
| 206 preds.append(bb) | |
| 207 return preds | |
| 208 Predecessors = property(getPredecessors) | |
| 209 | |
| 210 def precedes(self, other): | |
| 211 raise NotImplementedError() | |
| 212 | |
| 213 def check(self): | |
| 214 assert isinstance(self.LastInstruction, LastStatement) | |
| 215 for i in self.instructions[:-1]: | |
| 216 assert not isinstance(i, LastStatement) | |
| 217 | |
| 218 | |
| 219 # Instructions: | |
| 220 class Term: | |
| 221 def __init__(self, x): | |
| 222 self.x = x | |
| 223 | |
| 224 def match_tree(tree, pattern): | |
| 225 if type(pattern) is Term: | |
| 226 return True, {pattern: tree} | |
| 227 elif type(pattern) is Binop and type(tree) is Binop and tree.operation == pattern.operation: | |
| 228 res_a, mp_a = match_tree(tree.a, pattern.a) | |
| 229 res_b, mp_b = match_tree(tree.b, pattern.b) | |
| 230 assert not (mp_a.keys() & mp_b.keys()) | |
| 231 mp_a.update(mp_b) | |
| 232 return res_a and res_b, mp_a | |
| 233 elif type(pattern) is Const and type(tree) is Const and pattern.value == tree.value: | |
| 234 return True, {} | |
| 235 else: | |
| 236 return False, {} | |
| 237 | |
| 238 | |
| 239 class Expression: | |
| 304 | 240 """ Base class for an expression """ |
| 277 | 241 pass |
| 242 | |
| 243 | |
| 244 class Const(Expression): | |
| 304 | 245 """ Represents a constant value """ |
| 277 | 246 def __init__(self, value): |
| 247 self.value = value | |
| 248 | |
| 249 def __repr__(self): | |
| 250 return 'Const {}'.format(self.value) | |
| 251 | |
| 252 | |
| 253 # Function calling: | |
| 254 class Call(Expression): | |
| 255 def __init__(self, f, arguments): | |
| 256 self.f = f | |
| 257 assert type(f) is Function | |
| 258 self.arguments = arguments | |
| 259 | |
| 260 def __repr__(self): | |
| 261 args = ', '.join([str(arg) for arg in self.arguments]) | |
| 262 return '{}({})'.format(self.f.name, args) | |
| 263 | |
| 264 | |
| 265 # Data operations | |
| 266 class Binop(Expression): | |
| 304 | 267 """ Generic binary operation """ |
| 277 | 268 ops = ['+', '-', '*', '/', '|', '&', '<<', '>>'] |
| 269 def __init__(self, value1, operation, value2): | |
| 270 assert operation in Binop.ops | |
| 271 self.a = value1 | |
| 272 self.b = value2 | |
| 273 self.operation = operation | |
| 274 | |
| 275 def __repr__(self): | |
| 276 a, b = self.a, self.b | |
| 277 return '({} {} {})'.format(a, self.operation, b) | |
| 278 | |
| 279 | |
| 280 def Add(a, b): | |
| 281 """ Convenience call """ | |
| 282 return Binop(a, '+', b) | |
| 283 | |
| 292 | 284 |
| 279 | 285 def Sub(a, b): |
| 286 return Binop(a, '-', b) | |
| 287 | |
| 292 | 288 |
| 279 | 289 def Mul(a, b): |
| 290 return Binop(a, '*', b) | |
| 291 | |
| 292 | 292 |
| 279 | 293 def Div(a, b): |
| 294 return Binop(a, '/', b) | |
| 277 | 295 |
| 303 | 296 |
| 277 | 297 class Eseq(Expression): |
| 298 """ Sequence of instructions where the last is an expression """ | |
| 299 def __init__(self, stmt, e): | |
| 300 self.stmt = stmt | |
| 301 self.e = e | |
| 302 | |
| 303 def __repr__(self): | |
| 304 return '({}, {})'.format(self.stmt, self.e) | |
| 305 | |
| 306 | |
| 307 class Alloc(Expression): | |
| 308 """ Allocates space on the stack """ | |
| 309 def __init__(self): | |
| 310 super().__init__() | |
| 311 | |
| 312 def __repr__(self): | |
| 313 return 'Alloc' | |
| 314 | |
| 315 | |
| 316 class Variable(Expression): | |
| 317 def __init__(self, name): | |
| 318 self.name = name | |
| 319 | |
| 320 def __repr__(self): | |
| 321 return 'Var {}'.format(self.name) | |
| 322 | |
| 323 | |
| 324 class LocalVariable(Variable): | |
| 325 def __repr__(self): | |
| 326 return 'Local {}'.format(self.name) | |
| 327 | |
| 328 | |
| 329 class Parameter(Variable): | |
| 330 def __repr__(self): | |
| 331 return 'Param {}'.format(self.name) | |
| 332 | |
| 333 | |
| 334 class Temp(Expression): | |
| 335 """ Temporary storage, same as register """ | |
| 336 def __init__(self, name): | |
| 337 self.name = name | |
| 338 | |
| 339 def __repr__(self): | |
| 340 return 'TMP_{}'.format(self.name) | |
| 341 | |
| 342 | |
| 343 class Mem(Expression): | |
| 344 def __init__(self, e): | |
| 345 self.e = e | |
| 346 | |
| 347 def __repr__(self): | |
| 348 return '[{}]'.format(self.e) | |
| 349 | |
| 350 | |
| 351 class Statement: | |
| 352 """ Base class for all instructions. """ | |
| 353 pass | |
| 354 | |
| 355 | |
| 356 class Move(Statement): | |
| 357 def __init__(self, dst, src): | |
| 358 self.dst = dst | |
| 359 self.src = src | |
| 360 | |
| 361 def __repr__(self): | |
| 362 return '{} = {}'.format(self.dst, self.src) | |
| 363 | |
| 364 | |
| 365 class Exp(Statement): | |
| 366 def __init__(self, e): | |
| 367 self.e = e | |
| 368 | |
| 369 def __repr__(self): | |
| 370 return '{}'.format(self.e) | |
| 371 | |
| 372 | |
| 373 # Branching: | |
| 374 class LastStatement(Statement): | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
375 def changeTarget(self, old, new): |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
376 idx = self.Targets.index(old) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
377 self.Targets[idx] = new |
| 277 | 378 |
| 379 | |
| 380 class Terminator(LastStatement): | |
| 381 """ Instruction that terminates the terminal block """ | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
382 def __init__(self): |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
383 self.Targets = [] |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
384 |
| 277 | 385 def __repr__(self): |
| 386 return 'Terminator' | |
| 387 | |
| 388 | |
| 389 class Jump(LastStatement): | |
| 304 | 390 """ Jump statement to some target location """ |
| 277 | 391 def __init__(self, target): |
| 392 self.Targets = [target] | |
| 393 | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
394 def setTarget(self, t): |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
395 self.Targets[0] = t |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
396 target = property(lambda s: s.Targets[0], setTarget) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
397 |
| 277 | 398 def __repr__(self): |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
399 return 'JUMP {}'.format(self.target.name) |
| 277 | 400 |
| 401 | |
| 402 class CJump(LastStatement): | |
| 403 conditions = ['==', '<', '>', '>=', '<=', '!='] | |
| 404 def __init__(self, a, cond, b, lab_yes, lab_no): | |
| 405 assert cond in CJump.conditions | |
| 406 self.a = a | |
| 407 self.cond = cond | |
| 408 self.b = b | |
| 409 self.Targets = [lab_yes, lab_no] | |
| 410 | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
411 lab_yes = property(lambda s: s.Targets[0]) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
412 lab_no = property(lambda s: s.Targets[1]) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
413 |
| 277 | 414 def __repr__(self): |
| 415 return 'IF {} {} {} THEN {} ELSE {}'.format(self.a, self.cond, self.b, self.lab_yes, self.lab_no) | |
| 416 | |
| 417 | |
| 279 | 418 # Constructing IR: |
| 419 | |
| 277 | 420 class NamedClassGenerator: |
| 421 def __init__(self, prefix, cls): | |
| 422 self.prefix = prefix | |
| 423 self.cls = cls | |
| 424 def NumGen(): | |
| 425 a = 0 | |
| 426 while True: | |
| 427 yield a | |
| 428 a = a + 1 | |
| 429 self.nums = NumGen() | |
| 430 | |
| 431 def gen(self, prefix=None): | |
| 432 if not prefix: | |
| 433 prefix = self.prefix | |
| 434 return self.cls('{0}{1}'.format(prefix, self.nums.__next__())) | |
| 435 | |
| 436 | |
| 437 class Builder: | |
| 438 """ Base class for ir code generators """ | |
| 439 def __init__(self): | |
| 440 self.prepare() | |
| 441 | |
| 442 def prepare(self): | |
| 443 self.newTemp = NamedClassGenerator('reg', Temp).gen | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
444 self.newBlock2 = NamedClassGenerator('block', Block).gen |
| 277 | 445 self.bb = None |
| 446 self.m = None | |
| 447 self.fn = None | |
| 448 self.loc = None | |
| 449 | |
| 450 # Helpers: | |
| 451 def setModule(self, m): | |
| 452 self.m = m | |
| 453 | |
| 454 def newFunction(self, name): | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
455 f = Function(name) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
456 self.m.addFunc(f) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
457 return f |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
458 |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
459 def newBlock(self): |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
460 assert self.fn |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
461 b = self.newBlock2() |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
462 b.function = self.fn |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
463 return b |
| 277 | 464 |
| 465 def setFunction(self, f): | |
| 466 self.fn = f | |
| 467 self.bb = f.entry if f else None | |
| 468 | |
| 469 def setBlock(self, b): | |
| 470 self.bb = b | |
| 471 | |
| 472 def setLoc(self, l): | |
| 473 self.loc = l | |
| 474 | |
| 475 def emit(self, i): | |
| 476 assert isinstance(i, Statement) | |
| 477 i.debugLoc = self.loc | |
| 478 if not self.bb: | |
| 479 raise Exception('No basic block') | |
| 480 self.bb.addInstruction(i) |