Mercurial > lcfOS
annotate python/ppci/c3/codegenerator.py @ 308:2e7f55319858
Merged analyse into codegenerator
author | Windel Bouwman |
---|---|
date | Fri, 13 Dec 2013 11:53:29 +0100 |
parents | e609d5296ee9 |
children | ff665880a6b0 |
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'] | |
255 | 37 self.logger.info('Generating ir-code for {}'.format(pkg.name)) |
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) | |
308 | 51 return self.m |
52 | |
53 def error(self, msg, loc=None): | |
54 self.pkg.ok = False | |
55 self.diag.error(msg, loc) | |
307 | 56 |
57 def checkType(self, t): | |
58 """ Verify the type is correct """ | |
59 t = self.theType(t) | |
174 | 60 |
308 | 61 def gen_function(self, fn): |
268 | 62 # TODO: handle arguments |
63 f = self.funcMap[fn] | |
272 | 64 f.return_value = self.newTemp() |
268 | 65 self.setFunction(f) |
269 | 66 l2 = self.newBlock() |
67 self.emit(ir.Jump(l2)) | |
68 self.setBlock(l2) | |
268 | 69 # generate room for locals: |
174 | 70 |
268 | 71 for sym in fn.innerScope: |
72 # TODO: handle parameters different | |
272 | 73 if sym.isParameter: |
307 | 74 self.checkType(sym.typ) |
308 | 75 variable = ir.Parameter(sym.name) |
76 f.addParameter(variable) | |
274 | 77 elif sym.isLocal: |
307 | 78 self.checkType(sym.typ) |
308 | 79 variable = ir.LocalVariable(sym.name) |
80 f.addLocal(variable) | |
81 elif isinstance(sym, ast.Variable): | |
307 | 82 self.checkType(sym.typ) |
308 | 83 variable = ir.LocalVariable(sym.name) |
84 f.addLocal(variable) | |
274 | 85 else: |
275 | 86 raise NotImplementedError('{}'.format(sym)) |
308 | 87 self.varMap[sym] = variable |
268 | 88 |
89 self.genCode(fn.body) | |
272 | 90 self.emit(ir.Move(f.return_value, ir.Const(0))) |
269 | 91 self.emit(ir.Jump(f.epiloog)) |
268 | 92 self.setFunction(None) |
158 | 93 |
217 | 94 def genCode(self, code): |
308 | 95 """ Wrapper around gen_stmt to catch errors """ |
307 | 96 try: |
308 | 97 self.gen_stmt(code) |
307 | 98 except SemanticError as e: |
99 self.error(e.msg, e.loc) | |
100 | |
308 | 101 def gen_stmt(self, code): |
102 """ Generate code for a statement """ | |
103 assert isinstance(code, ast.Statement) | |
268 | 104 self.setLoc(code.loc) |
308 | 105 if type(code) is ast.Compound: |
221 | 106 for s in code.statements: |
107 self.genCode(s) | |
308 | 108 elif type(code) is ast.Empty: |
306 | 109 pass |
308 | 110 elif type(code) is ast.Assignment: |
268 | 111 lval = self.genExprCode(code.lval) |
307 | 112 rval = self.genExprCode(code.rval) |
113 if not self.equalTypes(code.lval.typ, code.rval.typ): | |
114 msg = 'Cannot assign {} to {}'.format(code.lval.typ, code.rval.typ) | |
115 raise SemanticError(msg, code.loc) | |
116 if not code.lval.lvalue: | |
117 raise SemanticError('No valid lvalue {}'.format(code.lval), code.lval.loc) | |
268 | 118 self.emit(ir.Move(lval, rval)) |
308 | 119 elif type(code) is ast.ExpressionStatement: |
275 | 120 self.emit(ir.Exp(self.genExprCode(code.ex))) |
308 | 121 elif type(code) is ast.If: |
268 | 122 bbtrue = self.newBlock() |
123 bbfalse = self.newBlock() | |
124 te = self.newBlock() | |
308 | 125 self.gen_cond_code(code.condition, bbtrue, bbfalse) |
268 | 126 self.setBlock(bbtrue) |
127 self.genCode(code.truestatement) | |
128 self.emit(ir.Jump(te)) | |
129 self.setBlock(bbfalse) | |
306 | 130 self.genCode(code.falsestatement) |
268 | 131 self.emit(ir.Jump(te)) |
132 self.setBlock(te) | |
308 | 133 elif type(code) is ast.Return: |
303 | 134 re = self.genExprCode(code.expr) |
135 self.emit(ir.Move(self.fn.return_value, re)) | |
136 self.emit(ir.Jump(self.fn.epiloog)) | |
137 b = self.newBlock() | |
138 self.setBlock(b) | |
308 | 139 elif type(code) is ast.While: |
268 | 140 bbdo = self.newBlock() |
141 bbtest = self.newBlock() | |
142 te = self.newBlock() | |
143 self.emit(ir.Jump(bbtest)) | |
144 self.setBlock(bbtest) | |
308 | 145 self.gen_cond_code(code.condition, bbdo, te) |
268 | 146 self.setBlock(bbdo) |
228 | 147 self.genCode(code.statement) |
268 | 148 self.emit(ir.Jump(bbtest)) |
149 self.setBlock(te) | |
222 | 150 else: |
268 | 151 raise NotImplementedError('Unknown stmt {}'.format(code)) |
230 | 152 |
308 | 153 def gen_cond_code(self, expr, bbtrue, bbfalse): |
154 """ Generate conditional logic. | |
155 Implement sequential logical operators. """ | |
156 if type(expr) is ast.Binop: | |
268 | 157 if expr.op == 'or': |
158 l2 = self.newBlock() | |
308 | 159 self.gen_cond_code(expr.a, bbtrue, l2) |
160 if not self.equalTypes(expr.a.typ, self.boolType): | |
307 | 161 raise SemanticError('Must be boolean', expr.a.loc) |
268 | 162 self.setBlock(l2) |
308 | 163 self.gen_cond_code(expr.b, bbtrue, bbfalse) |
164 if not self.equalTypes(expr.b.typ, self.boolType): | |
307 | 165 raise SemanticError('Must be boolean', expr.b.loc) |
268 | 166 elif expr.op == 'and': |
167 l2 = self.newBlock() | |
308 | 168 self.gen_cond_code(expr.a, l2, bbfalse) |
169 if not self.equalTypes(expr.a.typ, self.boolType): | |
307 | 170 self.error('Must be boolean', expr.a.loc) |
268 | 171 self.setBlock(l2) |
308 | 172 self.gen_cond_code(expr.b, bbtrue, bbfalse) |
173 if not self.equalTypes(expr.b.typ, self.boolType): | |
307 | 174 raise SemanticError('Must be boolean', expr.b.loc) |
305 | 175 elif expr.op in ['==', '>', '<', '!=', '<=', '>=']: |
228 | 176 ta = self.genExprCode(expr.a) |
177 tb = self.genExprCode(expr.b) | |
307 | 178 if not self.equalTypes(expr.a.typ, expr.b.typ): |
179 raise SemanticError('Types unequal {} != {}' | |
180 .format(expr.a.typ, expr.b.typ), expr.loc) | |
268 | 181 self.emit(ir.CJump(ta, expr.op, tb, bbtrue, bbfalse)) |
182 else: | |
183 raise NotImplementedError('Unknown condition {}'.format(expr)) | |
307 | 184 expr.typ = self.boolType |
308 | 185 elif type(expr) is ast.Literal: |
186 self.genExprCode(expr) | |
288 | 187 if expr.val: |
268 | 188 self.emit(ir.Jump(bbtrue)) |
288 | 189 else: |
268 | 190 self.emit(ir.Jump(bbfalse)) |
228 | 191 else: |
288 | 192 raise NotImplementedError('Unknown cond {}'.format(expr)) |
307 | 193 if not self.equalTypes(expr.typ, self.boolType): |
194 self.error('Condition must be boolean', expr.loc) | |
230 | 195 |
217 | 196 def genExprCode(self, expr): |
308 | 197 """ Generate code for an expression. Return the generated ir-value """ |
198 assert isinstance(expr, ast.Expression) | |
199 if type(expr) is ast.Binop: | |
307 | 200 expr.lvalue = False |
201 if expr.op in ['+', '-', '*', '/', '<<', '>>', '|', '&']: | |
202 ra = self.genExprCode(expr.a) | |
203 rb = self.genExprCode(expr.b) | |
204 if self.equalTypes(expr.a.typ, self.intType) and \ | |
205 self.equalTypes(expr.b.typ, self.intType): | |
206 expr.typ = expr.a.typ | |
207 else: | |
208 raise SemanticError('Can only add integers', expr.loc) | |
209 else: | |
210 raise NotImplementedError("Cannot use equality as expressions") | |
268 | 211 return ir.Binop(ra, expr.op, rb) |
308 | 212 elif type(expr) is ast.Unop: |
307 | 213 if expr.op == '&': |
214 ra = self.genExprCode(expr.a) | |
308 | 215 expr.typ = ast.PointerType(expr.a.typ) |
307 | 216 if not expr.a.lvalue: |
217 raise SemanticError('No valid lvalue', expr.a.loc) | |
218 expr.lvalue = False | |
219 assert type(ra) is ir.Mem | |
220 return ra.e | |
221 else: | |
222 raise NotImplementedError('Unknown unop {0}'.format(expr.op)) | |
308 | 223 elif type(expr) is ast.Identifier: |
307 | 224 # Generate code for this identifier. |
225 expr.lvalue = True | |
226 tg = self.resolveSymbol(expr) | |
227 expr.kind = type(tg) | |
228 expr.typ = tg.typ | |
279 | 229 # This returns the dereferenced variable. |
308 | 230 if isinstance(tg, ast.Variable): |
307 | 231 return ir.Mem(self.varMap[tg]) |
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
232 else: |
308 | 233 raise NotImplementedError(str(tg)) |
234 elif type(expr) is ast.Deref: | |
222 | 235 # dereference pointer type: |
225 | 236 addr = self.genExprCode(expr.ptr) |
307 | 237 ptr_typ = self.theType(expr.ptr.typ) |
238 expr.lvalue = True | |
308 | 239 if type(ptr_typ) is ast.PointerType: |
307 | 240 expr.typ = ptr_typ.ptype |
241 return ir.Mem(addr) | |
242 else: | |
243 raise SemanticError('Cannot deref non-pointer', expr.loc) | |
308 | 244 elif type(expr) is ast.Member: |
279 | 245 base = self.genExprCode(expr.base) |
307 | 246 expr.lvalue = expr.base.lvalue |
247 basetype = self.theType(expr.base.typ) | |
308 | 248 if type(basetype) is ast.StructureType: |
307 | 249 if basetype.hasField(expr.field): |
250 expr.typ = basetype.fieldType(expr.field) | |
251 else: | |
252 raise SemanticError('{} does not contain field {}' | |
308 | 253 .format(basetype, expr.field), expr.loc) |
307 | 254 else: |
308 | 255 raise SemanticError('Cannot select {} of non-structure type {}' |
256 .format(expr.field, basetype), expr.loc) | |
307 | 257 |
279 | 258 assert type(base) is ir.Mem, type(base) |
307 | 259 bt = self.theType(expr.base.typ) |
268 | 260 offset = ir.Const(bt.fieldOffset(expr.field)) |
308 | 261 return ir.Mem(ir.Add(base.e, offset)) |
262 elif type(expr) is ast.Literal: | |
307 | 263 expr.lvalue = False |
264 typemap = {int: 'int', float: 'double', bool: 'bool'} | |
265 if type(expr.val) in typemap: | |
266 expr.typ = self.pkg.scope[typemap[type(expr.val)]] | |
267 else: | |
268 raise SemanticError('Unknown literal type {}'.format(expr.val)) | |
268 | 269 return ir.Const(expr.val) |
308 | 270 elif type(expr) is ast.TypeCast: |
271 return self.gen_type_cast(expr) | |
272 elif type(expr) is ast.FunctionCall: | |
273 return self.gen_function_call(expr) | |
225 | 274 else: |
259 | 275 raise NotImplementedError('Unknown expr {}'.format(expr)) |
307 | 276 |
308 | 277 def gen_type_cast(self, expr): |
278 """ Generate code for type casting """ | |
279 ar = self.genExprCode(expr.a) | |
280 from_type = self.theType(expr.a.typ) | |
281 to_type = self.theType(expr.to_type) | |
282 if isinstance(from_type, ast.PointerType) and isinstance(to_type, ast.PointerType): | |
283 expr.typ = expr.to_type | |
284 return ar | |
285 elif type(from_type) is ast.BaseType and from_type.name == 'int' and \ | |
286 isinstance(to_type, ast.PointerType): | |
287 expr.typ = expr.to_type | |
288 return ar | |
289 else: | |
290 raise SemanticError('Cannot cast {} to {}' | |
291 .format(from_type, to_type), expr.loc) | |
292 | |
293 def gen_function_call(self, expr): | |
294 """ Generate code for a function call """ | |
295 # Evaluate the arguments: | |
296 args = [self.genExprCode(e) for e in expr.args] | |
297 # Check arguments: | |
298 tg = self.resolveSymbol(expr.proc) | |
299 if type(tg) is not ast.Function: | |
300 raise SemanticError('cannot call {}'.format(tg)) | |
301 ftyp = tg.typ | |
302 fname = tg.name | |
303 ptypes = ftyp.parametertypes | |
304 if len(expr.args) != len(ptypes): | |
305 raise SemanticError('{} requires {} arguments, {} given' | |
306 .format(fname, len(ptypes), len(expr.args)), expr.loc) | |
307 for arg, at in zip(expr.args, ptypes): | |
308 if not self.equalTypes(arg.typ, at): | |
309 raise SemanticError('Got {}, expected {}' | |
310 .format(arg.typ, at), arg.loc) | |
311 # determine return type: | |
312 expr.typ = ftyp.returntype | |
313 return ir.Call(fname, args) | |
314 | |
307 | 315 def resolveSymbol(self, sym): |
308 | 316 if type(sym) is ast.Member: |
307 | 317 base = self.resolveSymbol(sym.base) |
308 | 318 if type(base) is not ast.Package: |
319 raise SemanticError('Base is not a package', sym.loc) | |
307 | 320 scope = base.innerScope |
321 name = sym.field | |
308 | 322 elif type(sym) is ast.Identifier: |
307 | 323 scope = sym.scope |
324 name = sym.target | |
325 else: | |
326 raise NotImplementedError(str(sym)) | |
327 if name in scope: | |
328 s = scope[name] | |
329 else: | |
330 raise SemanticError('{} undefined'.format(name), sym.loc) | |
308 | 331 assert isinstance(s, ast.Symbol) |
307 | 332 return s |
333 | |
334 def theType(self, t): | |
335 """ Recurse until a 'real' type is found """ | |
308 | 336 if type(t) is ast.DefinedType: |
307 | 337 t = self.theType(t.typ) |
308 | 338 elif type(t) in [ast.Identifier, ast.Member]: |
307 | 339 t = self.theType(self.resolveSymbol(t)) |
308 | 340 elif isinstance(t, ast.Type): |
307 | 341 pass |
342 else: | |
343 raise NotImplementedError(str(t)) | |
308 | 344 assert isinstance(t, ast.Type) |
307 | 345 return t |
346 | |
347 def equalTypes(self, a, b): | |
348 """ Compare types a and b for structural equavalence. """ | |
349 # Recurse into named types: | |
350 a = self.theType(a) | |
351 b = self.theType(b) | |
308 | 352 assert isinstance(a, ast.Type) |
353 assert isinstance(b, ast.Type) | |
307 | 354 |
355 if type(a) is type(b): | |
308 | 356 if type(a) is ast.BaseType: |
307 | 357 return a.name == b.name |
308 | 358 elif type(a) is ast.PointerType: |
307 | 359 return self.equalTypes(a.ptype, b.ptype) |
308 | 360 elif type(a) is ast.StructureType: |
307 | 361 if len(a.mems) != len(b.mems): |
362 return False | |
363 return all(self.equalTypes(am.typ, bm.typ) for am, bm in | |
364 zip(a.mems, b.mems)) | |
365 else: | |
366 raise NotImplementedError('{} not implemented'.format(type(a))) | |
367 return False |