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