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