From c535a132e40a516a7cca219b2659e85bccaa0529 Mon Sep 17 00:00:00 2001 From: Mark Shannon Date: Mon, 31 Mar 2025 13:52:48 +0100 Subject: GH-131498: Another refactoring of the code generator (GH-131827) * Rename 'defined' attribute to 'in_local' to more accurately reflect how it is used * Make death of variables explicit even for array variables. * Convert in_memory from boolean to stack offset * Don't apply liveness analyis to optimizer generated code * Add 'out' parameter to stack.pop --- Tools/cases_generator/stack.py | 327 ++++++++++++++++++++--------------------- 1 file changed, 160 insertions(+), 167 deletions(-) (limited to 'Tools/cases_generator/stack.py') diff --git a/Tools/cases_generator/stack.py b/Tools/cases_generator/stack.py index 94a5d395064..76dfc48a6b5 100644 --- a/Tools/cases_generator/stack.py +++ b/Tools/cases_generator/stack.py @@ -30,79 +30,96 @@ def var_size(var: StackItem) -> str: @dataclass -class StackOffset: - "The stack offset of the virtual base of the stack from the physical stack pointer" - - popped: list[str] - pushed: list[str] +class PointerOffset: + """The offset of a pointer from the reference pointer + The 'reference pointer' is the address of the physical stack pointer + at the start of the code section, as if each code section started with + `const PyStackRef *reference = stack_pointer` + """ + numeric: int + positive: tuple[str, ...] + negative: tuple[str, ...] @staticmethod - def empty() -> "StackOffset": - return StackOffset([], []) + def zero() -> "PointerOffset": + return PointerOffset(0, (), ()) - def copy(self) -> "StackOffset": - return StackOffset(self.popped[:], self.pushed[:]) + def pop(self, item: StackItem) -> "PointerOffset": + return self - PointerOffset.from_item(item) - def pop(self, item: StackItem) -> None: - self.popped.append(var_size(item)) + def push(self, item: StackItem) -> "PointerOffset": + return self + PointerOffset.from_item(item) - def push(self, item: StackItem) -> None: - self.pushed.append(var_size(item)) + @staticmethod + def from_item(item: StackItem) -> "PointerOffset": + if not item.size: + return PointerOffset(1, (), ()) + txt = item.size.strip() + n: tuple[str, ...] = () + p: tuple[str, ...] = () + try: + i = int(txt) + except ValueError: + i = 0 + if txt[0] == "+": + txt = txt[1:] + if txt[0] == "-": + n = (txt[1:],) + else: + p = (txt,) + return PointerOffset(i, p, n) - def __sub__(self, other: "StackOffset") -> "StackOffset": - return StackOffset(self.popped + other.pushed, self.pushed + other.popped) + @staticmethod + def create(numeric: int, positive: tuple[str, ...], negative: tuple[str, ...]) -> "PointerOffset": + positive, negative = PointerOffset._simplify(positive, negative) + return PointerOffset(numeric, positive, negative) + + def __sub__(self, other: "PointerOffset") -> "PointerOffset": + return PointerOffset.create( + self.numeric - other.numeric, + self.positive + other.negative, + self.negative + other.positive + ) - def __neg__(self) -> "StackOffset": - return StackOffset(self.pushed, self.popped) + def __add__(self, other: "PointerOffset") -> "PointerOffset": + return PointerOffset.create( + self.numeric + other.numeric, + self.positive + other.positive, + self.negative + other.negative + ) - def simplify(self) -> None: - "Remove matching values from both the popped and pushed list" - if not self.popped: - self.pushed.sort() - return - if not self.pushed: - self.popped.sort() - return - # Sort the list so the lexically largest element is last. - popped = sorted(self.popped) - pushed = sorted(self.pushed) - self.popped = [] - self.pushed = [] - while popped and pushed: - pop = popped.pop() - push = pushed.pop() - if pop == push: - pass - elif pop > push: - # if pop > push, there can be no element in pushed matching pop. - self.popped.append(pop) - pushed.append(push) - else: - self.pushed.append(push) - popped.append(pop) - self.popped.extend(popped) - self.pushed.extend(pushed) - self.pushed.sort() - self.popped.sort() + def __neg__(self) -> "PointerOffset": + return PointerOffset(-self.numeric, self.negative, self.positive) + + @staticmethod + def _simplify(positive: tuple[str, ...], negative: tuple[str, ...]) -> tuple[tuple[str, ...], tuple[str, ...]]: + p_orig: list[str] = sorted(positive) + n_orig: list[str] = sorted(negative) + p_uniq: list[str] = [] + n_uniq: list[str] = [] + while p_orig and n_orig: + p_item = p_orig.pop() + n_item = n_orig.pop() + if p_item > n_item: + # if p_item > n_item, there can be no element in n matching p_item. + p_uniq.append(p_item) + n_orig.append(n_item) + elif p_item < n_item: + n_uniq.append(n_item) + p_orig.append(p_item) + # Otherwise they are the same and cancel each other out + return tuple(p_orig + p_uniq), tuple(n_orig + n_uniq) def to_c(self) -> str: - self.simplify() - int_offset = 0 symbol_offset = "" - for item in self.popped: - try: - int_offset -= int(item) - except ValueError: - symbol_offset += f" - {maybe_parenthesize(item)}" - for item in self.pushed: - try: - int_offset += int(item) - except ValueError: - symbol_offset += f" + {maybe_parenthesize(item)}" - if symbol_offset and not int_offset: + for item in self.negative: + symbol_offset += f" - {maybe_parenthesize(item)}" + for item in self.positive: + symbol_offset += f" + {maybe_parenthesize(item)}" + if symbol_offset and self.numeric == 0: res = symbol_offset else: - res = f"{int_offset}{symbol_offset}" + res = f"{self.numeric}{symbol_offset}" if res.startswith(" + "): res = res[3:] if res.startswith(" - "): @@ -110,53 +127,36 @@ class StackOffset: return res def as_int(self) -> int | None: - self.simplify() - int_offset = 0 - for item in self.popped: - try: - int_offset -= int(item) - except ValueError: - return None - for item in self.pushed: - try: - int_offset += int(item) - except ValueError: - return None - return int_offset - - def clear(self) -> None: - self.popped = [] - self.pushed = [] + if self.positive or self.negative: + return None + return self.numeric def __bool__(self) -> bool: - self.simplify() - return bool(self.popped) or bool(self.pushed) + return self.numeric != 0 or bool(self.positive) or bool(self.negative) - def __eq__(self, other: object) -> bool: - if not isinstance(other, StackOffset): - return NotImplemented - return self.to_c() == other.to_c() + def __str__(self) -> str: + return self.to_c() + def __repr__(self) -> str: + return f"PointerOffset({self.to_c()})" @dataclass class Local: item: StackItem - memory_offset: StackOffset | None + memory_offset: PointerOffset | None in_local: bool def __repr__(self) -> str: return f"Local('{self.item.name}', mem={self.memory_offset}, local={self.in_local}, array={self.is_array()})" - #def compact_str(self) -> str: - #mtag = "M" if self.memory_offset else "" - #dtag = "D" if self.in_local else "" - #atag = "A" if self.is_array() else "" - #return f"'{self.item.name}'{mtag}{dtag}{atag}" - - compact_str = __repr__ + def compact_str(self) -> str: + mtag = "M" if self.memory_offset else "" + dtag = "D" if self.in_local else "" + atag = "A" if self.is_array() else "" + return f"'{self.item.name}'{mtag}{dtag}{atag}" @staticmethod - def unused(defn: StackItem, offset: StackOffset) -> "Local": + def unused(defn: StackItem, offset: PointerOffset | None) -> "Local": return Local(defn, offset, False) @staticmethod @@ -164,7 +164,7 @@ class Local: return Local(defn, None, False) @staticmethod - def from_memory(defn: StackItem, offset: StackOffset) -> "Local": + def from_memory(defn: StackItem, offset: PointerOffset) -> "Local": return Local(defn, offset, True) def kill(self) -> None: @@ -213,15 +213,15 @@ def array_or_scalar(var: StackItem | Local) -> str: class Stack: def __init__(self, extract_bits: bool=True, cast_type: str = "uintptr_t") -> None: - self.top_offset = StackOffset.empty() - self.base_offset = StackOffset.empty() + self.base_offset = PointerOffset.zero() + self.physical_sp = PointerOffset.zero() + self.logical_sp = PointerOffset.zero() self.variables: list[Local] = [] - self.defined: set[str] = set() self.extract_bits = extract_bits self.cast_type = cast_type def drop(self, var: StackItem, check_liveness: bool) -> None: - self.top_offset.pop(var) + self.logical_sp = self.logical_sp.pop(var) if self.variables: popped = self.variables.pop() if popped.is_dead() or not var.used: @@ -229,8 +229,8 @@ class Stack: if check_liveness: raise StackError(f"Dropping live value '{var.name}'") - def pop(self, var: StackItem) -> tuple[str, Local]: - self.top_offset.pop(var) + def pop(self, var: StackItem, out: CWriter) -> Local: + self.logical_sp = self.logical_sp.pop(var) indirect = "&" if var.is_array() else "" if self.variables: popped = self.variables.pop() @@ -244,125 +244,122 @@ class Stack: f"Size mismatch when popping '{popped.name}' from stack to assign to '{var.name}'. " f"Expected {var_size(var)} got {var_size(popped.item)}" ) - if var.name in UNUSED: - if popped.name not in UNUSED and popped.name in self.defined: - raise StackError( - f"Value is declared unused, but is already cached by prior operation as '{popped.name}'" - ) - return "", popped if not var.used: - return "", popped - self.defined.add(var.name) + return popped if popped.name != var.name: rename = f"{var.name} = {popped.name};\n" popped.item = var else: rename = "" if not popped.in_local: - assert popped.memory_offset is not None + if popped.memory_offset is None: + popped.memory_offset = self.logical_sp + assert popped.memory_offset == self.logical_sp, (popped, self.as_comment()) + offset = popped.memory_offset.to_c() if var.is_array(): - defn = f"{var.name} = &stack_pointer[{self.top_offset.to_c()}];\n" + defn = f"{var.name} = &stack_pointer[{offset}];\n" else: - defn = f"{var.name} = stack_pointer[{self.top_offset.to_c()}];\n" + defn = f"{var.name} = stack_pointer[{offset}];\n" popped.in_local = True else: defn = rename - return defn, popped + out.emit(defn) + return popped - self.base_offset.pop(var) + self.base_offset = self.logical_sp if var.name in UNUSED or not var.used: - return "", Local.unused(var, self.base_offset) - self.defined.add(var.name) + return Local.unused(var, self.base_offset) cast = f"({var.type})" if (not indirect and var.type) else "" bits = ".bits" if cast and self.extract_bits else "" - assign = f"{var.name} = {cast}{indirect}stack_pointer[{self.base_offset.to_c()}]{bits};" - assign = f"{assign}\n" - return assign, Local.from_memory(var, self.base_offset.copy()) + offset = (self.base_offset - self.physical_sp).to_c() + assign = f"{var.name} = {cast}{indirect}stack_pointer[{offset}]{bits};\n" + out.emit(assign) + return Local.from_memory(var, self.base_offset) def push(self, var: Local) -> None: assert(var not in self.variables) self.variables.append(var) - self.top_offset.push(var.item) - if var.item.used: - self.defined.add(var.name) + self.logical_sp = self.logical_sp.push(var.item) @staticmethod def _do_emit( out: CWriter, var: StackItem, - base_offset: StackOffset, + stack_offset: PointerOffset, cast_type: str, extract_bits: bool, ) -> None: cast = f"({cast_type})" if var.type else "" bits = ".bits" if cast and extract_bits else "" - out.emit(f"stack_pointer[{base_offset.to_c()}]{bits} = {cast}{var.name};\n") + out.emit(f"stack_pointer[{stack_offset.to_c()}]{bits} = {cast}{var.name};\n") - def _adjust_stack_pointer(self, out: CWriter, number: str) -> None: - if number != "0": + def _save_physical_sp(self, out: CWriter) -> None: + if self.physical_sp != self.logical_sp: + diff = self.logical_sp - self.physical_sp out.start_line() - out.emit(f"stack_pointer += {number};\n") + out.emit(f"stack_pointer += {diff.to_c()};\n") out.emit("assert(WITHIN_STACK_BOUNDS());\n") + self.physical_sp = self.logical_sp def flush(self, out: CWriter) -> None: out.start_line() - var_offset = self.base_offset.copy() + var_offset = self.base_offset for var in self.variables: if ( var.in_local and not var.memory_offset and not var.is_array() ): - Stack._do_emit(out, var.item, var_offset, self.cast_type, self.extract_bits) - var.memory_offset = var_offset.copy() - var_offset.push(var.item) - number = self.top_offset.to_c() - self._adjust_stack_pointer(out, number) - self.base_offset -= self.top_offset - self.top_offset.clear() + var.memory_offset = var_offset + stack_offset = var_offset - self.physical_sp + Stack._do_emit(out, var.item, stack_offset, self.cast_type, self.extract_bits) + var_offset = var_offset.push(var.item) + self._save_physical_sp(out) out.start_line() def is_flushed(self) -> bool: - return not self.variables and not self.base_offset and not self.top_offset + for var in self.variables: + if not var.in_memory(): + return False + return self.physical_sp == self.logical_sp - def peek_offset(self) -> str: - return self.top_offset.to_c() + def sp_offset(self) -> str: + return (self.physical_sp - self.logical_sp).to_c() def as_comment(self) -> str: variables = ", ".join([v.compact_str() for v in self.variables]) return ( - f"/* Variables: {variables}. base: {self.base_offset.to_c()}. top: {self.top_offset.to_c()} */" + f"/* Variables: {variables}. base: {self.base_offset.to_c()}. sp: {self.physical_sp.to_c()}. logical_sp: {self.logical_sp.to_c()} */" ) def copy(self) -> "Stack": other = Stack(self.extract_bits, self.cast_type) - other.top_offset = self.top_offset.copy() - other.base_offset = self.base_offset.copy() + other.base_offset = self.base_offset + other.physical_sp = self.physical_sp + other.logical_sp = self.logical_sp other.variables = [var.copy() for var in self.variables] - other.defined = set(self.defined) return other def __eq__(self, other: object) -> bool: if not isinstance(other, Stack): return NotImplemented return ( - self.top_offset == other.top_offset + self.physical_sp == other.physical_sp + and self.logical_sp == other.logical_sp and self.base_offset == other.base_offset and self.variables == other.variables ) def align(self, other: "Stack", out: CWriter) -> None: - if len(self.variables) != len(other.variables): - raise StackError("Cannot align stacks: differing variables") - if self.top_offset == other.top_offset: + if self.logical_sp != other.logical_sp: + raise StackError("Cannot align stacks: differing logical top") + if self.physical_sp == other.physical_sp: return - diff = self.top_offset - other.top_offset - try: - self.top_offset -= diff - self.base_offset -= diff - self._adjust_stack_pointer(out, diff.to_c()) - except ValueError: - raise StackError("Cannot align stacks: cannot adjust stack pointer") + diff = other.physical_sp - self.physical_sp + out.start_line() + out.emit(f"stack_pointer += {diff.to_c()};\n") + out.emit("assert(WITHIN_STACK_BOUNDS());\n") + self.physical_sp = other.physical_sp def merge(self, other: "Stack", out: CWriter) -> None: if len(self.variables) != len(other.variables): @@ -394,15 +391,16 @@ def stacks(inst: Instruction | PseudoInstruction) -> Iterator[StackEffect]: def apply_stack_effect(stack: Stack, effect: StackEffect) -> None: locals: dict[str, Local] = {} + null = CWriter.null() for var in reversed(effect.inputs): - _, local = stack.pop(var) + local = stack.pop(var, null) if var.name != "unused": locals[local.name] = local for var in effect.outputs: if var.name in locals: local = locals[var.name] else: - local = Local.unused(var, stack.base_offset) + local = Local.unused(var, None) stack.push(local) @@ -521,13 +519,11 @@ class Storage: out.emit_reload() @staticmethod - def for_uop(stack: Stack, uop: Uop, check_liveness: bool = True) -> tuple[list[str], "Storage"]: - code_list: list[str] = [] + def for_uop(stack: Stack, uop: Uop, out: CWriter, check_liveness: bool = True) -> "Storage": inputs: list[Local] = [] peeks: list[Local] = [] for input in reversed(uop.stack.inputs): - code, local = stack.pop(input) - code_list.append(code) + local = stack.pop(input, out) if input.peek: peeks.append(local) else: @@ -536,18 +532,16 @@ class Storage: peeks.reverse() for peek in peeks: stack.push(peek) - top_offset = stack.top_offset.copy() + offset = stack.logical_sp - stack.physical_sp for ouput in uop.stack.outputs: if ouput.is_array() and ouput.used and not ouput.peek: - c_offset = top_offset.to_c() - top_offset.push(ouput) - code_list.append(f"{ouput.name} = &stack_pointer[{c_offset}];\n") - else: - top_offset.push(ouput) + c_offset = offset.to_c() + out.emit(f"{ouput.name} = &stack_pointer[{c_offset}];\n") + offset = offset.push(ouput) for var in inputs: stack.push(var) outputs = [ Local.undefined(var) for var in uop.stack.outputs if not var.peek ] - return code_list, Storage(stack, inputs, outputs, check_liveness) + return Storage(stack, inputs, outputs, check_liveness) @staticmethod def copy_list(arg: list[Local]) -> list[Local]: @@ -712,7 +706,7 @@ class Storage: self.stack.drop(self.inputs[0].item, False) output_in_place = self.outputs and output is self.outputs[0] and lowest.memory_offset is not None if output_in_place: - output.memory_offset = lowest.memory_offset.copy() # type: ignore[union-attr] + output.memory_offset = lowest.memory_offset # type: ignore[union-attr] else: self.stack.flush(out) if output is not None: @@ -721,5 +715,4 @@ class Storage: if output_in_place: self.stack.flush(out) if output is not None: - code, output = self.stack.pop(output.item) - out.emit(code) + output = self.stack.pop(output.item, out) -- cgit v1.2.3