paul@438 | 1 | #!/usr/bin/env python |
paul@438 | 2 | |
paul@438 | 3 | """ |
paul@438 | 4 | Generate low-level code. |
paul@438 | 5 | |
paul@438 | 6 | Copyright (C) 2007, 2008, 2009, 2010, 2011 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.common import * |
paul@438 | 24 | from micropython.data 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@438 | 32 | def __init__(self, optimisations): |
paul@438 | 33 | |
paul@438 | 34 | "Initialise the assembler with an optimiser and status attributes." |
paul@438 | 35 | |
paul@438 | 36 | # Optimisation. |
paul@438 | 37 | |
paul@438 | 38 | self.optimiser = Optimiser(self, optimisations) |
paul@438 | 39 | |
paul@438 | 40 | # The current unit being translated. |
paul@438 | 41 | |
paul@438 | 42 | self.unit = None |
paul@438 | 43 | |
paul@438 | 44 | # The temporary storage used by the current assignment expression. |
paul@438 | 45 | |
paul@438 | 46 | self.expr_temp = [] |
paul@438 | 47 | |
paul@469 | 48 | # The start of the current assignment target instructions. |
paul@469 | 49 | |
paul@469 | 50 | self.target_start = None |
paul@469 | 51 | |
paul@438 | 52 | # Wiring within the code. |
paul@438 | 53 | |
paul@438 | 54 | self.labels = {} |
paul@438 | 55 | self.label_number = 0 |
paul@438 | 56 | self.loop_blocks = [] |
paul@438 | 57 | self.exception_blocks = [] |
paul@438 | 58 | |
paul@438 | 59 | def reset(self): |
paul@438 | 60 | |
paul@438 | 61 | "Reset the state of the assembler." |
paul@438 | 62 | |
paul@438 | 63 | # The code itself. This is limited to the code for a particular block |
paul@438 | 64 | # being processed. |
paul@438 | 65 | |
paul@438 | 66 | self.blocks = [] |
paul@438 | 67 | |
paul@438 | 68 | # Information about temporary values. |
paul@438 | 69 | |
paul@438 | 70 | self.temp_positions = set() |
paul@438 | 71 | self.max_temp_position = -1 |
paul@438 | 72 | |
paul@438 | 73 | # Information about instructions which construct frames. |
paul@438 | 74 | |
paul@438 | 75 | self.frame_makers = [] |
paul@438 | 76 | |
paul@438 | 77 | # Optimiser state must be reset for each unit. |
paul@438 | 78 | |
paul@438 | 79 | self.optimiser.reset() |
paul@438 | 80 | |
paul@438 | 81 | def new_block(self): |
paul@438 | 82 | |
paul@438 | 83 | "Return a new code block." |
paul@438 | 84 | |
paul@438 | 85 | return Block() |
paul@438 | 86 | |
paul@452 | 87 | def get_block(self): |
paul@452 | 88 | |
paul@452 | 89 | "Return the current block." |
paul@452 | 90 | |
paul@452 | 91 | return self.blocks[-1] |
paul@438 | 92 | |
paul@452 | 93 | def set_block(self, block, preceding=None): |
paul@438 | 94 | |
paul@452 | 95 | """ |
paul@452 | 96 | Add the given 'block' to the unit's list of blocks, noting any active |
paul@452 | 97 | value information from 'preceding' blocks on the new block. |
paul@452 | 98 | """ |
paul@452 | 99 | |
paul@452 | 100 | self.optimiser.reset(block, preceding) |
paul@438 | 101 | self.blocks.append(block) |
paul@438 | 102 | |
paul@438 | 103 | def get_loop_blocks(self): |
paul@438 | 104 | return self.loop_blocks[-1] |
paul@438 | 105 | |
paul@438 | 106 | def add_loop_blocks(self, next_block, exit_block): |
paul@438 | 107 | self.loop_blocks.append((next_block, exit_block)) |
paul@438 | 108 | |
paul@438 | 109 | def drop_loop_blocks(self): |
paul@438 | 110 | self.loop_blocks.pop() |
paul@438 | 111 | |
paul@438 | 112 | def add_exception_unit(self): |
paul@438 | 113 | self.exception_blocks.append([]) |
paul@438 | 114 | |
paul@438 | 115 | def get_exception_blocks(self): |
paul@438 | 116 | return self.exception_blocks[-1][-1] |
paul@438 | 117 | |
paul@438 | 118 | def add_exception_blocks(self, handler_block, exit_block): |
paul@438 | 119 | self.exception_blocks[-1].append((handler_block, exit_block)) |
paul@438 | 120 | |
paul@438 | 121 | def drop_exception_blocks(self): |
paul@438 | 122 | self.exception_blocks[-1].pop() |
paul@438 | 123 | |
paul@438 | 124 | def drop_exception_unit(self): |
paul@438 | 125 | self.exception_blocks.pop() |
paul@438 | 126 | |
paul@438 | 127 | # Assignment expression values. |
paul@438 | 128 | |
paul@438 | 129 | def record_value(self, immediate=1): |
paul@438 | 130 | |
paul@438 | 131 | """ |
paul@438 | 132 | Record the current active value for an assignment. If the optional |
paul@464 | 133 | 'immediate' parameter is set to a false value, new temporary storage to |
paul@464 | 134 | hold the recorded value will be allocated; otherwise, the |
paul@438 | 135 | value-providing instruction may be replicated in order to provide the |
paul@438 | 136 | active value later on. |
paul@438 | 137 | """ |
paul@438 | 138 | |
paul@438 | 139 | if immediate: |
paul@438 | 140 | temp = self.optimiser.optimise_temp_storage() |
paul@438 | 141 | else: |
paul@438 | 142 | temp = self.get_temp() |
paul@438 | 143 | self.expr_temp.append(temp) |
paul@438 | 144 | |
paul@438 | 145 | def discard_value(self): |
paul@438 | 146 | |
paul@438 | 147 | "Discard any temporary storage in use for the current assignment value." |
paul@438 | 148 | |
paul@438 | 149 | self.discard_temp(self.expr_temp.pop()) |
paul@438 | 150 | |
paul@469 | 151 | def start_target(self): |
paul@469 | 152 | |
paul@469 | 153 | """ |
paul@469 | 154 | Start recording instructions used to define the target of an assignment. |
paul@469 | 155 | """ |
paul@469 | 156 | |
paul@469 | 157 | self.target_start = len(self.blocks[-1]) |
paul@469 | 158 | |
paul@469 | 159 | def remove_target_ops(self): |
paul@469 | 160 | |
paul@469 | 161 | "Remove the assignment target instructions." |
paul@469 | 162 | |
paul@469 | 163 | del self.blocks[-1].code[self.target_start:] |
paul@469 | 164 | self.target_start = None |
paul@469 | 165 | self.optimiser.clear_active() |
paul@469 | 166 | |
paul@469 | 167 | def get_target_ops(self): |
paul@469 | 168 | |
paul@469 | 169 | "Return the assignment target instructions." |
paul@469 | 170 | |
paul@469 | 171 | return self.blocks[-1].code[self.target_start:] |
paul@469 | 172 | |
paul@451 | 173 | def assign_value(self, expr=None): |
paul@438 | 174 | |
paul@438 | 175 | """ |
paul@450 | 176 | Set the source of an assignment using 'expr' or the current assignment |
paul@469 | 177 | value. This may set the source register of the current instruction. |
paul@438 | 178 | """ |
paul@438 | 179 | |
paul@469 | 180 | expr = expr or self.expr_temp[-1] |
paul@469 | 181 | |
paul@469 | 182 | # Optimise away constant storage if appropriate. |
paul@450 | 183 | |
paul@469 | 184 | if self.optimiser.optimise_constant_storage(expr): |
paul@469 | 185 | self.remove_target_ops() |
paul@469 | 186 | return |
paul@450 | 187 | |
paul@450 | 188 | # Otherwise, insert the assignment source. |
paul@438 | 189 | |
paul@469 | 190 | expr_copy = expr.copy() |
paul@469 | 191 | assign_ops = self.get_target_ops() |
paul@469 | 192 | |
paul@469 | 193 | if not assign_ops: |
paul@469 | 194 | self.target_start = None |
paul@469 | 195 | return |
paul@464 | 196 | |
paul@469 | 197 | assign_op = assign_ops[-1] |
paul@464 | 198 | |
paul@469 | 199 | # Either insert the instruction yielding the value and adjust the |
paul@469 | 200 | # assignment source. |
paul@464 | 201 | |
paul@469 | 202 | expr_copy.target = "source" |
paul@464 | 203 | |
paul@469 | 204 | if self.insert_op(-1, expr_copy): |
paul@469 | 205 | assign_op.source = "source" |
paul@469 | 206 | self.update_temp(expr, expr_copy) |
paul@464 | 207 | |
paul@469 | 208 | # (Now, the instruction need not be inserted.) |
paul@469 | 209 | |
paul@469 | 210 | # Or transfer the working value to the source register. |
paul@464 | 211 | |
paul@469 | 212 | elif assign_op.working == "working": |
paul@469 | 213 | self.insert_op(-1, Transfer(source="working_context", target="source_context")) |
paul@469 | 214 | self.insert_op(-1, Transfer(source="working", target="source")) |
paul@469 | 215 | assign_op.source = "source" |
paul@464 | 216 | |
paul@469 | 217 | # Or let the assignment use the working register. |
paul@464 | 218 | |
paul@469 | 219 | else: |
paul@469 | 220 | assign_op.source = "working" |
paul@469 | 221 | |
paul@469 | 222 | self.target_start = None |
paul@438 | 223 | |
paul@450 | 224 | def set_target(self, target): |
paul@450 | 225 | |
paul@450 | 226 | "Reset the target of the active instruction to 'target'." |
paul@450 | 227 | |
paul@450 | 228 | self.optimiser.set_target(target) |
paul@438 | 229 | |
paul@438 | 230 | def is_immediate_user(self, node): |
paul@438 | 231 | |
paul@438 | 232 | """ |
paul@438 | 233 | Return whether 'node' is an immediate user of an assignment expression. |
paul@438 | 234 | """ |
paul@438 | 235 | |
paul@438 | 236 | return isinstance(node, (compiler.ast.AssName, compiler.ast.AssAttr)) |
paul@438 | 237 | |
paul@438 | 238 | def has_immediate_usage(self, nodes): |
paul@438 | 239 | |
paul@438 | 240 | """ |
paul@438 | 241 | Return whether 'nodes' are all immediate users of an assignment expression. |
paul@438 | 242 | """ |
paul@438 | 243 | |
paul@438 | 244 | for n in nodes: |
paul@438 | 245 | if not self.is_immediate_user(n): |
paul@438 | 246 | return 0 |
paul@438 | 247 | return 1 |
paul@438 | 248 | |
paul@438 | 249 | # Temporary storage administration. |
paul@438 | 250 | |
paul@438 | 251 | def get_temp(self): |
paul@438 | 252 | |
paul@438 | 253 | """ |
paul@464 | 254 | Return a temporary storage access instruction for the current value. |
paul@464 | 255 | Initially, this instruction is not associated with an allocated unit of |
paul@464 | 256 | temporary storage, and if used as a new instruction will not be added to |
paul@464 | 257 | the code, but if the current value changes, the 'set_temp' method will |
paul@464 | 258 | be called by the optimiser and a unit of storage will be allocated. |
paul@438 | 259 | """ |
paul@438 | 260 | |
paul@464 | 261 | temp = LoadTemp(None) |
paul@464 | 262 | self.optimiser.request_active_value(temp, self.blocks[-1], len(self.blocks[-1].code)) |
paul@464 | 263 | return temp |
paul@464 | 264 | |
paul@464 | 265 | def set_temp(self, temp, block, pos): |
paul@464 | 266 | |
paul@464 | 267 | """ |
paul@464 | 268 | Emit a storage instruction for the given 'temp' loading instruction, |
paul@464 | 269 | reserving a new temporary storage location. |
paul@464 | 270 | """ |
paul@464 | 271 | |
paul@464 | 272 | if temp.attr is None: |
paul@464 | 273 | temp.attr = self.reserve_temp() |
paul@464 | 274 | block.insert(pos, StoreTemp(temp.attr)) |
paul@464 | 275 | |
paul@464 | 276 | def update_temp(self, temp, updated): |
paul@464 | 277 | |
paul@464 | 278 | "Update 'temp' using the given 'updated' instruction." |
paul@464 | 279 | |
paul@464 | 280 | if isinstance(temp, LoadTemp): |
paul@464 | 281 | temp.attr = updated.attr |
paul@438 | 282 | |
paul@438 | 283 | def reserve_temp(self, temp_position=None): |
paul@438 | 284 | |
paul@438 | 285 | """ |
paul@438 | 286 | Reserve a new temporary storage position, or if the optional |
paul@438 | 287 | 'temp_position' is specified, ensure that this particular position is |
paul@438 | 288 | reserved. |
paul@438 | 289 | """ |
paul@438 | 290 | |
paul@438 | 291 | if temp_position is not None: |
paul@438 | 292 | pass |
paul@438 | 293 | elif not self.temp_positions: |
paul@438 | 294 | temp_position = 0 |
paul@438 | 295 | else: |
paul@438 | 296 | temp_position = max(self.temp_positions) + 1 |
paul@438 | 297 | |
paul@438 | 298 | self.temp_positions.add(temp_position) |
paul@438 | 299 | self.max_temp_position = max(self.max_temp_position, temp_position) |
paul@438 | 300 | return self.unit.all_local_usage + temp_position # position in frame |
paul@438 | 301 | |
paul@438 | 302 | def ensure_temp(self, instruction=None): |
paul@438 | 303 | |
paul@438 | 304 | """ |
paul@438 | 305 | Ensure that the 'instruction' is using a reserved temporary storage |
paul@438 | 306 | position. |
paul@438 | 307 | """ |
paul@438 | 308 | |
paul@438 | 309 | if isinstance(instruction, LoadTemp): |
paul@438 | 310 | temp_position = instruction.attr - self.unit.all_local_usage |
paul@438 | 311 | self.reserve_temp(temp_position) |
paul@438 | 312 | |
paul@438 | 313 | def discard_temp(self, instruction=None): |
paul@438 | 314 | |
paul@438 | 315 | "Discard any temporary storage position used by 'instruction'." |
paul@438 | 316 | |
paul@464 | 317 | if isinstance(instruction, LoadTemp) and instruction.attr is not None: |
paul@438 | 318 | temp_position = instruction.attr - self.unit.all_local_usage |
paul@438 | 319 | self.free_temp(temp_position) |
paul@469 | 320 | |
paul@469 | 321 | # Prevent any requested active value from generating instructions now |
paul@469 | 322 | # that our interest in it has passed. |
paul@469 | 323 | |
paul@469 | 324 | self.optimiser.ignore_active_value() |
paul@438 | 325 | |
paul@438 | 326 | def free_temp(self, temp_position): |
paul@438 | 327 | |
paul@438 | 328 | "Free the temporary storage position specified by 'temp_position'." |
paul@438 | 329 | |
paul@438 | 330 | if temp_position in self.temp_positions: |
paul@438 | 331 | self.temp_positions.remove(temp_position) |
paul@438 | 332 | |
paul@438 | 333 | def set_frame_usage(self, node, extend): |
paul@438 | 334 | |
paul@438 | 335 | """ |
paul@438 | 336 | Ensure that the frame usage for the unit associated with 'node' is set |
paul@438 | 337 | on the 'extend' instruction. |
paul@438 | 338 | """ |
paul@438 | 339 | |
paul@438 | 340 | # Remove any ExtendFrame instructions which do nothing. |
paul@438 | 341 | |
paul@438 | 342 | if self.last_op() is extend: |
paul@438 | 343 | self.remove_op() |
paul@438 | 344 | return |
paul@438 | 345 | |
paul@438 | 346 | ntemp = self.max_temp_position + 1 |
paul@438 | 347 | extend.attr = ntemp + node.unit.local_usage # NOTE: See get_code for similar code. |
paul@438 | 348 | |
paul@438 | 349 | # Code writing methods. |
paul@438 | 350 | |
paul@438 | 351 | def new_op(self, op): |
paul@438 | 352 | |
paul@438 | 353 | """ |
paul@438 | 354 | Add 'op' to the generated code, returning a true value if an instruction |
paul@438 | 355 | was added. |
paul@438 | 356 | """ |
paul@438 | 357 | |
paul@464 | 358 | if not self.check_op(op): |
paul@438 | 359 | return 0 |
paul@438 | 360 | |
paul@438 | 361 | # Add the operation to the current block. |
paul@438 | 362 | |
paul@438 | 363 | self.optimiser.set_new(op) |
paul@464 | 364 | self.blocks[-1].append(op) |
paul@438 | 365 | return 1 |
paul@438 | 366 | |
paul@450 | 367 | def insert_op(self, i, op): |
paul@450 | 368 | |
paul@450 | 369 | "Insert at index 'i' in the current block the instruction 'op'." |
paul@450 | 370 | |
paul@464 | 371 | if not self.check_op(op): |
paul@464 | 372 | return 0 |
paul@464 | 373 | |
paul@464 | 374 | self.blocks[-1].insert(i, op) |
paul@464 | 375 | return 1 |
paul@464 | 376 | |
paul@464 | 377 | def check_op(self, op): |
paul@464 | 378 | |
paul@464 | 379 | "Return whether the given 'op' is to be added to the code." |
paul@464 | 380 | |
paul@464 | 381 | # Optimise away temporary storage instructions where the active value is |
paul@464 | 382 | # still available and was not recorded. |
paul@464 | 383 | |
paul@464 | 384 | if isinstance(op, LoadTemp) and op.attr is None: |
paul@464 | 385 | return 0 |
paul@464 | 386 | |
paul@464 | 387 | # Optimise load operations employed by this instruction. |
paul@464 | 388 | |
paul@464 | 389 | if self.optimiser.optimise_away_no_operations(op) or self.optimiser.optimise_unused_handlers(op): |
paul@464 | 390 | return 0 |
paul@464 | 391 | |
paul@464 | 392 | return 1 |
paul@450 | 393 | |
paul@438 | 394 | def remove_op(self): |
paul@438 | 395 | |
paul@438 | 396 | "Remove the last instruction." |
paul@438 | 397 | |
paul@438 | 398 | op = self.blocks[-1].code.pop() |
paul@438 | 399 | self.optimiser.clear_active() |
paul@469 | 400 | return op |
paul@438 | 401 | |
paul@438 | 402 | def replace_op(self, op): |
paul@438 | 403 | |
paul@438 | 404 | "Replace the last added instruction with 'op'." |
paul@438 | 405 | |
paul@438 | 406 | self.remove_op() |
paul@438 | 407 | self.new_op(op) |
paul@438 | 408 | |
paul@438 | 409 | def replace_active_value(self, op): |
paul@438 | 410 | |
paul@438 | 411 | """ |
paul@438 | 412 | Replace the value-providing active instruction with 'op' if appropriate. |
paul@438 | 413 | """ |
paul@438 | 414 | |
paul@469 | 415 | removed = self.optimiser.remove_active_value() |
paul@438 | 416 | self.new_op(op) |
paul@469 | 417 | return removed |
paul@438 | 418 | |
paul@438 | 419 | def last_op(self): |
paul@438 | 420 | |
paul@438 | 421 | "Return the last added instruction." |
paul@438 | 422 | |
paul@438 | 423 | try: |
paul@438 | 424 | return self.blocks[-1].code[-1] |
paul@438 | 425 | except IndexError: |
paul@438 | 426 | return None |
paul@438 | 427 | |
paul@438 | 428 | # vim: tabstop=4 expandtab shiftwidth=4 |