Mercurial > lcfOS
annotate python/ppci/c3/codegenerator.py @ 316:56e6ff84f646
Fixed burn led demo
| author | Windel Bouwman |
|---|---|
| date | Sat, 21 Dec 2013 13:13:26 +0100 |
| parents | 084cccaa5deb |
| children | 6f4753202b9a |
| rev | line source |
|---|---|
| 255 | 1 import logging |
| 301 | 2 from .. import ir |
| 307 | 3 from .. import irutils |
| 308 | 4 from . import astnodes as ast |
| 230 | 5 |
| 228 | 6 |
| 307 | 7 class SemanticError(Exception): |
| 308 | 8 """ Error thrown when a semantic issue is observed """ |
| 307 | 9 def __init__(self, msg, loc): |
| 308 | 10 super().__init__() |
| 307 | 11 self.msg = msg |
| 12 self.loc = loc | |
| 13 | |
| 14 | |
| 15 class CodeGenerator(irutils.Builder): | |
| 288 | 16 """ |
| 274 | 17 Generates intermediate (IR) code from a package. The entry function is |
| 18 'genModule'. The main task of this part is to rewrite complex control | |
| 19 structures, such as while and for loops into simple conditional | |
| 20 jump statements. Also complex conditional statements are simplified. | |
| 21 Such as 'and' and 'or' statements are rewritten in conditional jumps. | |
| 22 And structured datatypes are rewritten. | |
| 307 | 23 |
| 24 Type checking is done in one run with code generation. | |
| 274 | 25 """ |
| 307 | 26 def __init__(self, diag): |
| 261 | 27 self.logger = logging.getLogger('c3cgen') |
| 307 | 28 self.diag = diag |
| 261 | 29 |
| 217 | 30 def gencode(self, pkg): |
| 308 | 31 """ Generate code for a single module """ |
| 268 | 32 self.prepare() |
| 308 | 33 assert type(pkg) is ast.Package |
| 307 | 34 self.pkg = pkg |
| 35 self.intType = pkg.scope['int'] | |
| 36 self.boolType = pkg.scope['bool'] | |
| 313 | 37 self.logger.info('Generating ir-code for {}'.format(pkg.name), extra={'c3_ast':pkg}) |
| 288 | 38 self.varMap = {} # Maps variables to storage locations. |
| 217 | 39 self.funcMap = {} |
| 268 | 40 self.m = ir.Module(pkg.name) |
| 307 | 41 try: |
| 42 for s in pkg.innerScope.Functions: | |
| 43 f = self.newFunction(s.name) | |
| 44 self.funcMap[s] = f | |
| 45 for v in pkg.innerScope.Variables: | |
| 46 self.varMap[v] = self.newTemp() | |
| 47 for s in pkg.innerScope.Functions: | |
| 308 | 48 self.gen_function(s) |
| 307 | 49 except SemanticError as e: |
| 50 self.error(e.msg, e.loc) | |
| 313 | 51 if self.pkg.ok: |
| 52 return self.m | |
| 308 | 53 |
| 54 def error(self, msg, loc=None): | |
| 55 self.pkg.ok = False | |
| 56 self.diag.error(msg, loc) | |
| 307 | 57 |
| 308 | 58 def gen_function(self, fn): |
| 268 | 59 # TODO: handle arguments |
| 60 f = self.funcMap[fn] | |
| 272 | 61 f.return_value = self.newTemp() |
| 268 | 62 self.setFunction(f) |
| 269 | 63 l2 = self.newBlock() |
| 64 self.emit(ir.Jump(l2)) | |
| 65 self.setBlock(l2) | |
| 268 | 66 # generate room for locals: |
| 174 | 67 |
| 268 | 68 for sym in fn.innerScope: |
| 316 | 69 self.the_type(sym.typ) |
| 272 | 70 if sym.isParameter: |
| 316 | 71 p = ir.Parameter(sym.name) |
| 72 variable = ir.LocalVariable(sym.name + '_copy') | |
| 73 f.addParameter(p) | |
| 74 f.addLocal(variable) | |
| 75 # Move parameter into local copy: | |
| 76 self.emit(ir.Move(ir.Mem(variable), p)) | |
| 274 | 77 elif sym.isLocal: |
| 308 | 78 variable = ir.LocalVariable(sym.name) |
| 79 f.addLocal(variable) | |
| 80 elif isinstance(sym, ast.Variable): | |
| 81 variable = ir.LocalVariable(sym.name) | |
| 82 f.addLocal(variable) | |
| 274 | 83 else: |
| 275 | 84 raise NotImplementedError('{}'.format(sym)) |
| 308 | 85 self.varMap[sym] = variable |
| 268 | 86 |
| 87 self.genCode(fn.body) | |
| 272 | 88 self.emit(ir.Move(f.return_value, ir.Const(0))) |
| 269 | 89 self.emit(ir.Jump(f.epiloog)) |
| 268 | 90 self.setFunction(None) |
| 158 | 91 |
| 217 | 92 def genCode(self, code): |
| 308 | 93 """ Wrapper around gen_stmt to catch errors """ |
| 307 | 94 try: |
| 308 | 95 self.gen_stmt(code) |
| 307 | 96 except SemanticError as e: |
| 97 self.error(e.msg, e.loc) | |
| 98 | |
| 308 | 99 def gen_stmt(self, code): |
| 100 """ Generate code for a statement """ | |
| 101 assert isinstance(code, ast.Statement) | |
| 268 | 102 self.setLoc(code.loc) |
| 308 | 103 if type(code) is ast.Compound: |
| 221 | 104 for s in code.statements: |
| 105 self.genCode(s) | |
| 308 | 106 elif type(code) is ast.Empty: |
| 306 | 107 pass |
| 308 | 108 elif type(code) is ast.Assignment: |
| 268 | 109 lval = self.genExprCode(code.lval) |
| 307 | 110 rval = self.genExprCode(code.rval) |
| 111 if not self.equalTypes(code.lval.typ, code.rval.typ): | |
| 315 | 112 msg = 'Cannot assign {} to {}'.format(code.rval.typ, code.lval.typ) |
| 307 | 113 raise SemanticError(msg, code.loc) |
| 114 if not code.lval.lvalue: | |
| 115 raise SemanticError('No valid lvalue {}'.format(code.lval), code.lval.loc) | |
| 268 | 116 self.emit(ir.Move(lval, rval)) |
| 308 | 117 elif type(code) is ast.ExpressionStatement: |
| 275 | 118 self.emit(ir.Exp(self.genExprCode(code.ex))) |
| 308 | 119 elif type(code) is ast.If: |
| 268 | 120 bbtrue = self.newBlock() |
| 121 bbfalse = self.newBlock() | |
| 122 te = self.newBlock() | |
| 308 | 123 self.gen_cond_code(code.condition, bbtrue, bbfalse) |
| 268 | 124 self.setBlock(bbtrue) |
| 125 self.genCode(code.truestatement) | |
| 126 self.emit(ir.Jump(te)) | |
| 127 self.setBlock(bbfalse) | |
| 306 | 128 self.genCode(code.falsestatement) |
| 268 | 129 self.emit(ir.Jump(te)) |
| 130 self.setBlock(te) | |
| 308 | 131 elif type(code) is ast.Return: |
| 303 | 132 re = self.genExprCode(code.expr) |
| 133 self.emit(ir.Move(self.fn.return_value, re)) | |
| 134 self.emit(ir.Jump(self.fn.epiloog)) | |
| 135 b = self.newBlock() | |
| 136 self.setBlock(b) | |
| 308 | 137 elif type(code) is ast.While: |
| 268 | 138 bbdo = self.newBlock() |
| 139 bbtest = self.newBlock() | |
| 140 te = self.newBlock() | |
| 141 self.emit(ir.Jump(bbtest)) | |
| 142 self.setBlock(bbtest) | |
| 308 | 143 self.gen_cond_code(code.condition, bbdo, te) |
| 268 | 144 self.setBlock(bbdo) |
| 228 | 145 self.genCode(code.statement) |
| 268 | 146 self.emit(ir.Jump(bbtest)) |
| 147 self.setBlock(te) | |
| 315 | 148 elif type(code) is ast.For: |
| 149 bbdo = self.newBlock() | |
| 150 bbtest = self.newBlock() | |
| 151 te = self.newBlock() | |
| 152 self.genCode(code.init) | |
| 153 self.emit(ir.Jump(bbtest)) | |
| 154 self.setBlock(bbtest) | |
| 155 self.gen_cond_code(code.condition, bbdo, te) | |
| 156 self.setBlock(bbdo) | |
| 157 self.genCode(code.statement) | |
| 158 self.emit(ir.Jump(bbtest)) | |
| 159 self.setBlock(te) | |
| 222 | 160 else: |
| 268 | 161 raise NotImplementedError('Unknown stmt {}'.format(code)) |
| 230 | 162 |
| 308 | 163 def gen_cond_code(self, expr, bbtrue, bbfalse): |
| 164 """ Generate conditional logic. | |
| 165 Implement sequential logical operators. """ | |
| 166 if type(expr) is ast.Binop: | |
| 268 | 167 if expr.op == 'or': |
| 168 l2 = self.newBlock() | |
| 308 | 169 self.gen_cond_code(expr.a, bbtrue, l2) |
| 170 if not self.equalTypes(expr.a.typ, self.boolType): | |
| 307 | 171 raise SemanticError('Must be boolean', expr.a.loc) |
| 268 | 172 self.setBlock(l2) |
| 308 | 173 self.gen_cond_code(expr.b, bbtrue, bbfalse) |
| 174 if not self.equalTypes(expr.b.typ, self.boolType): | |
| 307 | 175 raise SemanticError('Must be boolean', expr.b.loc) |
| 268 | 176 elif expr.op == 'and': |
| 177 l2 = self.newBlock() | |
| 308 | 178 self.gen_cond_code(expr.a, l2, bbfalse) |
| 179 if not self.equalTypes(expr.a.typ, self.boolType): | |
| 307 | 180 self.error('Must be boolean', expr.a.loc) |
| 268 | 181 self.setBlock(l2) |
| 308 | 182 self.gen_cond_code(expr.b, bbtrue, bbfalse) |
| 183 if not self.equalTypes(expr.b.typ, self.boolType): | |
| 307 | 184 raise SemanticError('Must be boolean', expr.b.loc) |
| 305 | 185 elif expr.op in ['==', '>', '<', '!=', '<=', '>=']: |
| 228 | 186 ta = self.genExprCode(expr.a) |
| 187 tb = self.genExprCode(expr.b) | |
| 307 | 188 if not self.equalTypes(expr.a.typ, expr.b.typ): |
| 189 raise SemanticError('Types unequal {} != {}' | |
| 190 .format(expr.a.typ, expr.b.typ), expr.loc) | |
| 268 | 191 self.emit(ir.CJump(ta, expr.op, tb, bbtrue, bbfalse)) |
| 192 else: | |
| 311 | 193 raise SemanticError('non-bool: {}'.format(expr.op), expr.loc) |
| 307 | 194 expr.typ = self.boolType |
| 308 | 195 elif type(expr) is ast.Literal: |
| 196 self.genExprCode(expr) | |
| 288 | 197 if expr.val: |
| 268 | 198 self.emit(ir.Jump(bbtrue)) |
| 288 | 199 else: |
| 268 | 200 self.emit(ir.Jump(bbfalse)) |
| 228 | 201 else: |
| 288 | 202 raise NotImplementedError('Unknown cond {}'.format(expr)) |
| 307 | 203 if not self.equalTypes(expr.typ, self.boolType): |
| 204 self.error('Condition must be boolean', expr.loc) | |
| 230 | 205 |
| 217 | 206 def genExprCode(self, expr): |
| 308 | 207 """ Generate code for an expression. Return the generated ir-value """ |
| 208 assert isinstance(expr, ast.Expression) | |
| 209 if type(expr) is ast.Binop: | |
| 307 | 210 expr.lvalue = False |
| 211 if expr.op in ['+', '-', '*', '/', '<<', '>>', '|', '&']: | |
| 212 ra = self.genExprCode(expr.a) | |
| 213 rb = self.genExprCode(expr.b) | |
| 214 if self.equalTypes(expr.a.typ, self.intType) and \ | |
| 215 self.equalTypes(expr.b.typ, self.intType): | |
| 216 expr.typ = expr.a.typ | |
| 217 else: | |
| 218 raise SemanticError('Can only add integers', expr.loc) | |
| 219 else: | |
| 220 raise NotImplementedError("Cannot use equality as expressions") | |
| 268 | 221 return ir.Binop(ra, expr.op, rb) |
| 308 | 222 elif type(expr) is ast.Unop: |
| 307 | 223 if expr.op == '&': |
| 224 ra = self.genExprCode(expr.a) | |
| 308 | 225 expr.typ = ast.PointerType(expr.a.typ) |
| 307 | 226 if not expr.a.lvalue: |
| 227 raise SemanticError('No valid lvalue', expr.a.loc) | |
| 228 expr.lvalue = False | |
| 229 assert type(ra) is ir.Mem | |
| 230 return ra.e | |
| 231 else: | |
| 232 raise NotImplementedError('Unknown unop {0}'.format(expr.op)) | |
| 308 | 233 elif type(expr) is ast.Identifier: |
| 307 | 234 # Generate code for this identifier. |
| 235 tg = self.resolveSymbol(expr) | |
| 236 expr.kind = type(tg) | |
| 237 expr.typ = tg.typ | |
| 279 | 238 # This returns the dereferenced variable. |
| 308 | 239 if isinstance(tg, ast.Variable): |
| 313 | 240 expr.lvalue = True |
| 307 | 241 return ir.Mem(self.varMap[tg]) |
| 313 | 242 elif isinstance(tg, ast.Constant): |
| 243 c_val = self.genExprCode(tg.value) | |
| 244 return self.evalConst(c_val) | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
245 else: |
| 308 | 246 raise NotImplementedError(str(tg)) |
| 247 elif type(expr) is ast.Deref: | |
| 222 | 248 # dereference pointer type: |
| 225 | 249 addr = self.genExprCode(expr.ptr) |
| 316 | 250 ptr_typ = self.the_type(expr.ptr.typ) |
| 307 | 251 expr.lvalue = True |
| 308 | 252 if type(ptr_typ) is ast.PointerType: |
| 307 | 253 expr.typ = ptr_typ.ptype |
| 254 return ir.Mem(addr) | |
| 255 else: | |
| 256 raise SemanticError('Cannot deref non-pointer', expr.loc) | |
| 308 | 257 elif type(expr) is ast.Member: |
| 279 | 258 base = self.genExprCode(expr.base) |
| 307 | 259 expr.lvalue = expr.base.lvalue |
| 316 | 260 basetype = self.the_type(expr.base.typ) |
| 308 | 261 if type(basetype) is ast.StructureType: |
| 307 | 262 if basetype.hasField(expr.field): |
| 263 expr.typ = basetype.fieldType(expr.field) | |
| 264 else: | |
| 265 raise SemanticError('{} does not contain field {}' | |
| 308 | 266 .format(basetype, expr.field), expr.loc) |
| 307 | 267 else: |
| 308 | 268 raise SemanticError('Cannot select {} of non-structure type {}' |
| 269 .format(expr.field, basetype), expr.loc) | |
| 307 | 270 |
| 279 | 271 assert type(base) is ir.Mem, type(base) |
| 316 | 272 bt = self.the_type(expr.base.typ) |
| 268 | 273 offset = ir.Const(bt.fieldOffset(expr.field)) |
| 308 | 274 return ir.Mem(ir.Add(base.e, offset)) |
| 275 elif type(expr) is ast.Literal: | |
| 307 | 276 expr.lvalue = False |
| 313 | 277 typemap = {int: 'int', float: 'double', bool: 'bool', str:'string'} |
| 307 | 278 if type(expr.val) in typemap: |
| 279 expr.typ = self.pkg.scope[typemap[type(expr.val)]] | |
| 280 else: | |
| 312 | 281 raise SemanticError('Unknown literal type {}'.format(expr.val), expr.loc) |
| 268 | 282 return ir.Const(expr.val) |
| 308 | 283 elif type(expr) is ast.TypeCast: |
| 284 return self.gen_type_cast(expr) | |
| 285 elif type(expr) is ast.FunctionCall: | |
| 286 return self.gen_function_call(expr) | |
| 225 | 287 else: |
| 259 | 288 raise NotImplementedError('Unknown expr {}'.format(expr)) |
| 307 | 289 |
| 308 | 290 def gen_type_cast(self, expr): |
| 291 """ Generate code for type casting """ | |
| 292 ar = self.genExprCode(expr.a) | |
| 316 | 293 from_type = self.the_type(expr.a.typ) |
| 294 to_type = self.the_type(expr.to_type) | |
| 308 | 295 if isinstance(from_type, ast.PointerType) and isinstance(to_type, ast.PointerType): |
| 296 expr.typ = expr.to_type | |
| 297 return ar | |
| 298 elif type(from_type) is ast.BaseType and from_type.name == 'int' and \ | |
| 299 isinstance(to_type, ast.PointerType): | |
| 300 expr.typ = expr.to_type | |
| 301 return ar | |
| 302 else: | |
| 303 raise SemanticError('Cannot cast {} to {}' | |
| 304 .format(from_type, to_type), expr.loc) | |
| 305 | |
| 306 def gen_function_call(self, expr): | |
| 307 """ Generate code for a function call """ | |
| 308 # Evaluate the arguments: | |
| 309 args = [self.genExprCode(e) for e in expr.args] | |
| 310 # Check arguments: | |
| 311 tg = self.resolveSymbol(expr.proc) | |
| 312 if type(tg) is not ast.Function: | |
| 313 raise SemanticError('cannot call {}'.format(tg)) | |
| 314 ftyp = tg.typ | |
| 315 fname = tg.name | |
| 316 ptypes = ftyp.parametertypes | |
| 317 if len(expr.args) != len(ptypes): | |
| 318 raise SemanticError('{} requires {} arguments, {} given' | |
| 319 .format(fname, len(ptypes), len(expr.args)), expr.loc) | |
| 320 for arg, at in zip(expr.args, ptypes): | |
| 321 if not self.equalTypes(arg.typ, at): | |
| 322 raise SemanticError('Got {}, expected {}' | |
| 323 .format(arg.typ, at), arg.loc) | |
| 324 # determine return type: | |
| 325 expr.typ = ftyp.returntype | |
| 326 return ir.Call(fname, args) | |
| 327 | |
| 313 | 328 def evalConst(self, c): |
| 329 if isinstance(c, ir.Const): | |
| 330 return c | |
| 331 else: | |
| 332 raise SemanticError('Cannot evaluate constant {}'.format(c)) | |
| 333 | |
| 307 | 334 def resolveSymbol(self, sym): |
| 308 | 335 if type(sym) is ast.Member: |
| 307 | 336 base = self.resolveSymbol(sym.base) |
| 308 | 337 if type(base) is not ast.Package: |
| 338 raise SemanticError('Base is not a package', sym.loc) | |
| 307 | 339 scope = base.innerScope |
| 340 name = sym.field | |
| 308 | 341 elif type(sym) is ast.Identifier: |
| 307 | 342 scope = sym.scope |
| 343 name = sym.target | |
| 344 else: | |
| 345 raise NotImplementedError(str(sym)) | |
| 346 if name in scope: | |
| 347 s = scope[name] | |
| 348 else: | |
| 349 raise SemanticError('{} undefined'.format(name), sym.loc) | |
| 308 | 350 assert isinstance(s, ast.Symbol) |
| 307 | 351 return s |
| 352 | |
| 316 | 353 def size_of(self, t): |
| 354 """ Determine the byte size of a type """ | |
| 355 t = self.the_type(t) | |
| 356 if type(t) is ast.BaseType: | |
| 357 return t.bytesize | |
| 358 elif type(t) is ast.StructureType: | |
| 359 return sum(self.size_of(mem.typ) for mem in t.mems) | |
| 360 else: | |
| 361 raise NotImplementedError(str(t)) | |
| 362 | |
| 363 def the_type(self, t): | |
| 307 | 364 """ Recurse until a 'real' type is found """ |
| 308 | 365 if type(t) is ast.DefinedType: |
| 316 | 366 t = self.the_type(t.typ) |
| 308 | 367 elif type(t) in [ast.Identifier, ast.Member]: |
| 316 | 368 t = self.the_type(self.resolveSymbol(t)) |
| 369 elif type(t) is ast.StructureType: | |
| 370 # Setup offsets of fields. Is this the right place?: | |
| 371 offset = 0 | |
| 372 for mem in t.mems: | |
| 373 mem.offset = offset | |
| 374 offset = offset + self.size_of(mem.typ) | |
| 308 | 375 elif isinstance(t, ast.Type): |
| 307 | 376 pass |
| 377 else: | |
| 378 raise NotImplementedError(str(t)) | |
| 308 | 379 assert isinstance(t, ast.Type) |
| 307 | 380 return t |
| 381 | |
| 382 def equalTypes(self, a, b): | |
| 383 """ Compare types a and b for structural equavalence. """ | |
| 384 # Recurse into named types: | |
| 316 | 385 a = self.the_type(a) |
| 386 b = self.the_type(b) | |
| 307 | 387 |
| 388 if type(a) is type(b): | |
| 308 | 389 if type(a) is ast.BaseType: |
| 307 | 390 return a.name == b.name |
| 308 | 391 elif type(a) is ast.PointerType: |
| 307 | 392 return self.equalTypes(a.ptype, b.ptype) |
| 308 | 393 elif type(a) is ast.StructureType: |
| 307 | 394 if len(a.mems) != len(b.mems): |
| 395 return False | |
| 396 return all(self.equalTypes(am.typ, bm.typ) for am, bm in | |
| 397 zip(a.mems, b.mems)) | |
| 398 else: | |
| 399 raise NotImplementedError('{} not implemented'.format(type(a))) | |
| 400 return False |