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