paul@438 | 1 | #!/usr/bin/env python |
paul@438 | 2 | |
paul@438 | 3 | """ |
paul@438 | 4 | Generate low-level code. |
paul@438 | 5 | |
paul@491 | 6 | Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012 Paul Boddie <paul@boddie.org.uk> |
paul@438 | 7 | |
paul@438 | 8 | This program is free software; you can redistribute it and/or modify it under |
paul@438 | 9 | the terms of the GNU General Public License as published by the Free Software |
paul@438 | 10 | Foundation; either version 3 of the License, or (at your option) any later |
paul@438 | 11 | version. |
paul@438 | 12 | |
paul@438 | 13 | This program is distributed in the hope that it will be useful, but WITHOUT |
paul@438 | 14 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS |
paul@438 | 15 | FOR A PARTICULAR PURPOSE. See the GNU General Public License for more |
paul@438 | 16 | details. |
paul@438 | 17 | |
paul@438 | 18 | You should have received a copy of the GNU General Public License along with |
paul@438 | 19 | this program. If not, see <http://www.gnu.org/licenses/>. |
paul@438 | 20 | """ |
paul@438 | 21 | |
paul@438 | 22 | from micropython.opt import Optimiser |
paul@438 | 23 | from micropython.data import * |
paul@555 | 24 | from micropython.errors import * |
paul@438 | 25 | from micropython.rsvp import * |
paul@438 | 26 | import compiler.ast |
paul@438 | 27 | |
paul@438 | 28 | class Assembler: |
paul@438 | 29 | |
paul@438 | 30 | "Support for generating low-level code." |
paul@438 | 31 | |
paul@479 | 32 | def __init__(self, program): |
paul@438 | 33 | |
paul@479 | 34 | """ |
paul@479 | 35 | Initialise the assembler with a program, optimiser and status |
paul@479 | 36 | attributes. |
paul@479 | 37 | """ |
paul@479 | 38 | |
paul@479 | 39 | self.program = program |
paul@438 | 40 | |
paul@438 | 41 | # Optimisation. |
paul@438 | 42 | |
paul@479 | 43 | self.optimiser = Optimiser(self, program.optimisations) |
paul@438 | 44 | |
paul@438 | 45 | # The current unit being translated. |
paul@438 | 46 | |
paul@438 | 47 | self.unit = None |
paul@438 | 48 | |
paul@438 | 49 | # The temporary storage used by the current assignment expression. |
paul@438 | 50 | |
paul@438 | 51 | self.expr_temp = [] |
paul@438 | 52 | |
paul@469 | 53 | # The start of the current assignment target instructions. |
paul@469 | 54 | |
paul@469 | 55 | self.target_start = None |
paul@469 | 56 | |
paul@438 | 57 | # Wiring within the code. |
paul@438 | 58 | |
paul@438 | 59 | self.labels = {} |
paul@438 | 60 | self.label_number = 0 |
paul@438 | 61 | self.loop_blocks = [] |
paul@438 | 62 | self.exception_blocks = [] |
paul@438 | 63 | |
paul@438 | 64 | def reset(self): |
paul@438 | 65 | |
paul@438 | 66 | "Reset the state of the assembler." |
paul@438 | 67 | |
paul@438 | 68 | # The code itself. This is limited to the code for a particular block |
paul@438 | 69 | # being processed. |
paul@438 | 70 | |
paul@438 | 71 | self.blocks = [] |
paul@438 | 72 | |
paul@438 | 73 | # Information about temporary values. |
paul@438 | 74 | |
paul@438 | 75 | self.temp_positions = set() |
paul@438 | 76 | self.max_temp_position = -1 |
paul@438 | 77 | |
paul@438 | 78 | # Information about instructions which construct frames. |
paul@438 | 79 | |
paul@438 | 80 | self.frame_makers = [] |
paul@438 | 81 | |
paul@438 | 82 | # Optimiser state must be reset for each unit. |
paul@438 | 83 | |
paul@438 | 84 | self.optimiser.reset() |
paul@438 | 85 | |
paul@438 | 86 | def new_block(self): |
paul@438 | 87 | |
paul@438 | 88 | "Return a new code block." |
paul@438 | 89 | |
paul@491 | 90 | return Block(self.unit) |
paul@438 | 91 | |
paul@452 | 92 | def get_block(self): |
paul@452 | 93 | |
paul@452 | 94 | "Return the current block." |
paul@452 | 95 | |
paul@452 | 96 | return self.blocks[-1] |
paul@438 | 97 | |
paul@452 | 98 | def set_block(self, block, preceding=None): |
paul@438 | 99 | |
paul@452 | 100 | """ |
paul@452 | 101 | Add the given 'block' to the unit's list of blocks, noting any active |
paul@452 | 102 | value information from 'preceding' blocks on the new block. |
paul@452 | 103 | """ |
paul@452 | 104 | |
paul@452 | 105 | self.optimiser.reset(block, preceding) |
paul@438 | 106 | self.blocks.append(block) |
paul@438 | 107 | |
paul@438 | 108 | def get_loop_blocks(self): |
paul@438 | 109 | return self.loop_blocks[-1] |
paul@438 | 110 | |
paul@438 | 111 | def add_loop_blocks(self, next_block, exit_block): |
paul@438 | 112 | self.loop_blocks.append((next_block, exit_block)) |
paul@438 | 113 | |
paul@438 | 114 | def drop_loop_blocks(self): |
paul@438 | 115 | self.loop_blocks.pop() |
paul@438 | 116 | |
paul@438 | 117 | def add_exception_unit(self): |
paul@438 | 118 | self.exception_blocks.append([]) |
paul@438 | 119 | |
paul@438 | 120 | def get_exception_blocks(self): |
paul@438 | 121 | return self.exception_blocks[-1][-1] |
paul@438 | 122 | |
paul@438 | 123 | def add_exception_blocks(self, handler_block, exit_block): |
paul@438 | 124 | self.exception_blocks[-1].append((handler_block, exit_block)) |
paul@438 | 125 | |
paul@438 | 126 | def drop_exception_blocks(self): |
paul@438 | 127 | self.exception_blocks[-1].pop() |
paul@438 | 128 | |
paul@438 | 129 | def drop_exception_unit(self): |
paul@438 | 130 | self.exception_blocks.pop() |
paul@438 | 131 | |
paul@438 | 132 | # Assignment expression values. |
paul@438 | 133 | |
paul@438 | 134 | def record_value(self, immediate=1): |
paul@438 | 135 | |
paul@438 | 136 | """ |
paul@438 | 137 | Record the current active value for an assignment. If the optional |
paul@464 | 138 | 'immediate' parameter is set to a false value, new temporary storage to |
paul@464 | 139 | hold the recorded value will be allocated; otherwise, the |
paul@438 | 140 | value-providing instruction may be replicated in order to provide the |
paul@438 | 141 | active value later on. |
paul@438 | 142 | """ |
paul@438 | 143 | |
paul@438 | 144 | if immediate: |
paul@438 | 145 | temp = self.optimiser.optimise_temp_storage() |
paul@438 | 146 | else: |
paul@438 | 147 | temp = self.get_temp() |
paul@438 | 148 | self.expr_temp.append(temp) |
paul@438 | 149 | |
paul@438 | 150 | def discard_value(self): |
paul@438 | 151 | |
paul@438 | 152 | "Discard any temporary storage in use for the current assignment value." |
paul@438 | 153 | |
paul@438 | 154 | self.discard_temp(self.expr_temp.pop()) |
paul@438 | 155 | |
paul@469 | 156 | def start_target(self): |
paul@469 | 157 | |
paul@469 | 158 | """ |
paul@469 | 159 | Start recording instructions used to define the target of an assignment. |
paul@469 | 160 | """ |
paul@469 | 161 | |
paul@469 | 162 | self.target_start = len(self.blocks[-1]) |
paul@469 | 163 | |
paul@469 | 164 | def remove_target_ops(self): |
paul@469 | 165 | |
paul@469 | 166 | "Remove the assignment target instructions." |
paul@469 | 167 | |
paul@469 | 168 | del self.blocks[-1].code[self.target_start:] |
paul@469 | 169 | self.target_start = None |
paul@469 | 170 | self.optimiser.clear_active() |
paul@469 | 171 | |
paul@469 | 172 | def get_target_ops(self): |
paul@469 | 173 | |
paul@469 | 174 | "Return the assignment target instructions." |
paul@469 | 175 | |
paul@469 | 176 | return self.blocks[-1].code[self.target_start:] |
paul@469 | 177 | |
paul@451 | 178 | def assign_value(self, expr=None): |
paul@438 | 179 | |
paul@438 | 180 | """ |
paul@450 | 181 | Set the source of an assignment using 'expr' or the current assignment |
paul@469 | 182 | value. This may set the source register of the current instruction. |
paul@438 | 183 | """ |
paul@438 | 184 | |
paul@469 | 185 | expr = expr or self.expr_temp[-1] |
paul@469 | 186 | |
paul@469 | 187 | # Optimise away constant storage if appropriate. |
paul@450 | 188 | |
paul@469 | 189 | if self.optimiser.optimise_constant_storage(expr): |
paul@469 | 190 | self.remove_target_ops() |
paul@469 | 191 | return |
paul@450 | 192 | |
paul@450 | 193 | # Otherwise, insert the assignment source. |
paul@438 | 194 | |
paul@469 | 195 | expr_copy = expr.copy() |
paul@469 | 196 | assign_ops = self.get_target_ops() |
paul@469 | 197 | |
paul@469 | 198 | if not assign_ops: |
paul@469 | 199 | self.target_start = None |
paul@469 | 200 | return |
paul@464 | 201 | |
paul@469 | 202 | assign_op = assign_ops[-1] |
paul@464 | 203 | |
paul@469 | 204 | # Either insert the instruction yielding the value and adjust the |
paul@469 | 205 | # assignment source. |
paul@464 | 206 | |
paul@469 | 207 | expr_copy.target = "source" |
paul@464 | 208 | |
paul@469 | 209 | if self.insert_op(-1, expr_copy): |
paul@469 | 210 | assign_op.source = "source" |
paul@469 | 211 | self.update_temp(expr, expr_copy) |
paul@464 | 212 | |
paul@469 | 213 | # (Now, the instruction need not be inserted.) |
paul@469 | 214 | |
paul@469 | 215 | # Or transfer the working value to the source register. |
paul@464 | 216 | |
paul@469 | 217 | elif assign_op.working == "working": |
paul@469 | 218 | self.insert_op(-1, Transfer(source="working_context", target="source_context")) |
paul@469 | 219 | self.insert_op(-1, Transfer(source="working", target="source")) |
paul@469 | 220 | assign_op.source = "source" |
paul@464 | 221 | |
paul@469 | 222 | # Or let the assignment use the working register. |
paul@464 | 223 | |
paul@469 | 224 | else: |
paul@469 | 225 | assign_op.source = "working" |
paul@469 | 226 | |
paul@469 | 227 | self.target_start = None |
paul@438 | 228 | |
paul@450 | 229 | def set_target(self, target): |
paul@450 | 230 | |
paul@450 | 231 | "Reset the target of the active instruction to 'target'." |
paul@450 | 232 | |
paul@484 | 233 | self.optimiser.set_target("working", target) |
paul@438 | 234 | |
paul@438 | 235 | def is_immediate_user(self, node): |
paul@438 | 236 | |
paul@438 | 237 | """ |
paul@438 | 238 | Return whether 'node' is an immediate user of an assignment expression. |
paul@438 | 239 | """ |
paul@438 | 240 | |
paul@438 | 241 | return isinstance(node, (compiler.ast.AssName, compiler.ast.AssAttr)) |
paul@438 | 242 | |
paul@438 | 243 | def has_immediate_usage(self, nodes): |
paul@438 | 244 | |
paul@438 | 245 | """ |
paul@438 | 246 | Return whether 'nodes' are all immediate users of an assignment expression. |
paul@438 | 247 | """ |
paul@438 | 248 | |
paul@438 | 249 | for n in nodes: |
paul@438 | 250 | if not self.is_immediate_user(n): |
paul@591 | 251 | return False |
paul@591 | 252 | return True |
paul@438 | 253 | |
paul@438 | 254 | # Temporary storage administration. |
paul@438 | 255 | |
paul@438 | 256 | def get_temp(self): |
paul@438 | 257 | |
paul@438 | 258 | """ |
paul@464 | 259 | Return a temporary storage access instruction for the current value. |
paul@464 | 260 | Initially, this instruction is not associated with an allocated unit of |
paul@464 | 261 | temporary storage, and if used as a new instruction will not be added to |
paul@464 | 262 | the code, but if the current value changes, the 'set_temp' method will |
paul@464 | 263 | be called by the optimiser and a unit of storage will be allocated. |
paul@438 | 264 | """ |
paul@438 | 265 | |
paul@464 | 266 | temp = LoadTemp(None) |
paul@484 | 267 | self.optimiser.request_active_value("working", temp, self.blocks[-1], len(self.blocks[-1].code)) |
paul@464 | 268 | return temp |
paul@464 | 269 | |
paul@464 | 270 | def set_temp(self, temp, block, pos): |
paul@464 | 271 | |
paul@464 | 272 | """ |
paul@464 | 273 | Emit a storage instruction for the given 'temp' loading instruction, |
paul@464 | 274 | reserving a new temporary storage location. |
paul@464 | 275 | """ |
paul@464 | 276 | |
paul@464 | 277 | if temp.attr is None: |
paul@464 | 278 | temp.attr = self.reserve_temp() |
paul@464 | 279 | block.insert(pos, StoreTemp(temp.attr)) |
paul@464 | 280 | |
paul@464 | 281 | def update_temp(self, temp, updated): |
paul@464 | 282 | |
paul@464 | 283 | "Update 'temp' using the given 'updated' instruction." |
paul@464 | 284 | |
paul@464 | 285 | if isinstance(temp, LoadTemp): |
paul@464 | 286 | temp.attr = updated.attr |
paul@438 | 287 | |
paul@438 | 288 | def reserve_temp(self, temp_position=None): |
paul@438 | 289 | |
paul@438 | 290 | """ |
paul@438 | 291 | Reserve a new temporary storage position, or if the optional |
paul@438 | 292 | 'temp_position' is specified, ensure that this particular position is |
paul@438 | 293 | reserved. |
paul@438 | 294 | """ |
paul@438 | 295 | |
paul@438 | 296 | if temp_position is not None: |
paul@438 | 297 | pass |
paul@438 | 298 | elif not self.temp_positions: |
paul@438 | 299 | temp_position = 0 |
paul@438 | 300 | else: |
paul@438 | 301 | temp_position = max(self.temp_positions) + 1 |
paul@438 | 302 | |
paul@438 | 303 | self.temp_positions.add(temp_position) |
paul@438 | 304 | self.max_temp_position = max(self.max_temp_position, temp_position) |
paul@438 | 305 | return self.unit.all_local_usage + temp_position # position in frame |
paul@438 | 306 | |
paul@438 | 307 | def ensure_temp(self, instruction=None): |
paul@438 | 308 | |
paul@438 | 309 | """ |
paul@438 | 310 | Ensure that the 'instruction' is using a reserved temporary storage |
paul@438 | 311 | position. |
paul@438 | 312 | """ |
paul@438 | 313 | |
paul@438 | 314 | if isinstance(instruction, LoadTemp): |
paul@438 | 315 | temp_position = instruction.attr - self.unit.all_local_usage |
paul@438 | 316 | self.reserve_temp(temp_position) |
paul@438 | 317 | |
paul@438 | 318 | def discard_temp(self, instruction=None): |
paul@438 | 319 | |
paul@438 | 320 | "Discard any temporary storage position used by 'instruction'." |
paul@438 | 321 | |
paul@464 | 322 | if isinstance(instruction, LoadTemp) and instruction.attr is not None: |
paul@438 | 323 | temp_position = instruction.attr - self.unit.all_local_usage |
paul@438 | 324 | self.free_temp(temp_position) |
paul@469 | 325 | |
paul@469 | 326 | # Prevent any requested active value from generating instructions now |
paul@469 | 327 | # that our interest in it has passed. |
paul@469 | 328 | |
paul@484 | 329 | self.optimiser.ignore_active_value("working") |
paul@438 | 330 | |
paul@438 | 331 | def free_temp(self, temp_position): |
paul@438 | 332 | |
paul@438 | 333 | "Free the temporary storage position specified by 'temp_position'." |
paul@438 | 334 | |
paul@438 | 335 | if temp_position in self.temp_positions: |
paul@438 | 336 | self.temp_positions.remove(temp_position) |
paul@438 | 337 | |
paul@438 | 338 | def set_frame_usage(self, node, extend): |
paul@438 | 339 | |
paul@438 | 340 | """ |
paul@438 | 341 | Ensure that the frame usage for the unit associated with 'node' is set |
paul@438 | 342 | on the 'extend' instruction. |
paul@438 | 343 | """ |
paul@438 | 344 | |
paul@438 | 345 | # Remove any ExtendFrame instructions which do nothing. |
paul@438 | 346 | |
paul@438 | 347 | if self.last_op() is extend: |
paul@438 | 348 | self.remove_op() |
paul@438 | 349 | return |
paul@438 | 350 | |
paul@438 | 351 | ntemp = self.max_temp_position + 1 |
paul@438 | 352 | extend.attr = ntemp + node.unit.local_usage # NOTE: See get_code for similar code. |
paul@438 | 353 | |
paul@438 | 354 | # Code writing methods. |
paul@438 | 355 | |
paul@438 | 356 | def new_op(self, op): |
paul@438 | 357 | |
paul@438 | 358 | """ |
paul@438 | 359 | Add 'op' to the generated code, returning a true value if an instruction |
paul@438 | 360 | was added. |
paul@438 | 361 | """ |
paul@438 | 362 | |
paul@464 | 363 | if not self.check_op(op): |
paul@591 | 364 | return False |
paul@438 | 365 | |
paul@438 | 366 | # Add the operation to the current block. |
paul@438 | 367 | |
paul@484 | 368 | self.optimiser.set_new("working", op) |
paul@464 | 369 | self.blocks[-1].append(op) |
paul@591 | 370 | return True |
paul@438 | 371 | |
paul@450 | 372 | def insert_op(self, i, op): |
paul@450 | 373 | |
paul@450 | 374 | "Insert at index 'i' in the current block the instruction 'op'." |
paul@450 | 375 | |
paul@464 | 376 | if not self.check_op(op): |
paul@591 | 377 | return False |
paul@464 | 378 | |
paul@464 | 379 | self.blocks[-1].insert(i, op) |
paul@591 | 380 | return True |
paul@464 | 381 | |
paul@464 | 382 | def check_op(self, op): |
paul@464 | 383 | |
paul@464 | 384 | "Return whether the given 'op' is to be added to the code." |
paul@464 | 385 | |
paul@464 | 386 | # Optimise away temporary storage instructions where the active value is |
paul@464 | 387 | # still available and was not recorded. |
paul@464 | 388 | |
paul@464 | 389 | if isinstance(op, LoadTemp) and op.attr is None: |
paul@591 | 390 | return False |
paul@464 | 391 | |
paul@464 | 392 | # Optimise load operations employed by this instruction. |
paul@464 | 393 | |
paul@464 | 394 | if self.optimiser.optimise_away_no_operations(op) or self.optimiser.optimise_unused_handlers(op): |
paul@591 | 395 | return False |
paul@464 | 396 | |
paul@591 | 397 | return True |
paul@450 | 398 | |
paul@438 | 399 | def remove_op(self): |
paul@438 | 400 | |
paul@438 | 401 | "Remove the last instruction." |
paul@438 | 402 | |
paul@438 | 403 | op = self.blocks[-1].code.pop() |
paul@438 | 404 | self.optimiser.clear_active() |
paul@469 | 405 | return op |
paul@438 | 406 | |
paul@438 | 407 | def replace_op(self, op): |
paul@438 | 408 | |
paul@438 | 409 | "Replace the last added instruction with 'op'." |
paul@438 | 410 | |
paul@438 | 411 | self.remove_op() |
paul@438 | 412 | self.new_op(op) |
paul@438 | 413 | |
paul@484 | 414 | def replace_active_value(self, register, op): |
paul@438 | 415 | |
paul@438 | 416 | """ |
paul@484 | 417 | Replace the active instruction providing 'register' with its value with |
paul@484 | 418 | the given 'op' if appropriate. |
paul@438 | 419 | """ |
paul@438 | 420 | |
paul@484 | 421 | removed = self.optimiser.remove_active_value(register) |
paul@438 | 422 | self.new_op(op) |
paul@469 | 423 | return removed |
paul@438 | 424 | |
paul@438 | 425 | def last_op(self): |
paul@438 | 426 | |
paul@438 | 427 | "Return the last added instruction." |
paul@438 | 428 | |
paul@438 | 429 | try: |
paul@438 | 430 | return self.blocks[-1].code[-1] |
paul@438 | 431 | except IndexError: |
paul@438 | 432 | return None |
paul@438 | 433 | |
paul@479 | 434 | # Allocation-related methods. |
paul@479 | 435 | |
paul@479 | 436 | def make_instance(self, cls, n): |
paul@479 | 437 | |
paul@479 | 438 | """ |
paul@479 | 439 | Request a new instance using the given class 'cls' and with 'n' |
paul@479 | 440 | attributes. |
paul@479 | 441 | """ |
paul@479 | 442 | |
paul@479 | 443 | # Load the class in order to locate the instance template. |
paul@479 | 444 | |
paul@479 | 445 | self.new_op(LoadConst(cls)) |
paul@479 | 446 | |
paul@479 | 447 | # NOTE: Instance headers are one location. |
paul@479 | 448 | |
paul@479 | 449 | self.new_op(MakeInstance(n + 1)) |
paul@479 | 450 | |
paul@479 | 451 | def make_exception(self, name): |
paul@479 | 452 | |
paul@479 | 453 | "Make an exception of the given 'name' using 'node'." |
paul@479 | 454 | |
paul@479 | 455 | # NOTE: Reserving an attribute. |
paul@479 | 456 | |
paul@479 | 457 | self.make_instance(self.get_builtin_class(name), 1) |
paul@479 | 458 | |
paul@479 | 459 | # Name-related methods. |
paul@479 | 460 | |
paul@479 | 461 | def get_scope(self, name): |
paul@479 | 462 | |
paul@479 | 463 | "Return the scope for the given 'name'." |
paul@479 | 464 | |
paul@479 | 465 | attr, scope, from_name = self.unit._get_with_scope(name) |
paul@479 | 466 | return scope |
paul@479 | 467 | |
paul@479 | 468 | def load_builtin(self, name, node): |
paul@479 | 469 | |
paul@479 | 470 | "Generate an instruction loading 'name' for the given 'node'." |
paul@479 | 471 | |
paul@479 | 472 | self.new_op(LoadAddress(self.get_builtin(name))) |
paul@479 | 473 | |
paul@479 | 474 | def get_builtin_class(self, name): |
paul@479 | 475 | |
paul@479 | 476 | "Return the built-in class with the given 'name'." |
paul@479 | 477 | |
paul@479 | 478 | return self.get_builtin(name).get_value() |
paul@479 | 479 | |
paul@479 | 480 | def get_builtin(self, name): |
paul@479 | 481 | |
paul@479 | 482 | "Return the built-in module definition for the given 'name'." |
paul@479 | 483 | |
paul@479 | 484 | if self.builtins is not None: |
paul@479 | 485 | try: |
paul@479 | 486 | return self.builtins[name] |
paul@479 | 487 | except KeyError: |
paul@479 | 488 | raise TranslateError("No __builtins__ definition is available for name %r." % name) |
paul@479 | 489 | else: |
paul@479 | 490 | raise TranslateError("No __builtins__ module is available for name %r." % name) |
paul@479 | 491 | |
paul@438 | 492 | # vim: tabstop=4 expandtab shiftwidth=4 |