| 1 |
import re |
| 2 |
from analyzer import StackItem, StackEffect, Instruction, Uop, PseudoInstruction |
| 3 |
from dataclasses import dataclass |
| 4 |
from cwriter import CWriter |
| 5 |
from typing import Iterator |
| 6 |
|
| 7 |
UNUSED = {"unused"} |
| 8 |
|
| 9 |
# Set this to true for voluminous output showing state of stack and locals |
| 10 |
PRINT_STACKS = False |
| 11 |
|
| 12 |
def maybe_parenthesize(sym: str) -> str: |
| 13 |
"""Add parentheses around a string if it contains an operator |
| 14 |
and is not already parenthesized. |
| 15 |
|
| 16 |
An exception is made for '*' which is common and harmless |
| 17 |
in the context where the symbolic size is used. |
| 18 |
""" |
| 19 |
if sym.startswith("(") and sym.endswith(")"): |
| 20 |
return sym |
| 21 |
if re.match(r"^[\s\w*]+$", sym): |
| 22 |
return sym |
| 23 |
else: |
| 24 |
return f"({sym})" |
| 25 |
|
| 26 |
|
| 27 |
def var_size(var: StackItem) -> str: |
| 28 |
if var.size: |
| 29 |
return var.size |
| 30 |
else: |
| 31 |
return "1" |
| 32 |
|
| 33 |
|
| 34 |
@dataclass |
| 35 |
class PointerOffset: |
| 36 |
"""The offset of a pointer from the reference pointer |
| 37 |
The 'reference pointer' is the address of the physical stack pointer |
| 38 |
at the start of the code section, as if each code section started with |
| 39 |
`const PyStackRef *reference = stack_pointer` |
| 40 |
""" |
| 41 |
numeric: int |
| 42 |
positive: tuple[str, ...] |
| 43 |
negative: tuple[str, ...] |
| 44 |
|
| 45 |
@staticmethod |
| 46 |
def zero() -> "PointerOffset": |
| 47 |
return PointerOffset(0, (), ()) |
| 48 |
|
| 49 |
def pop(self, item: StackItem) -> "PointerOffset": |
| 50 |
return self - PointerOffset.from_item(item) |
| 51 |
|
| 52 |
def push(self, item: StackItem) -> "PointerOffset": |
| 53 |
return self + PointerOffset.from_item(item) |
| 54 |
|
| 55 |
@staticmethod |
| 56 |
def from_item(item: StackItem) -> "PointerOffset": |
| 57 |
if not item.size: |
| 58 |
return PointerOffset(1, (), ()) |
| 59 |
txt = item.size.strip() |
| 60 |
n: tuple[str, ...] = () |
| 61 |
p: tuple[str, ...] = () |
| 62 |
try: |
| 63 |
i = int(txt) |
| 64 |
except ValueError: |
| 65 |
i = 0 |
| 66 |
if txt[0] == "+": |
| 67 |
txt = txt[1:] |
| 68 |
if txt[0] == "-": |
| 69 |
n = (txt[1:],) |
| 70 |
else: |
| 71 |
p = (txt,) |
| 72 |
return PointerOffset(i, p, n) |
| 73 |
|
| 74 |
@staticmethod |
| 75 |
def create(numeric: int, positive: tuple[str, ...], negative: tuple[str, ...]) -> "PointerOffset": |
| 76 |
positive, negative = PointerOffset._simplify(positive, negative) |
| 77 |
return PointerOffset(numeric, positive, negative) |
| 78 |
|
| 79 |
def __sub__(self, other: "PointerOffset") -> "PointerOffset": |
| 80 |
return PointerOffset.create( |
| 81 |
self.numeric - other.numeric, |
| 82 |
self.positive + other.negative, |
| 83 |
self.negative + other.positive |
| 84 |
) |
| 85 |
|
| 86 |
def __add__(self, other: "PointerOffset") -> "PointerOffset": |
| 87 |
return PointerOffset.create( |
| 88 |
self.numeric + other.numeric, |
| 89 |
self.positive + other.positive, |
| 90 |
self.negative + other.negative |
| 91 |
) |
| 92 |
|
| 93 |
def __neg__(self) -> "PointerOffset": |
| 94 |
return PointerOffset(-self.numeric, self.negative, self.positive) |
| 95 |
|
| 96 |
@staticmethod |
| 97 |
def _simplify(positive: tuple[str, ...], negative: tuple[str, ...]) -> tuple[tuple[str, ...], tuple[str, ...]]: |
| 98 |
p_orig: list[str] = sorted(positive) |
| 99 |
n_orig: list[str] = sorted(negative) |
| 100 |
p_uniq: list[str] = [] |
| 101 |
n_uniq: list[str] = [] |
| 102 |
while p_orig and n_orig: |
| 103 |
p_item = p_orig.pop() |
| 104 |
n_item = n_orig.pop() |
| 105 |
if p_item > n_item: |
| 106 |
# if p_item > n_item, there can be no element in n matching p_item. |
| 107 |
p_uniq.append(p_item) |
| 108 |
n_orig.append(n_item) |
| 109 |
elif p_item < n_item: |
| 110 |
n_uniq.append(n_item) |
| 111 |
p_orig.append(p_item) |
| 112 |
# Otherwise they are the same and cancel each other out |
| 113 |
return tuple(p_orig + p_uniq), tuple(n_orig + n_uniq) |
| 114 |
|
| 115 |
def to_c(self) -> str: |
| 116 |
symbol_offset = "" |
| 117 |
for item in self.negative: |
| 118 |
symbol_offset += f" - {maybe_parenthesize(item)}" |
| 119 |
for item in self.positive: |
| 120 |
symbol_offset += f" + {maybe_parenthesize(item)}" |
| 121 |
if symbol_offset and self.numeric == 0: |
| 122 |
res = symbol_offset |
| 123 |
else: |
| 124 |
res = f"{self.numeric}{symbol_offset}" |
| 125 |
if res.startswith(" + "): |
| 126 |
res = res[3:] |
| 127 |
if res.startswith(" - "): |
| 128 |
res = "-" + res[3:] |
| 129 |
return res |
| 130 |
|
| 131 |
def as_int(self) -> int | None: |
| 132 |
if self.positive or self.negative: |
| 133 |
return None |
| 134 |
return self.numeric |
| 135 |
|
| 136 |
def __str__(self) -> str: |
| 137 |
return self.to_c() |
| 138 |
|
| 139 |
def __repr__(self) -> str: |
| 140 |
return f"PointerOffset({self.to_c()})" |
| 141 |
|
| 142 |
@dataclass |
| 143 |
class Local: |
| 144 |
item: StackItem |
| 145 |
memory_offset: PointerOffset | None |
| 146 |
in_local: bool |
| 147 |
|
| 148 |
def __repr__(self) -> str: |
| 149 |
return f"Local('{self.item.name}', mem={self.memory_offset}, local={self.in_local}, array={self.is_array()})" |
| 150 |
|
| 151 |
def compact_str(self) -> str: |
| 152 |
mtag = "M" if self.memory_offset else "" |
| 153 |
dtag = "L" if self.in_local else "" |
| 154 |
atag = "A" if self.is_array() else "" |
| 155 |
return f"'{self.item.name}'{mtag}{dtag}{atag}" |
| 156 |
|
| 157 |
@staticmethod |
| 158 |
def unused(defn: StackItem, offset: PointerOffset | None) -> "Local": |
| 159 |
return Local(defn, offset, False) |
| 160 |
|
| 161 |
@staticmethod |
| 162 |
def undefined(defn: StackItem) -> "Local": |
| 163 |
return Local(defn, None, False) |
| 164 |
|
| 165 |
@staticmethod |
| 166 |
def from_memory(defn: StackItem, offset: PointerOffset) -> "Local": |
| 167 |
return Local(defn, offset, True) |
| 168 |
|
| 169 |
@staticmethod |
| 170 |
def register(name: str) -> "Local": |
| 171 |
item = StackItem(name, None, "", False, True) |
| 172 |
return Local(item, None, True) |
| 173 |
|
| 174 |
def kill(self) -> None: |
| 175 |
self.in_local = False |
| 176 |
self.memory_offset = None |
| 177 |
|
| 178 |
def in_memory(self) -> bool: |
| 179 |
return self.memory_offset is not None or self.is_array() |
| 180 |
|
| 181 |
def is_dead(self) -> bool: |
| 182 |
return not self.in_local and self.memory_offset is None |
| 183 |
|
| 184 |
def copy(self) -> "Local": |
| 185 |
return Local( |
| 186 |
self.item, |
| 187 |
self.memory_offset, |
| 188 |
self.in_local |
| 189 |
) |
| 190 |
|
| 191 |
@property |
| 192 |
def size(self) -> str: |
| 193 |
return self.item.size |
| 194 |
|
| 195 |
@property |
| 196 |
def name(self) -> str: |
| 197 |
return self.item.name |
| 198 |
|
| 199 |
def is_array(self) -> bool: |
| 200 |
return self.item.is_array() |
| 201 |
|
| 202 |
def __eq__(self, other: object) -> bool: |
| 203 |
if not isinstance(other, Local): |
| 204 |
return NotImplemented |
| 205 |
return ( |
| 206 |
self.item is other.item |
| 207 |
and self.memory_offset == other.memory_offset |
| 208 |
and self.in_local == other.in_local |
| 209 |
) |
| 210 |
|
| 211 |
|
| 212 |
class StackError(Exception): |
| 213 |
pass |
| 214 |
|
| 215 |
def array_or_scalar(var: StackItem | Local) -> str: |
| 216 |
return "array" if var.is_array() else "scalar" |
| 217 |
|
| 218 |
class Stack: |
| 219 |
def __init__(self, extract_bits: bool=True, cast_type: str = "uintptr_t") -> None: |
| 220 |
self.base_offset = PointerOffset.zero() |
| 221 |
self.physical_sp = PointerOffset.zero() |
| 222 |
self.logical_sp = PointerOffset.zero() |
| 223 |
self.variables: list[Local] = [] |
| 224 |
self.extract_bits = extract_bits |
| 225 |
self.cast_type = cast_type |
| 226 |
|
| 227 |
def drop(self, var: StackItem, check_liveness: bool) -> None: |
| 228 |
self.logical_sp = self.logical_sp.pop(var) |
| 229 |
if self.variables: |
| 230 |
popped = self.variables.pop() |
| 231 |
if popped.is_dead() or not var.used: |
| 232 |
return |
| 233 |
if check_liveness: |
| 234 |
raise StackError(f"Dropping live value '{var.name}'") |
| 235 |
|
| 236 |
def pop(self, var: StackItem, out: CWriter) -> Local: |
| 237 |
if self.variables: |
| 238 |
top = self.variables[-1] |
| 239 |
if var.is_array() != top.is_array() or top.size != var.size: |
| 240 |
# Mismatch in variables |
| 241 |
self.clear(out) |
| 242 |
self.logical_sp = self.logical_sp.pop(var) |
| 243 |
indirect = "&" if var.is_array() else "" |
| 244 |
if self.variables: |
| 245 |
popped = self.variables.pop() |
| 246 |
assert var.is_array() == popped.is_array() and popped.size == var.size |
| 247 |
if not var.used: |
| 248 |
return popped |
| 249 |
if popped.name != var.name: |
| 250 |
rename = f"{var.name} = {popped.name};\n" |
| 251 |
popped.item = var |
| 252 |
else: |
| 253 |
rename = "" |
| 254 |
if not popped.in_local: |
| 255 |
if popped.memory_offset is None: |
| 256 |
popped.memory_offset = self.logical_sp |
| 257 |
assert popped.memory_offset == self.logical_sp, (popped, self.as_comment()) |
| 258 |
offset = popped.memory_offset - self.physical_sp |
| 259 |
if var.is_array(): |
| 260 |
defn = f"{var.name} = &stack_pointer[{offset.to_c()}];\n" |
| 261 |
else: |
| 262 |
defn = f"{var.name} = stack_pointer[{offset.to_c()}];\n" |
| 263 |
popped.in_local = True |
| 264 |
else: |
| 265 |
defn = rename |
| 266 |
out.emit(defn) |
| 267 |
return popped |
| 268 |
self.base_offset = self.logical_sp |
| 269 |
if var.name in UNUSED or not var.used: |
| 270 |
return Local.unused(var, self.base_offset) |
| 271 |
cast = f"({var.type})" if (not indirect and var.type) else "" |
| 272 |
bits = ".bits" if cast and self.extract_bits else "" |
| 273 |
c_offset = (self.base_offset - self.physical_sp).to_c() |
| 274 |
assign = f"{var.name} = {cast}{indirect}stack_pointer[{c_offset}]{bits};\n" |
| 275 |
out.emit(assign) |
| 276 |
self._print(out) |
| 277 |
return Local.from_memory(var, self.base_offset) |
| 278 |
|
| 279 |
def clear(self, out: CWriter) -> None: |
| 280 |
"Flush to memory and clear variables stack" |
| 281 |
self.flush(out) |
| 282 |
self.variables = [] |
| 283 |
self.base_offset = self.logical_sp |
| 284 |
|
| 285 |
def push(self, var: Local) -> None: |
| 286 |
assert(var not in self.variables), var |
| 287 |
self.variables.append(var) |
| 288 |
self.logical_sp = self.logical_sp.push(var.item) |
| 289 |
|
| 290 |
@staticmethod |
| 291 |
def _do_emit( |
| 292 |
out: CWriter, |
| 293 |
var: StackItem, |
| 294 |
stack_offset: PointerOffset, |
| 295 |
cast_type: str, |
| 296 |
extract_bits: bool, |
| 297 |
) -> None: |
| 298 |
cast = f"({cast_type})" if var.type else "" |
| 299 |
bits = ".bits" if cast and extract_bits else "" |
| 300 |
out.emit(f"stack_pointer[{stack_offset.to_c()}]{bits} = {cast}{var.name};\n") |
| 301 |
|
| 302 |
def _save_physical_sp(self, out: CWriter) -> None: |
| 303 |
if self.physical_sp != self.logical_sp: |
| 304 |
diff = self.logical_sp - self.physical_sp |
| 305 |
out.start_line() |
| 306 |
out.emit(f"stack_pointer += {diff.to_c()};\n") |
| 307 |
out.emit(f"assert(WITHIN_STACK_BOUNDS());\n") |
| 308 |
self.physical_sp = self.logical_sp |
| 309 |
self._print(out) |
| 310 |
|
| 311 |
def save_variables(self, out: CWriter) -> None: |
| 312 |
out.start_line() |
| 313 |
var_offset = self.base_offset |
| 314 |
for var in self.variables: |
| 315 |
if ( |
| 316 |
var.in_local and |
| 317 |
not var.memory_offset and |
| 318 |
not var.is_array() |
| 319 |
): |
| 320 |
self._print(out) |
| 321 |
var.memory_offset = var_offset |
| 322 |
stack_offset = var_offset - self.physical_sp |
| 323 |
Stack._do_emit(out, var.item, stack_offset, self.cast_type, self.extract_bits) |
| 324 |
self._print(out) |
| 325 |
var_offset = var_offset.push(var.item) |
| 326 |
|
| 327 |
def flush(self, out: CWriter) -> None: |
| 328 |
self._print(out) |
| 329 |
self.save_variables(out) |
| 330 |
self._save_physical_sp(out) |
| 331 |
out.start_line() |
| 332 |
|
| 333 |
def is_flushed(self) -> bool: |
| 334 |
for var in self.variables: |
| 335 |
if not var.in_memory(): |
| 336 |
return False |
| 337 |
return self.physical_sp == self.logical_sp |
| 338 |
|
| 339 |
def sp_offset(self) -> str: |
| 340 |
return (self.physical_sp - self.logical_sp).to_c() |
| 341 |
|
| 342 |
def as_comment(self) -> str: |
| 343 |
variables = ", ".join([v.compact_str() for v in self.variables]) |
| 344 |
return ( |
| 345 |
f"/* Variables=[{variables}]; base={self.base_offset.to_c()}; sp={self.physical_sp.to_c()}; logical_sp={self.logical_sp.to_c()} */" |
| 346 |
) |
| 347 |
|
| 348 |
def _print(self, out: CWriter) -> None: |
| 349 |
if PRINT_STACKS: |
| 350 |
out.emit(self.as_comment() + "\n") |
| 351 |
|
| 352 |
def copy(self) -> "Stack": |
| 353 |
other = Stack(self.extract_bits, self.cast_type) |
| 354 |
other.base_offset = self.base_offset |
| 355 |
other.physical_sp = self.physical_sp |
| 356 |
other.logical_sp = self.logical_sp |
| 357 |
other.variables = [var.copy() for var in self.variables] |
| 358 |
return other |
| 359 |
|
| 360 |
def __eq__(self, other: object) -> bool: |
| 361 |
if not isinstance(other, Stack): |
| 362 |
return NotImplemented |
| 363 |
return ( |
| 364 |
self.physical_sp == other.physical_sp |
| 365 |
and self.logical_sp == other.logical_sp |
| 366 |
and self.base_offset == other.base_offset |
| 367 |
and self.variables == other.variables |
| 368 |
) |
| 369 |
|
| 370 |
def align(self, other: "Stack", out: CWriter) -> None: |
| 371 |
if self.logical_sp != other.logical_sp: |
| 372 |
raise StackError("Cannot align stacks: differing logical top") |
| 373 |
if self.physical_sp == other.physical_sp: |
| 374 |
return |
| 375 |
diff = other.physical_sp - self.physical_sp |
| 376 |
out.start_line() |
| 377 |
out.emit(f"stack_pointer += {diff.to_c()};\n") |
| 378 |
self.physical_sp = other.physical_sp |
| 379 |
|
| 380 |
def merge(self, other: "Stack", out: CWriter) -> None: |
| 381 |
if len(self.variables) != len(other.variables): |
| 382 |
raise StackError("Cannot merge stacks: differing variables") |
| 383 |
for self_var, other_var in zip(self.variables, other.variables): |
| 384 |
if self_var.name != other_var.name: |
| 385 |
raise StackError(f"Mismatched variables on stack: {self_var.name} and {other_var.name}") |
| 386 |
self_var.in_local = self_var.in_local and other_var.in_local |
| 387 |
if other_var.memory_offset is None: |
| 388 |
self_var.memory_offset = None |
| 389 |
self.align(other, out) |
| 390 |
for self_var, other_var in zip(self.variables, other.variables): |
| 391 |
if self_var.memory_offset is not None: |
| 392 |
if self_var.memory_offset != other_var.memory_offset: |
| 393 |
raise StackError(f"Mismatched stack depths for {self_var.name}: {self_var.memory_offset} and {other_var.memory_offset}") |
| 394 |
elif other_var.memory_offset is None: |
| 395 |
self_var.memory_offset = None |
| 396 |
|
| 397 |
|
| 398 |
def stacks(inst: Instruction | PseudoInstruction) -> Iterator[StackEffect]: |
| 399 |
if isinstance(inst, Instruction): |
| 400 |
for uop in inst.parts: |
| 401 |
if isinstance(uop, Uop): |
| 402 |
yield uop.stack |
| 403 |
else: |
| 404 |
assert isinstance(inst, PseudoInstruction) |
| 405 |
yield inst.stack |
| 406 |
|
| 407 |
|
| 408 |
def apply_stack_effect(stack: Stack, effect: StackEffect) -> None: |
| 409 |
locals: dict[str, Local] = {} |
| 410 |
null = CWriter.null() |
| 411 |
for var in reversed(effect.inputs): |
| 412 |
local = stack.pop(var, null) |
| 413 |
if var.name != "unused": |
| 414 |
locals[local.name] = local |
| 415 |
for var in effect.outputs: |
| 416 |
if var.name in locals: |
| 417 |
local = locals[var.name] |
| 418 |
else: |
| 419 |
local = Local.unused(var, None) |
| 420 |
stack.push(local) |
| 421 |
|
| 422 |
|
| 423 |
def get_stack_effect(inst: Instruction | PseudoInstruction) -> Stack: |
| 424 |
stack = Stack() |
| 425 |
for s in stacks(inst): |
| 426 |
apply_stack_effect(stack, s) |
| 427 |
return stack |
| 428 |
|
| 429 |
|
| 430 |
@dataclass |
| 431 |
class Storage: |
| 432 |
|
| 433 |
stack: Stack |
| 434 |
inputs: list[Local] |
| 435 |
outputs: list[Local] |
| 436 |
peeks: int |
| 437 |
check_liveness: bool |
| 438 |
spilled: int = 0 |
| 439 |
|
| 440 |
@staticmethod |
| 441 |
def needs_defining(var: Local) -> bool: |
| 442 |
return ( |
| 443 |
not var.item.peek and |
| 444 |
not var.in_local and |
| 445 |
not var.is_array() and |
| 446 |
var.name != "unused" |
| 447 |
) |
| 448 |
|
| 449 |
@staticmethod |
| 450 |
def is_live(var: Local) -> bool: |
| 451 |
return ( |
| 452 |
var.name != "unused" and |
| 453 |
( |
| 454 |
var.in_local or |
| 455 |
var.memory_offset is not None |
| 456 |
) |
| 457 |
) |
| 458 |
|
| 459 |
def clear_inputs(self, reason:str) -> None: |
| 460 |
while len(self.inputs) > self.peeks: |
| 461 |
tos = self.inputs.pop() |
| 462 |
if self.is_live(tos) and self.check_liveness: |
| 463 |
raise StackError( |
| 464 |
f"Input '{tos.name}' is still live {reason}" |
| 465 |
) |
| 466 |
self.stack.drop(tos.item, self.check_liveness) |
| 467 |
|
| 468 |
def clear_dead_inputs(self) -> None: |
| 469 |
live = "" |
| 470 |
while len(self.inputs) > self.peeks: |
| 471 |
tos = self.inputs[-1] |
| 472 |
if self.is_live(tos): |
| 473 |
live = tos.name |
| 474 |
break |
| 475 |
self.inputs.pop() |
| 476 |
self.stack.drop(tos.item, self.check_liveness) |
| 477 |
for var in self.inputs[self.peeks:]: |
| 478 |
if not self.is_live(var): |
| 479 |
raise StackError( |
| 480 |
f"Input '{var.name}' is not live, but '{live}' is" |
| 481 |
) |
| 482 |
|
| 483 |
def _push_defined_outputs(self) -> None: |
| 484 |
defined_output = "" |
| 485 |
for output in self.outputs: |
| 486 |
if output.in_local and not output.memory_offset: |
| 487 |
defined_output = output.name |
| 488 |
if not defined_output: |
| 489 |
return |
| 490 |
self.clear_inputs(f"when output '{defined_output}' is defined") |
| 491 |
undefined = "" |
| 492 |
for out in self.outputs: |
| 493 |
if out.in_local: |
| 494 |
if undefined: |
| 495 |
f"Locals not defined in stack order. " |
| 496 |
f"Expected '{undefined}' to be defined before '{out.name}'" |
| 497 |
else: |
| 498 |
undefined = out.name |
| 499 |
while len(self.outputs) > self.peeks and not self.needs_defining(self.outputs[0]): |
| 500 |
out = self.outputs.pop(self.peeks) |
| 501 |
self.stack.push(out) |
| 502 |
|
| 503 |
def locals_cached(self) -> bool: |
| 504 |
for out in self.outputs: |
| 505 |
if out.in_local: |
| 506 |
return True |
| 507 |
return False |
| 508 |
|
| 509 |
def flush(self, out: CWriter) -> None: |
| 510 |
self.clear_dead_inputs() |
| 511 |
self._push_defined_outputs() |
| 512 |
self.stack.flush(out) |
| 513 |
|
| 514 |
def save(self, out: CWriter) -> None: |
| 515 |
assert self.spilled >= 0 |
| 516 |
if self.spilled == 0: |
| 517 |
out.start_line() |
| 518 |
out.emit_spill() |
| 519 |
self.spilled += 1 |
| 520 |
|
| 521 |
def save_inputs(self, out: CWriter) -> None: |
| 522 |
assert self.spilled >= 0 |
| 523 |
if self.spilled == 0: |
| 524 |
self.clear_dead_inputs() |
| 525 |
self.stack.flush(out) |
| 526 |
out.start_line() |
| 527 |
out.emit_spill() |
| 528 |
self.spilled += 1 |
| 529 |
|
| 530 |
def reload(self, out: CWriter) -> None: |
| 531 |
if self.spilled == 0: |
| 532 |
raise StackError("Cannot reload stack as it hasn't been saved") |
| 533 |
assert self.spilled > 0 |
| 534 |
self.spilled -= 1 |
| 535 |
if self.spilled == 0: |
| 536 |
out.start_line() |
| 537 |
out.emit_reload() |
| 538 |
|
| 539 |
@staticmethod |
| 540 |
def for_uop(stack: Stack, uop: Uop, out: CWriter, check_liveness: bool = True) -> "Storage": |
| 541 |
inputs: list[Local] = [] |
| 542 |
peeks: list[Local] = [] |
| 543 |
for input in reversed(uop.stack.inputs): |
| 544 |
local = stack.pop(input, out) |
| 545 |
if input.peek: |
| 546 |
peeks.append(local) |
| 547 |
inputs.append(local) |
| 548 |
inputs.reverse() |
| 549 |
peeks.reverse() |
| 550 |
offset = stack.logical_sp - stack.physical_sp |
| 551 |
for ouput in uop.stack.outputs: |
| 552 |
if ouput.is_array() and ouput.used and not ouput.peek: |
| 553 |
c_offset = offset.to_c() |
| 554 |
out.emit(f"{ouput.name} = &stack_pointer[{c_offset}];\n") |
| 555 |
offset = offset.push(ouput) |
| 556 |
for var in inputs: |
| 557 |
stack.push(var) |
| 558 |
outputs = peeks + [ Local.undefined(var) for var in uop.stack.outputs if not var.peek ] |
| 559 |
return Storage(stack, inputs, outputs, len(peeks), check_liveness) |
| 560 |
|
| 561 |
@staticmethod |
| 562 |
def copy_list(arg: list[Local]) -> list[Local]: |
| 563 |
return [ l.copy() for l in arg ] |
| 564 |
|
| 565 |
def copy(self) -> "Storage": |
| 566 |
new_stack = self.stack.copy() |
| 567 |
variables = { var.name: var for var in new_stack.variables } |
| 568 |
inputs = [ variables[var.name] for var in self.inputs] |
| 569 |
assert [v.name for v in inputs] == [v.name for v in self.inputs], (inputs, self.inputs) |
| 570 |
return Storage( |
| 571 |
new_stack, inputs, self.copy_list(self.outputs), self.peeks, |
| 572 |
self.check_liveness, self.spilled |
| 573 |
) |
| 574 |
|
| 575 |
@staticmethod |
| 576 |
def check_names(locals: list[Local]) -> None: |
| 577 |
names: set[str] = set() |
| 578 |
for var in locals: |
| 579 |
if var.name == "unused": |
| 580 |
continue |
| 581 |
if var.name in names: |
| 582 |
raise StackError(f"Duplicate name {var.name}") |
| 583 |
names.add(var.name) |
| 584 |
|
| 585 |
def sanity_check(self) -> None: |
| 586 |
self.check_names(self.inputs) |
| 587 |
self.check_names(self.outputs) |
| 588 |
self.check_names(self.stack.variables) |
| 589 |
|
| 590 |
def is_flushed(self) -> bool: |
| 591 |
for var in self.outputs: |
| 592 |
if var.in_local and not var.memory_offset: |
| 593 |
return False |
| 594 |
return self.stack.is_flushed() |
| 595 |
|
| 596 |
def merge(self, other: "Storage", out: CWriter) -> None: |
| 597 |
self.sanity_check() |
| 598 |
if len(self.inputs) != len(other.inputs): |
| 599 |
self.clear_dead_inputs() |
| 600 |
other.clear_dead_inputs() |
| 601 |
if len(self.inputs) != len(other.inputs) and self.check_liveness: |
| 602 |
diff = self.inputs[-1] if len(self.inputs) > len(other.inputs) else other.inputs[-1] |
| 603 |
self._print(out) |
| 604 |
other._print(out) |
| 605 |
raise StackError(f"Unmergeable inputs. Differing state of '{diff.name}'") |
| 606 |
for var, other_var in zip(self.inputs, other.inputs): |
| 607 |
if var.in_local != other_var.in_local: |
| 608 |
raise StackError(f"'{var.name}' is cleared on some paths, but not all") |
| 609 |
if len(self.outputs) != len(other.outputs): |
| 610 |
self._push_defined_outputs() |
| 611 |
other._push_defined_outputs() |
| 612 |
if len(self.outputs) != len(other.outputs): |
| 613 |
var = self.outputs[0] if len(self.outputs) > len(other.outputs) else other.outputs[0] |
| 614 |
raise StackError(f"'{var.name}' is set on some paths, but not all") |
| 615 |
for var, other_var in zip(self.outputs, other.outputs): |
| 616 |
if var.memory_offset is None: |
| 617 |
other_var.memory_offset = None |
| 618 |
elif other_var.memory_offset is None: |
| 619 |
var.memory_offset = None |
| 620 |
self.stack.merge(other.stack, out) |
| 621 |
self.sanity_check() |
| 622 |
|
| 623 |
def push_outputs(self) -> None: |
| 624 |
if self.spilled: |
| 625 |
raise StackError(f"Unbalanced stack spills") |
| 626 |
self.clear_inputs("at the end of the micro-op") |
| 627 |
if len(self.inputs) > self.peeks and self.check_liveness: |
| 628 |
raise StackError(f"Input variable '{self.inputs[-1].name}' is still live") |
| 629 |
self._push_defined_outputs() |
| 630 |
if self.outputs: |
| 631 |
for out in self.outputs[self.peeks:]: |
| 632 |
if self.needs_defining(out): |
| 633 |
raise StackError(f"Output variable '{self.outputs[0].name}' is not defined") |
| 634 |
self.stack.push(out) |
| 635 |
self.outputs = [] |
| 636 |
|
| 637 |
def as_comment(self) -> str: |
| 638 |
stack_comment = self.stack.as_comment() |
| 639 |
next_line = "\n " |
| 640 |
inputs = ", ".join([var.compact_str() for var in self.inputs]) |
| 641 |
outputs = ", ".join([var.compact_str() for var in self.outputs]) |
| 642 |
return f"{stack_comment[:-2]}{next_line}inputs: {inputs} outputs: {outputs}*/" |
| 643 |
|
| 644 |
def _print(self, out: CWriter) -> None: |
| 645 |
if PRINT_STACKS: |
| 646 |
out.emit(self.as_comment() + "\n") |
| 647 |
|
| 648 |
def close_inputs(self, out: CWriter) -> None: |
| 649 |
|
| 650 |
tmp_defined = False |
| 651 |
def close_named(close: str, name: str, overwrite: str) -> None: |
| 652 |
nonlocal tmp_defined |
| 653 |
if overwrite: |
| 654 |
if not tmp_defined: |
| 655 |
out.emit("_PyStackRef ") |
| 656 |
tmp_defined = True |
| 657 |
out.emit(f"tmp = {name};\n") |
| 658 |
out.emit(f"{name} = {overwrite};\n") |
| 659 |
self.stack.save_variables(out) |
| 660 |
out.emit(f"{close}(tmp);\n") |
| 661 |
else: |
| 662 |
out.emit(f"{close}({name});\n") |
| 663 |
|
| 664 |
def close_variable(var: Local, overwrite: str) -> None: |
| 665 |
nonlocal tmp_defined |
| 666 |
close = "PyStackRef_CLOSE" |
| 667 |
if "null" in var.name: |
| 668 |
close = "PyStackRef_XCLOSE" |
| 669 |
var.memory_offset = None |
| 670 |
self.save(out) |
| 671 |
out.start_line() |
| 672 |
if var.size: |
| 673 |
if var.size == "1": |
| 674 |
close_named(close, f"{var.name}[0]", overwrite) |
| 675 |
else: |
| 676 |
if overwrite and not tmp_defined: |
| 677 |
out.emit("_PyStackRef tmp;\n") |
| 678 |
tmp_defined = True |
| 679 |
out.emit(f"for (int _i = {var.size}; --_i >= 0;) {{\n") |
| 680 |
close_named(close, f"{var.name}[_i]", overwrite) |
| 681 |
out.emit("}\n") |
| 682 |
else: |
| 683 |
close_named(close, var.name, overwrite) |
| 684 |
self.reload(out) |
| 685 |
|
| 686 |
self.clear_dead_inputs() |
| 687 |
if not self.inputs: |
| 688 |
return |
| 689 |
lowest = self.inputs[0] |
| 690 |
output: Local | None = None |
| 691 |
for var in self.outputs: |
| 692 |
if var.is_array(): |
| 693 |
if len(self.inputs) > 1: |
| 694 |
raise StackError("Cannot call DECREF_INPUTS with array output and more than one input") |
| 695 |
output = var |
| 696 |
elif var.in_local: |
| 697 |
if output is not None: |
| 698 |
raise StackError("Cannot call DECREF_INPUTS with more than one live output") |
| 699 |
output = var |
| 700 |
if output is not None: |
| 701 |
if output.is_array(): |
| 702 |
assert len(self.inputs) == 1 |
| 703 |
self.stack.drop(self.inputs[0].item, False) |
| 704 |
self.stack.push(output) |
| 705 |
self.stack.flush(out) |
| 706 |
close_variable(self.inputs[0], "") |
| 707 |
self.stack.drop(output.item, self.check_liveness) |
| 708 |
self.inputs = [] |
| 709 |
return |
| 710 |
if var_size(lowest.item) != var_size(output.item): |
| 711 |
raise StackError("Cannot call DECREF_INPUTS with live output not matching first input size") |
| 712 |
self.stack.flush(out) |
| 713 |
lowest.in_local = True |
| 714 |
close_variable(lowest, output.name) |
| 715 |
assert lowest.memory_offset is not None |
| 716 |
for input in reversed(self.inputs[1:]): |
| 717 |
close_variable(input, "PyStackRef_NULL") |
| 718 |
if output is None: |
| 719 |
close_variable(self.inputs[0], "PyStackRef_NULL") |
| 720 |
for input in reversed(self.inputs[1:]): |
| 721 |
input.kill() |
| 722 |
self.stack.drop(input.item, self.check_liveness) |
| 723 |
if output is None: |
| 724 |
self.inputs[0].kill() |
| 725 |
self.stack.drop(self.inputs[0].item, False) |
| 726 |
output_in_place = self.outputs and output is self.outputs[0] and lowest.memory_offset is not None |
| 727 |
if output_in_place: |
| 728 |
output.memory_offset = lowest.memory_offset # type: ignore[union-attr] |
| 729 |
else: |
| 730 |
self.stack.flush(out) |
| 731 |
if output is not None: |
| 732 |
self.stack.push(output) |
| 733 |
self.inputs = [] |
| 734 |
if output_in_place: |
| 735 |
self.stack.flush(out) |
| 736 |
if output is not None: |
| 737 |
output = self.stack.pop(output.item, out) |