Mercurial > lcfOS
annotate python/ppci/ir.py @ 394:988f3fb861e4
c3 code generator rewrite
| author | Windel Bouwman |
|---|---|
| date | Thu, 22 May 2014 08:14:12 +0200 |
| parents | 9667d78ba79e |
| children |
| rev | line source |
|---|---|
| 277 | 1 """ |
| 2 Intermediate representation (IR) code classes. | |
| 3 """ | |
| 4 | |
| 310 | 5 |
|
336
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
317
diff
changeset
|
6 def label_name(dut): |
| 394 | 7 """ Returns the assembly code label name """ |
|
336
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
317
diff
changeset
|
8 if isinstance(dut, Block): |
|
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
317
diff
changeset
|
9 f = dut.function |
|
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
317
diff
changeset
|
10 return label_name(f) + '_' + dut.name |
| 364 | 11 elif isinstance(dut, Function) or isinstance(dut, GlobalVariable): |
|
336
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
317
diff
changeset
|
12 return label_name(dut.module) + '_' + dut.name |
|
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
317
diff
changeset
|
13 elif isinstance(dut, Module): |
|
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
317
diff
changeset
|
14 return dut.name |
|
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
317
diff
changeset
|
15 else: |
|
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
317
diff
changeset
|
16 raise NotImplementedError(str(dut)) |
|
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
317
diff
changeset
|
17 |
|
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
317
diff
changeset
|
18 |
| 394 | 19 class Typ: |
| 20 def __init__(self): | |
| 21 pass | |
| 22 | |
| 23 | |
| 24 i32 = Typ() | |
| 25 i8 = Typ() | |
| 26 | |
| 277 | 27 class Module: |
| 305 | 28 """ Container unit for variables and functions. """ |
| 277 | 29 def __init__(self, name): |
| 30 self.name = name | |
| 309 | 31 self.functions = [] |
| 277 | 32 self.variables = [] |
| 33 | |
| 34 def __repr__(self): | |
| 309 | 35 return 'module {0}'.format(self.name) |
| 277 | 36 |
| 309 | 37 def add_function(self, f): |
| 38 """ Add a function to this module """ | |
| 39 self.functions.append(f) | |
|
336
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
317
diff
changeset
|
40 f.module = self |
| 277 | 41 |
|
336
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
317
diff
changeset
|
42 def add_variable(self, v): |
| 364 | 43 assert type(v) is GlobalVariable |
| 277 | 44 self.variables.append(v) |
| 364 | 45 v.module = self |
| 277 | 46 |
| 363 | 47 def get_variables(self): |
| 277 | 48 return self.variables |
| 49 | |
| 363 | 50 Variables = property(get_variables) |
| 277 | 51 |
| 377 | 52 def get_functions(self): |
| 309 | 53 return self.functions |
| 277 | 54 |
| 377 | 55 Functions = property(get_functions) |
| 277 | 56 |
| 394 | 57 def find_function(self, name): |
| 277 | 58 for f in self.funcs: |
| 59 if f.name == name: | |
| 60 return f | |
| 61 raise KeyError(name) | |
| 62 | |
| 63 | |
| 64 class Function: | |
| 305 | 65 """ Represents a function. """ |
| 309 | 66 def __init__(self, name, module=None): |
| 277 | 67 self.name = name |
|
336
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
317
diff
changeset
|
68 self.entry = Block('entry') |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
69 self.entry.function = self |
|
336
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
317
diff
changeset
|
70 self.epiloog = Block('epilog') |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
71 self.epiloog.function = self |
| 277 | 72 self.epiloog.addInstruction(Terminator()) |
| 73 self.return_value = Temp('{}_retval'.format(name)) | |
| 74 self.arguments = [] | |
| 75 self.localvars = [] | |
| 309 | 76 if module: |
| 77 module.add_function(self) | |
| 277 | 78 |
| 79 def __repr__(self): | |
| 80 args = ','.join(str(a) for a in self.arguments) | |
| 309 | 81 return 'function i32 {}({})'.format(self.name, args) |
| 277 | 82 |
| 309 | 83 def add_block(self, bb): |
| 84 #self.bbs.append(bb) | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
85 bb.function = self |
| 277 | 86 |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
87 def removeBlock(self, bb): |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
88 #self.bbs.remove(bb) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
89 bb.function = None |
| 277 | 90 |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
91 def getBlocks(self): |
| 277 | 92 bbs = [self.entry] |
| 93 worklist = [self.entry] | |
| 94 while worklist: | |
| 95 b = worklist.pop() | |
| 96 for sb in b.Successors: | |
| 97 if sb not in bbs: | |
| 98 bbs.append(sb) | |
| 99 worklist.append(sb) | |
| 100 bbs.remove(self.entry) | |
| 101 if self.epiloog in bbs: | |
| 102 bbs.remove(self.epiloog) | |
| 103 bbs.insert(0, self.entry) | |
| 104 bbs.append(self.epiloog) | |
| 105 return bbs | |
| 106 | |
| 107 def findBasicBlock(self, name): | |
| 108 for bb in self.bbs: | |
| 109 if bb.name == name: | |
| 110 return bb | |
| 111 raise KeyError(name) | |
| 112 | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
113 Blocks = property(getBlocks) |
| 277 | 114 |
| 115 @property | |
| 116 def Entry(self): | |
| 117 return self.entry | |
| 118 | |
| 119 def check(self): | |
| 120 for b in self.Blocks: | |
| 121 b.check() | |
| 122 | |
| 123 def addParameter(self, p): | |
| 124 assert type(p) is Parameter | |
| 125 p.num = len(self.arguments) | |
| 126 self.arguments.append(p) | |
| 127 | |
| 128 def addLocal(self, l): | |
| 129 assert type(l) is LocalVariable | |
| 130 self.localvars.append(l) | |
| 131 | |
| 132 | |
| 133 class Block: | |
| 305 | 134 """ |
| 277 | 135 Uninterrupted sequence of instructions with a label at the start. |
| 136 """ | |
| 317 | 137 def __init__(self, name, function=None): |
| 277 | 138 self.name = name |
| 317 | 139 self.function = function |
| 277 | 140 self.instructions = [] |
| 141 | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
142 parent = property(lambda s: s.function) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
143 |
| 277 | 144 def __repr__(self): |
| 309 | 145 return '{0}:'.format(self.name) |
| 277 | 146 |
| 147 def addInstruction(self, i): | |
| 148 i.parent = self | |
| 149 assert not isinstance(self.LastInstruction, LastStatement) | |
| 150 self.instructions.append(i) | |
| 151 | |
| 152 def replaceInstruction(self, i1, i2): | |
| 153 idx = self.instructions.index(i1) | |
| 154 i1.parent = None | |
| 155 i1.delete() | |
| 156 i2.parent = self | |
| 157 self.instructions[idx] = i2 | |
| 158 | |
| 159 def removeInstruction(self, i): | |
| 160 i.parent = None | |
| 317 | 161 #i.delete() |
| 277 | 162 self.instructions.remove(i) |
| 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 Instructions(self): |
| 277 | 166 return self.instructions |
| 167 | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
168 @property |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
169 def LastInstruction(self): |
| 277 | 170 if not self.Empty: |
| 171 return self.instructions[-1] | |
| 172 | |
| 173 @property | |
| 174 def Empty(self): | |
| 175 return len(self.instructions) == 0 | |
| 176 | |
| 177 @property | |
| 178 def FirstInstruction(self): | |
| 179 return self.instructions[0] | |
| 180 | |
| 181 def getSuccessors(self): | |
| 182 if not self.Empty: | |
| 183 return self.LastInstruction.Targets | |
| 184 return [] | |
| 312 | 185 |
| 277 | 186 Successors = property(getSuccessors) |
| 187 | |
| 188 def getPredecessors(self): | |
| 189 preds = [] | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
190 for bb in self.parent.Blocks: |
| 277 | 191 if self in bb.Successors: |
| 192 preds.append(bb) | |
| 193 return preds | |
| 312 | 194 |
| 277 | 195 Predecessors = property(getPredecessors) |
| 196 | |
| 197 def precedes(self, other): | |
| 198 raise NotImplementedError() | |
| 199 | |
| 200 | |
| 201 # Instructions: | |
| 202 | |
| 377 | 203 class Value: |
| 394 | 204 """ A value has a type and a name """ |
| 205 def __init__(self, name, ty): | |
| 206 assert isinstance(ty, Typ) | |
| 207 self.name = name | |
| 208 self.ty = ty | |
| 209 | |
| 377 | 210 |
| 394 | 211 class User(Value): |
| 212 """ Value that uses other values """ | |
| 213 def __init__(self, name, ty): | |
| 214 super().__init__(name, ty) | |
| 215 # Create a collection to store the values this value uses. | |
| 216 # TODO: think of better naming.. | |
| 217 self.uses = set() | |
| 218 | |
| 219 def add_use(self, v): | |
| 220 assert isinstance(v, Value) | |
| 221 self.uses.add(v) | |
| 222 | |
| 223 | |
| 224 class Expression(User): | |
| 304 | 225 """ Base class for an expression """ |
| 277 | 226 pass |
| 227 | |
| 228 | |
| 229 class Const(Expression): | |
| 304 | 230 """ Represents a constant value """ |
| 277 | 231 def __init__(self, value): |
| 232 self.value = value | |
| 233 | |
| 234 def __repr__(self): | |
| 235 return 'Const {}'.format(self.value) | |
| 236 | |
| 237 | |
| 238 class Call(Expression): | |
| 305 | 239 """ Call a function with some arguments """ |
| 277 | 240 def __init__(self, f, arguments): |
|
336
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
317
diff
changeset
|
241 assert type(f) is str |
| 277 | 242 self.f = f |
| 243 self.arguments = arguments | |
| 244 | |
| 245 def __repr__(self): | |
| 354 | 246 args = ', '.join(str(arg) for arg in self.arguments) |
| 305 | 247 return '{}({})'.format(self.f, args) |
| 277 | 248 |
| 249 | |
| 250 # Data operations | |
| 251 class Binop(Expression): | |
| 304 | 252 """ Generic binary operation """ |
| 277 | 253 ops = ['+', '-', '*', '/', '|', '&', '<<', '>>'] |
| 305 | 254 |
| 394 | 255 def __init__(self, a, operation, b, name, ty): |
| 256 super().__init__(name, ty) | |
| 277 | 257 assert operation in Binop.ops |
| 377 | 258 #assert type(value1) is type(value2) |
| 394 | 259 assert isinstance(a, Value), str(a) |
| 260 assert isinstance(b, Value), str(b) | |
| 261 self.a = a | |
| 262 self.b = b | |
| 277 | 263 self.operation = operation |
| 264 | |
| 265 def __repr__(self): | |
| 266 a, b = self.a, self.b | |
| 267 return '({} {} {})'.format(a, self.operation, b) | |
| 268 | |
| 269 | |
| 394 | 270 class Add(Binop): |
| 305 | 271 """ Add a and b """ |
| 394 | 272 def __init__(self, a, b, name, ty): |
| 273 super().__init__(a, '+', b, name, ty) | |
| 277 | 274 |
| 292 | 275 |
| 279 | 276 def Sub(a, b): |
| 305 | 277 """ Substract b from a """ |
| 279 | 278 return Binop(a, '-', b) |
| 279 | |
| 292 | 280 |
| 394 | 281 def Mul(a, b, name, ty): |
| 309 | 282 """ Multiply a by b """ |
| 394 | 283 return Binop(a, '*', b, name, ty) |
| 279 | 284 |
| 292 | 285 |
| 279 | 286 def Div(a, b): |
| 309 | 287 """ Divide a in b pieces """ |
| 279 | 288 return Binop(a, '/', b) |
| 277 | 289 |
| 303 | 290 |
| 394 | 291 def Phi(User): |
| 292 """ Imaginary phi instruction to make SSA possible. """ | |
| 293 def __init__(self, name, ty): | |
| 294 super().__init__(name, ty) | |
| 295 self.inputs = [] | |
| 296 | |
| 297 def add_input(self, value, block): | |
| 298 self.inputs.append((value, block)) | |
| 299 | |
| 300 | |
| 277 | 301 class Eseq(Expression): |
| 302 """ Sequence of instructions where the last is an expression """ | |
| 303 def __init__(self, stmt, e): | |
| 304 self.stmt = stmt | |
| 305 self.e = e | |
| 306 | |
| 307 def __repr__(self): | |
| 308 return '({}, {})'.format(self.stmt, self.e) | |
| 309 | |
| 310 | |
| 311 class Alloc(Expression): | |
| 312 """ Allocates space on the stack """ | |
| 313 def __init__(self): | |
| 314 super().__init__() | |
| 315 | |
| 316 def __repr__(self): | |
| 317 return 'Alloc' | |
| 318 | |
| 319 | |
| 320 class Variable(Expression): | |
| 394 | 321 def __init__(self, name, ty): |
| 322 super().__init__(name, ty) | |
| 277 | 323 self.name = name |
| 324 | |
| 325 def __repr__(self): | |
| 326 return 'Var {}'.format(self.name) | |
| 327 | |
| 328 | |
| 329 class LocalVariable(Variable): | |
| 330 def __repr__(self): | |
| 331 return 'Local {}'.format(self.name) | |
| 332 | |
| 333 | |
| 363 | 334 class GlobalVariable(Variable): |
| 335 def __repr__(self): | |
| 336 return 'Global {}'.format(self.name) | |
| 337 | |
| 338 | |
| 277 | 339 class Parameter(Variable): |
| 340 def __repr__(self): | |
| 341 return 'Param {}'.format(self.name) | |
| 342 | |
| 343 | |
| 344 class Temp(Expression): | |
| 345 """ Temporary storage, same as register """ | |
| 346 def __init__(self, name): | |
| 347 self.name = name | |
| 348 | |
| 349 def __repr__(self): | |
| 350 return 'TMP_{}'.format(self.name) | |
| 351 | |
| 352 | |
| 353 class Mem(Expression): | |
| 305 | 354 """ Memory access """ |
| 277 | 355 def __init__(self, e): |
| 356 self.e = e | |
| 357 | |
| 358 def __repr__(self): | |
| 359 return '[{}]'.format(self.e) | |
| 360 | |
| 361 | |
| 394 | 362 class Load(Value): |
| 363 """ Load a value from memory """ | |
| 364 def __init__(self, address, name, ty): | |
| 365 super().__init__(name, ty) | |
| 366 assert isinstance(address, Value) | |
| 367 self.address = address | |
| 368 | |
| 369 def __repr__(self): | |
| 370 return 'load {}'.format(self.address) | |
| 371 | |
| 372 | |
| 373 class Store: | |
| 374 """ Store a value into memory """ | |
| 375 def __init__(self, address, value): | |
| 376 self.address = address | |
| 377 | |
| 378 | |
| 354 | 379 class Addr(Expression): |
| 380 """ Address of label """ | |
| 381 def __init__(self, e): | |
| 382 self.e = e | |
| 383 | |
| 384 def __repr__(self): | |
| 385 return '&{}'.format(self.e) | |
| 386 | |
| 387 | |
| 277 | 388 class Statement: |
| 389 """ Base class for all instructions. """ | |
| 312 | 390 @property |
| 391 def IsTerminator(self): | |
| 392 return isinstance(self, LastStatement) | |
| 277 | 393 |
| 394 | |
| 395 class Move(Statement): | |
| 305 | 396 """ Move source to destination """ |
| 277 | 397 def __init__(self, dst, src): |
| 398 self.dst = dst | |
| 399 self.src = src | |
| 400 | |
| 401 def __repr__(self): | |
| 402 return '{} = {}'.format(self.dst, self.src) | |
| 403 | |
| 404 | |
| 405 class Exp(Statement): | |
| 406 def __init__(self, e): | |
| 407 self.e = e | |
| 408 | |
| 409 def __repr__(self): | |
| 410 return '{}'.format(self.e) | |
| 411 | |
| 412 | |
| 413 # Branching: | |
| 414 class LastStatement(Statement): | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
415 def changeTarget(self, old, new): |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
416 idx = self.Targets.index(old) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
417 self.Targets[idx] = new |
| 277 | 418 |
| 419 | |
| 420 class Terminator(LastStatement): | |
| 421 """ Instruction that terminates the terminal block """ | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
422 def __init__(self): |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
423 self.Targets = [] |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
424 |
| 277 | 425 def __repr__(self): |
| 426 return 'Terminator' | |
| 427 | |
| 428 | |
| 429 class Jump(LastStatement): | |
| 304 | 430 """ Jump statement to some target location """ |
| 277 | 431 def __init__(self, target): |
| 432 self.Targets = [target] | |
| 433 | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
434 def setTarget(self, t): |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
435 self.Targets[0] = t |
| 310 | 436 |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
437 target = property(lambda s: s.Targets[0], setTarget) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
438 |
| 277 | 439 def __repr__(self): |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
440 return 'JUMP {}'.format(self.target.name) |
| 277 | 441 |
| 442 | |
| 443 class CJump(LastStatement): | |
| 305 | 444 """ Conditional jump to true or false labels. """ |
| 277 | 445 conditions = ['==', '<', '>', '>=', '<=', '!='] |
| 305 | 446 |
| 277 | 447 def __init__(self, a, cond, b, lab_yes, lab_no): |
| 305 | 448 assert cond in CJump.conditions |
| 277 | 449 self.a = a |
| 450 self.cond = cond | |
| 451 self.b = b | |
| 452 self.Targets = [lab_yes, lab_no] | |
| 453 | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
454 lab_yes = property(lambda s: s.Targets[0]) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
455 lab_no = property(lambda s: s.Targets[1]) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
456 |
| 277 | 457 def __repr__(self): |
| 305 | 458 return 'IF {} {} {} THEN {} ELSE {}'\ |
| 459 .format(self.a, self.cond, self.b, self.lab_yes, self.lab_no) |