Mercurial > lcfOS
annotate python/ppci/c3/codegenerator.py @ 395:3b0c495e3008
Speed improvements
| author | Windel Bouwman |
|---|---|
| date | Fri, 23 May 2014 14:28:03 +0200 |
| parents | 988f3fb861e4 |
| children |
| rev | line source |
|---|---|
| 255 | 1 import logging |
| 354 | 2 import struct |
| 301 | 3 from .. import ir |
| 307 | 4 from .. import irutils |
| 308 | 5 from . import astnodes as ast |
| 230 | 6 |
| 228 | 7 |
| 307 | 8 class SemanticError(Exception): |
| 308 | 9 """ Error thrown when a semantic issue is observed """ |
| 307 | 10 def __init__(self, msg, loc): |
| 308 | 11 super().__init__() |
| 307 | 12 self.msg = msg |
| 13 self.loc = loc | |
| 14 | |
| 15 | |
| 394 | 16 class CodeGenerator: |
| 288 | 17 """ |
| 274 | 18 Generates intermediate (IR) code from a package. The entry function is |
| 19 'genModule'. The main task of this part is to rewrite complex control | |
| 20 structures, such as while and for loops into simple conditional | |
| 21 jump statements. Also complex conditional statements are simplified. | |
| 22 Such as 'and' and 'or' statements are rewritten in conditional jumps. | |
| 23 And structured datatypes are rewritten. | |
| 307 | 24 |
| 25 Type checking is done in one run with code generation. | |
| 274 | 26 """ |
| 307 | 27 def __init__(self, diag): |
| 261 | 28 self.logger = logging.getLogger('c3cgen') |
| 394 | 29 self.builder = irutils.Builder() |
| 307 | 30 self.diag = diag |
| 261 | 31 |
| 217 | 32 def gencode(self, pkg): |
| 308 | 33 """ Generate code for a single module """ |
| 394 | 34 self.builder.prepare() |
| 308 | 35 assert type(pkg) is ast.Package |
| 307 | 36 self.pkg = pkg |
| 37 self.intType = pkg.scope['int'] | |
| 38 self.boolType = pkg.scope['bool'] | |
| 389 | 39 self.pointerSize = 4 |
| 40 self.logger.debug('Generating ir-code for {}'.format(pkg.name), | |
| 41 extra={'c3_ast': pkg}) | |
| 288 | 42 self.varMap = {} # Maps variables to storage locations. |
| 394 | 43 self.builder.m = ir.Module(pkg.name) |
| 307 | 44 try: |
| 389 | 45 for typ in pkg.Types: |
| 46 self.check_type(typ) | |
| 362 | 47 # Only generate function if function contains a body: |
| 389 | 48 real_functions = list(filter( |
| 394 | 49 lambda f: f.body, pkg.Functions)) |
| 307 | 50 for v in pkg.innerScope.Variables: |
| 394 | 51 v2 = ir.GlobalVariable(v.name, ir.i32) |
| 364 | 52 self.varMap[v] = v2 |
| 363 | 53 if not v.isLocal: |
| 394 | 54 self.builder.m.add_variable(v2) |
| 362 | 55 for s in real_functions: |
| 308 | 56 self.gen_function(s) |
| 307 | 57 except SemanticError as e: |
| 58 self.error(e.msg, e.loc) | |
| 313 | 59 if self.pkg.ok: |
| 394 | 60 return self.builder.m |
| 308 | 61 |
| 62 def error(self, msg, loc=None): | |
| 63 self.pkg.ok = False | |
| 64 self.diag.error(msg, loc) | |
| 307 | 65 |
| 308 | 66 def gen_function(self, fn): |
| 268 | 67 # TODO: handle arguments |
| 394 | 68 f = self.builder.new_function(fn.name) |
| 69 f.return_value = self.builder.newTemp() | |
| 70 self.builder.setFunction(f) | |
| 71 l2 = self.builder.newBlock() | |
| 72 self.builder.emit(ir.Jump(l2)) | |
| 73 self.builder.setBlock(l2) | |
| 268 | 74 # generate room for locals: |
| 174 | 75 |
| 268 | 76 for sym in fn.innerScope: |
| 389 | 77 self.check_type(sym.typ) |
| 272 | 78 if sym.isParameter: |
| 394 | 79 p = ir.Parameter(sym.name, ir.i32) |
| 80 variable = ir.LocalVariable(sym.name + '_copy', ir.i32) | |
| 316 | 81 f.addParameter(p) |
| 82 f.addLocal(variable) | |
| 83 # Move parameter into local copy: | |
| 394 | 84 self.builder.emit(ir.Move(ir.Mem(variable), p)) |
| 274 | 85 elif sym.isLocal: |
| 394 | 86 variable = ir.LocalVariable(sym.name, ir.i32) |
| 308 | 87 f.addLocal(variable) |
| 88 elif isinstance(sym, ast.Variable): | |
| 394 | 89 variable = ir.LocalVariable(sym.name, ir.i32) |
| 308 | 90 f.addLocal(variable) |
| 274 | 91 else: |
| 275 | 92 raise NotImplementedError('{}'.format(sym)) |
| 308 | 93 self.varMap[sym] = variable |
| 268 | 94 |
| 394 | 95 self.gen_stmt(fn.body) |
| 96 self.builder.emit(ir.Move(f.return_value, ir.Const(0))) | |
| 97 self.builder.emit(ir.Jump(f.epiloog)) | |
| 98 self.builder.setFunction(None) | |
| 307 | 99 |
| 308 | 100 def gen_stmt(self, code): |
| 101 """ Generate code for a statement """ | |
| 394 | 102 try: |
| 103 assert isinstance(code, ast.Statement) | |
| 104 self.builder.setLoc(code.loc) | |
| 105 if type(code) is ast.Compound: | |
| 106 for s in code.statements: | |
| 107 self.gen_stmt(s) | |
| 108 elif type(code) is ast.Empty: | |
| 109 pass | |
| 110 elif type(code) is ast.Assignment: | |
| 111 self.gen_assignment_stmt(code) | |
| 112 elif type(code) is ast.ExpressionStatement: | |
| 113 self.builder.emit(ir.Exp(self.gen_expr_code(code.ex))) | |
| 114 elif type(code) is ast.If: | |
| 115 self.gen_if_stmt(code) | |
| 116 elif type(code) is ast.Return: | |
| 117 re = self.gen_expr_code(code.expr) | |
| 118 self.builder.emit(ir.Move(self.builder.fn.return_value, re)) | |
| 119 self.builder.emit(ir.Jump(self.builder.fn.epiloog)) | |
| 120 b = self.builder.newBlock() | |
| 121 self.builder.setBlock(b) | |
| 122 elif type(code) is ast.While: | |
| 123 self.gen_while(code) | |
| 124 elif type(code) is ast.For: | |
| 125 self.gen_for_stmt(code) | |
| 126 elif type(code) is ast.Switch: | |
| 127 raise NotImplementedError('Unknown stmt {}'.format(code)) | |
| 128 else: | |
| 129 raise NotImplementedError('Unknown stmt {}'.format(code)) | |
| 130 except SemanticError as e: | |
| 131 self.error(e.msg, e.loc) | |
| 132 | |
| 133 def gen_assignment_stmt(self, code): | |
| 134 """ Generate code for assignment statement """ | |
| 135 lval = self.gen_expr_code(code.lval) | |
| 136 rval = self.gen_expr_code(code.rval) | |
| 137 if not self.equal_types(code.lval.typ, code.rval.typ): | |
| 138 raise SemanticError('Cannot assign {} to {}' | |
| 139 .format(code.rval.typ, code.lval.typ), | |
| 140 code.loc) | |
| 141 if not code.lval.lvalue: | |
| 142 raise SemanticError('No valid lvalue {}'.format(code.lval), | |
| 143 code.lval.loc) | |
| 144 self.builder.emit(ir.Move(lval, rval)) | |
| 145 | |
| 146 def gen_if_stmt(self, code): | |
| 147 """ Generate code for if statement """ | |
| 148 true_block = self.builder.newBlock() | |
| 149 bbfalse = self.builder.newBlock() | |
| 150 te = self.builder.newBlock() | |
| 151 self.gen_cond_code(code.condition, true_block, bbfalse) | |
| 152 self.builder.setBlock(true_block) | |
| 153 self.gen_stmt(code.truestatement) | |
| 154 self.builder.emit(ir.Jump(te)) | |
| 155 self.builder.setBlock(bbfalse) | |
| 156 self.gen_stmt(code.falsestatement) | |
| 157 self.builder.emit(ir.Jump(te)) | |
| 158 self.builder.setBlock(te) | |
| 159 | |
| 160 def gen_while(self, code): | |
| 161 """ Generate code for while statement """ | |
| 162 bbdo = self.builder.newBlock() | |
| 163 test_block = self.builder.newBlock() | |
| 164 final_block = self.builder.newBlock() | |
| 165 self.builder.emit(ir.Jump(test_block)) | |
| 166 self.builder.setBlock(test_block) | |
| 167 self.gen_cond_code(code.condition, bbdo, final_block) | |
| 168 self.builder.setBlock(bbdo) | |
| 169 self.gen_stmt(code.statement) | |
| 170 self.builder.emit(ir.Jump(test_block)) | |
| 171 self.builder.setBlock(final_block) | |
| 172 | |
| 173 def gen_for_stmt(self, code): | |
| 174 """ Generate for statement code """ | |
| 175 bbdo = self.builder.newBlock() | |
| 176 test_block = self.builder.newBlock() | |
| 177 final_block = self.builder.newBlock() | |
| 178 self.gen_stmt(code.init) | |
| 179 self.builder.emit(ir.Jump(test_block)) | |
| 180 self.builder.setBlock(test_block) | |
| 181 self.gen_cond_code(code.condition, bbdo, final_block) | |
| 182 self.builder.setBlock(bbdo) | |
| 183 self.gen_stmt(code.statement) | |
| 184 self.gen_stmt(code.final) | |
| 185 self.builder.emit(ir.Jump(test_block)) | |
| 186 self.builder.setBlock(final_block) | |
| 230 | 187 |
| 308 | 188 def gen_cond_code(self, expr, bbtrue, bbfalse): |
| 189 """ Generate conditional logic. | |
| 190 Implement sequential logical operators. """ | |
| 191 if type(expr) is ast.Binop: | |
| 268 | 192 if expr.op == 'or': |
| 394 | 193 l2 = self.builder.newBlock() |
| 308 | 194 self.gen_cond_code(expr.a, bbtrue, l2) |
| 389 | 195 if not self.equal_types(expr.a.typ, self.boolType): |
| 307 | 196 raise SemanticError('Must be boolean', expr.a.loc) |
| 394 | 197 self.builder.setBlock(l2) |
| 308 | 198 self.gen_cond_code(expr.b, bbtrue, bbfalse) |
| 389 | 199 if not self.equal_types(expr.b.typ, self.boolType): |
| 307 | 200 raise SemanticError('Must be boolean', expr.b.loc) |
| 268 | 201 elif expr.op == 'and': |
| 394 | 202 l2 = self.builder.newBlock() |
| 308 | 203 self.gen_cond_code(expr.a, l2, bbfalse) |
| 389 | 204 if not self.equal_types(expr.a.typ, self.boolType): |
| 307 | 205 self.error('Must be boolean', expr.a.loc) |
| 394 | 206 self.builder.setBlock(l2) |
| 308 | 207 self.gen_cond_code(expr.b, bbtrue, bbfalse) |
| 389 | 208 if not self.equal_types(expr.b.typ, self.boolType): |
| 307 | 209 raise SemanticError('Must be boolean', expr.b.loc) |
| 305 | 210 elif expr.op in ['==', '>', '<', '!=', '<=', '>=']: |
| 393 | 211 ta = self.gen_expr_code(expr.a) |
| 212 tb = self.gen_expr_code(expr.b) | |
| 389 | 213 if not self.equal_types(expr.a.typ, expr.b.typ): |
| 307 | 214 raise SemanticError('Types unequal {} != {}' |
| 389 | 215 .format(expr.a.typ, expr.b.typ), |
| 216 expr.loc) | |
| 394 | 217 self.builder.emit(ir.CJump(ta, expr.op, tb, bbtrue, bbfalse)) |
| 268 | 218 else: |
| 311 | 219 raise SemanticError('non-bool: {}'.format(expr.op), expr.loc) |
| 307 | 220 expr.typ = self.boolType |
| 308 | 221 elif type(expr) is ast.Literal: |
| 393 | 222 self.gen_expr_code(expr) |
| 288 | 223 if expr.val: |
| 394 | 224 self.builder.emit(ir.Jump(bbtrue)) |
| 288 | 225 else: |
| 394 | 226 self.builder.emit(ir.Jump(bbfalse)) |
| 228 | 227 else: |
| 288 | 228 raise NotImplementedError('Unknown cond {}'.format(expr)) |
| 354 | 229 |
| 230 # Check that the condition is a boolean value: | |
| 389 | 231 if not self.equal_types(expr.typ, self.boolType): |
| 307 | 232 self.error('Condition must be boolean', expr.loc) |
| 230 | 233 |
| 393 | 234 def gen_expr_code(self, expr): |
| 308 | 235 """ Generate code for an expression. Return the generated ir-value """ |
| 236 assert isinstance(expr, ast.Expression) | |
| 237 if type(expr) is ast.Binop: | |
| 307 | 238 expr.lvalue = False |
| 239 if expr.op in ['+', '-', '*', '/', '<<', '>>', '|', '&']: | |
| 393 | 240 ra = self.gen_expr_code(expr.a) |
| 241 rb = self.gen_expr_code(expr.b) | |
| 389 | 242 if self.equal_types(expr.a.typ, self.intType) and \ |
| 243 self.equal_types(expr.b.typ, self.intType): | |
| 307 | 244 expr.typ = expr.a.typ |
| 393 | 245 elif self.equal_types(expr.b.typ, self.intType) and \ |
| 246 type(expr.a.typ) is ast.PointerType: | |
| 247 # Special case for pointer arithmatic TODO: coerce! | |
| 248 expr.typ = expr.a.typ | |
| 307 | 249 else: |
| 250 raise SemanticError('Can only add integers', expr.loc) | |
| 251 else: | |
| 252 raise NotImplementedError("Cannot use equality as expressions") | |
| 394 | 253 return ir.Binop(ra, expr.op, rb, "op", ir.i32) |
| 308 | 254 elif type(expr) is ast.Unop: |
| 307 | 255 if expr.op == '&': |
| 393 | 256 ra = self.gen_expr_code(expr.a) |
| 308 | 257 expr.typ = ast.PointerType(expr.a.typ) |
| 307 | 258 if not expr.a.lvalue: |
| 259 raise SemanticError('No valid lvalue', expr.a.loc) | |
| 260 expr.lvalue = False | |
| 261 assert type(ra) is ir.Mem | |
| 262 return ra.e | |
| 263 else: | |
| 264 raise NotImplementedError('Unknown unop {0}'.format(expr.op)) | |
| 308 | 265 elif type(expr) is ast.Identifier: |
| 307 | 266 # Generate code for this identifier. |
| 267 tg = self.resolveSymbol(expr) | |
| 268 expr.kind = type(tg) | |
| 269 expr.typ = tg.typ | |
| 279 | 270 # This returns the dereferenced variable. |
| 308 | 271 if isinstance(tg, ast.Variable): |
| 313 | 272 expr.lvalue = True |
| 307 | 273 return ir.Mem(self.varMap[tg]) |
| 313 | 274 elif isinstance(tg, ast.Constant): |
| 393 | 275 c_val = self.gen_expr_code(tg.value) |
| 313 | 276 return self.evalConst(c_val) |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
277 else: |
| 308 | 278 raise NotImplementedError(str(tg)) |
| 279 elif type(expr) is ast.Deref: | |
| 222 | 280 # dereference pointer type: |
| 393 | 281 addr = self.gen_expr_code(expr.ptr) |
| 316 | 282 ptr_typ = self.the_type(expr.ptr.typ) |
| 307 | 283 expr.lvalue = True |
| 308 | 284 if type(ptr_typ) is ast.PointerType: |
| 307 | 285 expr.typ = ptr_typ.ptype |
| 286 return ir.Mem(addr) | |
| 287 else: | |
| 288 raise SemanticError('Cannot deref non-pointer', expr.loc) | |
| 308 | 289 elif type(expr) is ast.Member: |
| 394 | 290 return self.gen_member_expr(expr) |
| 354 | 291 elif type(expr) is ast.Index: |
| 394 | 292 return self.gen_index_expr(expr) |
| 308 | 293 elif type(expr) is ast.Literal: |
| 394 | 294 return self.gen_literal_expr(expr) |
| 308 | 295 elif type(expr) is ast.TypeCast: |
| 296 return self.gen_type_cast(expr) | |
| 393 | 297 elif type(expr) is ast.Sizeof: |
| 298 # The type of this expression is int: | |
| 299 expr.typ = self.intType | |
| 300 self.check_type(expr.query_typ) | |
| 301 type_size = self.size_of(expr.query_typ) | |
| 302 return ir.Const(type_size) | |
| 308 | 303 elif type(expr) is ast.FunctionCall: |
| 304 return self.gen_function_call(expr) | |
| 225 | 305 else: |
| 259 | 306 raise NotImplementedError('Unknown expr {}'.format(expr)) |
| 307 | 307 |
| 394 | 308 def gen_member_expr(self, expr): |
| 309 base = self.gen_expr_code(expr.base) | |
| 310 expr.lvalue = expr.base.lvalue | |
| 311 basetype = self.the_type(expr.base.typ) | |
| 312 if type(basetype) is ast.StructureType: | |
| 313 if basetype.hasField(expr.field): | |
| 314 expr.typ = basetype.fieldType(expr.field) | |
| 315 else: | |
| 316 raise SemanticError('{} does not contain field {}' | |
| 317 .format(basetype, expr.field), | |
| 318 expr.loc) | |
| 319 else: | |
| 320 raise SemanticError('Cannot select {} of non-structure type {}' | |
| 321 .format(expr.field, basetype), expr.loc) | |
| 322 | |
| 323 assert type(base) is ir.Mem, type(base) | |
| 324 bt = self.the_type(expr.base.typ) | |
| 325 offset = ir.Const(bt.fieldOffset(expr.field)) | |
| 326 addr = ir.Add(base.e, offset, "mem_addr", ir.i32) | |
| 327 return ir.Mem(addr) | |
| 328 | |
| 329 def gen_index_expr(self, expr): | |
| 330 """ Array indexing """ | |
| 331 base = self.gen_expr_code(expr.base) | |
| 332 idx = self.gen_expr_code(expr.i) | |
| 333 base_typ = self.the_type(expr.base.typ) | |
| 334 if not isinstance(base_typ, ast.ArrayType): | |
| 335 raise SemanticError('Cannot index non-array type {}' | |
| 336 .format(base_typ), | |
| 337 expr.base.loc) | |
| 338 idx_type = self.the_type(expr.i.typ) | |
| 339 if not self.equal_types(idx_type, self.intType): | |
| 340 raise SemanticError('Index must be int not {}' | |
| 341 .format(idx_type), expr.i.loc) | |
| 342 assert type(base) is ir.Mem | |
| 343 element_type = self.the_type(base_typ.element_type) | |
| 344 element_size = self.size_of(element_type) | |
| 345 expr.typ = base_typ.element_type | |
| 346 expr.lvalue = True | |
| 347 | |
| 348 offset = ir.Mul(idx, ir.Const(element_size), "element_offset", ir.i32) | |
| 349 addr = ir.Add(base.e, offset, "element_address", ir.i32) | |
| 350 return ir.Mem(addr) | |
| 351 | |
| 352 def gen_literal_expr(self, expr): | |
| 353 """ Generate code for literal """ | |
| 354 expr.lvalue = False | |
| 355 typemap = {int: 'int', | |
| 356 float: 'double', | |
| 357 bool: 'bool', | |
| 358 str: 'string'} | |
| 359 if type(expr.val) in typemap: | |
| 360 expr.typ = self.pkg.scope[typemap[type(expr.val)]] | |
| 361 else: | |
| 362 raise SemanticError('Unknown literal type {}' | |
| 363 .format(expr.val), expr.loc) | |
| 364 # Construct correct const value: | |
| 365 if type(expr.val) is str: | |
| 366 cval = self.pack_string(expr.val) | |
| 367 return ir.Addr(ir.Const(cval)) | |
| 368 else: | |
| 369 return ir.Const(expr.val) | |
| 370 | |
| 389 | 371 def pack_string(self, txt): |
| 372 """ Pack a string using 4 bytes length followed by text data """ | |
| 373 length = struct.pack('<I', len(txt)) | |
| 374 data = txt.encode('ascii') | |
| 375 return length + data | |
| 376 | |
| 308 | 377 def gen_type_cast(self, expr): |
| 378 """ Generate code for type casting """ | |
| 393 | 379 ar = self.gen_expr_code(expr.a) |
| 316 | 380 from_type = self.the_type(expr.a.typ) |
| 381 to_type = self.the_type(expr.to_type) | |
| 389 | 382 if isinstance(from_type, ast.PointerType) and \ |
| 308 | 383 isinstance(to_type, ast.PointerType): |
| 384 expr.typ = expr.to_type | |
| 385 return ar | |
| 389 | 386 elif self.equal_types(self.intType, from_type) and \ |
| 387 isinstance(to_type, ast.PointerType): | |
| 388 expr.typ = expr.to_type | |
| 389 return ar | |
| 390 elif self.equal_types(self.intType, to_type) \ | |
| 364 | 391 and isinstance(from_type, ast.PointerType): |
| 392 expr.typ = expr.to_type | |
| 393 return ar | |
| 354 | 394 elif type(from_type) is ast.BaseType and from_type.name == 'byte' and \ |
| 395 type(to_type) is ast.BaseType and to_type.name == 'int': | |
| 396 expr.typ = expr.to_type | |
| 397 return ar | |
| 308 | 398 else: |
| 399 raise SemanticError('Cannot cast {} to {}' | |
| 400 .format(from_type, to_type), expr.loc) | |
| 353 | 401 |
| 308 | 402 def gen_function_call(self, expr): |
| 403 """ Generate code for a function call """ | |
| 404 # Evaluate the arguments: | |
| 393 | 405 args = [self.gen_expr_code(e) for e in expr.args] |
| 308 | 406 # Check arguments: |
| 407 tg = self.resolveSymbol(expr.proc) | |
| 408 if type(tg) is not ast.Function: | |
| 409 raise SemanticError('cannot call {}'.format(tg)) | |
| 410 ftyp = tg.typ | |
|
336
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
334
diff
changeset
|
411 fname = tg.package.name + '_' + tg.name |
| 308 | 412 ptypes = ftyp.parametertypes |
| 413 if len(expr.args) != len(ptypes): | |
| 414 raise SemanticError('{} requires {} arguments, {} given' | |
| 389 | 415 .format(fname, len(ptypes), len(expr.args)), |
| 416 expr.loc) | |
| 308 | 417 for arg, at in zip(expr.args, ptypes): |
| 389 | 418 if not self.equal_types(arg.typ, at): |
| 308 | 419 raise SemanticError('Got {}, expected {}' |
| 389 | 420 .format(arg.typ, at), arg.loc) |
| 308 | 421 # determine return type: |
| 422 expr.typ = ftyp.returntype | |
| 423 return ir.Call(fname, args) | |
| 424 | |
| 313 | 425 def evalConst(self, c): |
| 426 if isinstance(c, ir.Const): | |
| 427 return c | |
| 428 else: | |
| 429 raise SemanticError('Cannot evaluate constant {}'.format(c)) | |
| 430 | |
| 307 | 431 def resolveSymbol(self, sym): |
| 308 | 432 if type(sym) is ast.Member: |
| 307 | 433 base = self.resolveSymbol(sym.base) |
| 308 | 434 if type(base) is not ast.Package: |
| 435 raise SemanticError('Base is not a package', sym.loc) | |
| 307 | 436 scope = base.innerScope |
| 437 name = sym.field | |
| 308 | 438 elif type(sym) is ast.Identifier: |
| 307 | 439 scope = sym.scope |
| 440 name = sym.target | |
| 441 else: | |
| 442 raise NotImplementedError(str(sym)) | |
| 443 if name in scope: | |
| 444 s = scope[name] | |
| 445 else: | |
| 446 raise SemanticError('{} undefined'.format(name), sym.loc) | |
| 308 | 447 assert isinstance(s, ast.Symbol) |
| 307 | 448 return s |
| 449 | |
| 316 | 450 def size_of(self, t): |
| 451 """ Determine the byte size of a type """ | |
| 452 t = self.the_type(t) | |
| 453 if type(t) is ast.BaseType: | |
| 454 return t.bytesize | |
| 455 elif type(t) is ast.StructureType: | |
| 456 return sum(self.size_of(mem.typ) for mem in t.mems) | |
| 354 | 457 elif type(t) is ast.ArrayType: |
| 458 return t.size * self.size_of(t.element_type) | |
| 389 | 459 elif type(t) is ast.PointerType: |
| 460 return self.pointerSize | |
| 316 | 461 else: |
| 462 raise NotImplementedError(str(t)) | |
| 463 | |
| 389 | 464 def the_type(self, t, reveil_defined=True): |
| 465 """ Recurse until a 'real' type is found | |
| 466 When reveil_defined is True, defined types are resolved to | |
| 467 their backing types. | |
| 468 """ | |
| 308 | 469 if type(t) is ast.DefinedType: |
| 389 | 470 if reveil_defined: |
| 471 t = self.the_type(t.typ) | |
| 308 | 472 elif type(t) in [ast.Identifier, ast.Member]: |
| 389 | 473 t = self.the_type(self.resolveSymbol(t), reveil_defined) |
| 308 | 474 elif isinstance(t, ast.Type): |
| 307 | 475 pass |
| 476 else: | |
| 477 raise NotImplementedError(str(t)) | |
| 308 | 478 assert isinstance(t, ast.Type) |
| 307 | 479 return t |
| 480 | |
| 389 | 481 def equal_types(self, a, b, byname=False): |
| 482 """ Compare types a and b for structural equavalence. | |
| 483 if byname is True stop on defined types. | |
| 484 """ | |
| 307 | 485 # Recurse into named types: |
| 389 | 486 a = self.the_type(a, not byname) |
| 487 b = self.the_type(b, not byname) | |
| 307 | 488 |
| 389 | 489 # Check types for sanity: |
| 490 self.check_type(a) | |
| 491 self.check_type(b) | |
| 492 | |
| 493 # Do structural equivalence check: | |
| 307 | 494 if type(a) is type(b): |
| 308 | 495 if type(a) is ast.BaseType: |
| 307 | 496 return a.name == b.name |
| 308 | 497 elif type(a) is ast.PointerType: |
| 389 | 498 # If a pointed type is detected, stop structural |
| 499 # equivalence: | |
| 500 return self.equal_types(a.ptype, b.ptype, byname=True) | |
| 308 | 501 elif type(a) is ast.StructureType: |
| 307 | 502 if len(a.mems) != len(b.mems): |
| 503 return False | |
| 389 | 504 return all(self.equal_types(am.typ, bm.typ) for am, bm in |
| 307 | 505 zip(a.mems, b.mems)) |
| 354 | 506 elif type(a) is ast.ArrayType: |
| 389 | 507 return self.equal_types(a.element_type, b.element_type) |
| 508 elif type(a) is ast.DefinedType: | |
| 509 # Try by name in case of defined types: | |
| 510 return a.name == b.name | |
| 307 | 511 else: |
| 512 raise NotImplementedError('{} not implemented'.format(type(a))) | |
| 513 return False | |
| 389 | 514 |
| 515 def check_type(self, t, first=True, byname=False): | |
| 516 """ Determine struct offsets and check for recursiveness by using | |
| 517 mark and sweep algorithm. | |
| 518 The calling function could call this function with first set | |
| 519 to clear the marks. | |
| 520 """ | |
| 521 | |
| 522 # Reset the mark and sweep: | |
| 523 if first: | |
| 524 self.got_types = set() | |
| 525 | |
| 526 # Resolve the type: | |
| 527 t = self.the_type(t, not byname) | |
| 528 | |
| 529 # Check for recursion: | |
| 530 if t in self.got_types: | |
| 531 raise SemanticError('Recursive data type {}'.format(t), None) | |
| 532 | |
| 533 if type(t) is ast.BaseType: | |
| 534 pass | |
| 535 elif type(t) is ast.PointerType: | |
| 536 # If a pointed type is detected, stop structural | |
| 537 # equivalence: | |
| 538 self.check_type(t.ptype, first=False, byname=True) | |
| 539 elif type(t) is ast.StructureType: | |
| 540 self.got_types.add(t) | |
| 541 # Setup offsets of fields. Is this the right place?: | |
| 542 offset = 0 | |
| 543 for struct_member in t.mems: | |
| 544 self.check_type(struct_member.typ, first=False) | |
| 545 struct_member.offset = offset | |
| 546 offset = offset + self.size_of(struct_member.typ) | |
| 547 elif type(t) is ast.ArrayType: | |
| 548 self.check_type(t.element_type, first=False) | |
| 549 elif type(t) is ast.DefinedType: | |
| 550 pass | |
| 551 else: | |
| 552 raise NotImplementedError('{} not implemented'.format(type(t))) |