8000 GH-131729: Code-gen better liveness analysis by markshannon · Pull Request #131732 · python/cpython · GitHub
[go: up one dir, main page]
Skip to content

GH-131729: Code-gen better liveness analysis #131732

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 12 commits into from
Mar 26, 2025
Merged

GH-131729: Code-gen better liveness analysis #131732

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
12 commits
Select commit Hold shift + click to select a range
45199ae
Remove redundant attribute
markshannon Mar 24, 2025
d786146
Rename 'defined' attribute to 'in_local' to more accurately reflect h…
markshannon Mar 24, 2025
2b21bf9
Remove unused function
markshannon Mar 24, 2025
66f5826
Make death of variables explicit even for array variables.
markshannon Mar 24, 2025
5d6a9f8
Remove used 'peeks' attribute
markshannon Mar 24, 2025
6e2a189
Convert in_memory from boolean to stack offset
markshannon Mar 24, 2025
417c96d
Don't apply liveness analyis to optimizer generated code
markshannon Mar 25, 2025
05a4daa
Fix RETURN_VALUE in optimizer
markshannon Mar 25, 2025
b8c3a9e
Fix up type annotations
markshannon Mar 25, 2025
d81c7de
Fixup NULLing out array items during DECREF_INPUTS
markshannon Mar 26, 2025
af5f616
Cleanup errors
markshannon Mar 26, 2025
9238a67
Update test output to reflect fix
markshannon Mar 26, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Don't apply liveness analyis to optimizer generated code
  • Loading branch information
@markshannon
markshannon committed Mar 25, 2025
commit 417c96d3c408cfb23fed7aa3d0268e9983f46b66
84 changes: 20 additions & 64 deletions Python/optimizer_cases.c.h
View file
Open in desktop

Some generated files are not rendered by default. Learn more about how customized files appear on GitHub.

2 changes: 1 addition & 1 deletion Tools/cases_generator/optimizer_generator.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -123,7 +123,7 @@ def write_uop(
try:
out.start_line()
if override:
code_list, storage = Storage.for_uop(stack, prototype)
code_list, storage = Storage.for_uop(stack, prototype, check_liveness=False)
for code in code_list:
out.emit(code)
if debug:
Expand Down
28 changes: 15 additions & 13 deletions Tools/cases_generator/stack.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -220,13 +220,14 @@ def __init__(self, extract_bits: bool=True, cast_type: str = "uintptr_t") -> Non
self.extract_bits = extract_bits
self.cast_type = cast_type

def drop(self, var: StackItem):
def drop(self, var: StackItem, check_liveness: bool):
self.top_offset.pop(var)
if self.variables:
popped = self.variables.pop()
if popped.is_dead() or not var.used:
return
raise StackError(f"Dropping live value '{var.name}'")
if check_liveness:
raise StackError(f"Dropping live value '{var.name}'")

def pop(self, var: StackItem) -> tuple[str, Local]:
self.top_offset.pop(var)
Expand Down Expand Up @@ -415,6 +416,7 @@ class Storage:
stack: Stack
inputs: list[Local]
outputs: list[Local]
check_liveness: bool
spilled: int = 0

@staticmethod
Expand All @@ -438,11 +440,11 @@ def is_live(var: Local) -> bool:
def clear_inputs(self, reason:str) -> None:
while self.inputs:
tos = self.inputs.pop()
if self.is_live(tos):
if self.is_live(tos) and self.check_liveness:
raise StackError(
f"Input '{tos.name}' is still live {reason}"
)
self.stack.drop(tos.item)
self.stack.drop(tos.item, self.check_liveness)

def clear_dead_inputs(self) -> None:
live = ""
Expand All @@ -452,7 +454,7 @@ def clear_dead_inputs(self) -> None:
live = tos.name
break
self.inputs.pop()
self.stack.drop(tos.item)
self.stack.drop(tos.item, self.check_liveness)
for var in self.inputs:
if not self.is_live(var):
raise StackError(
Expand Down Expand Up @@ -516,7 +518,7 @@ def reload(self, out: CWriter) -> None:
out.emit_reload()

@staticmethod
def for_uop(stack: Stack, uop: Uop) -> tuple[list[str], "Storage"]:
def for_uop(stack: Stack, uop: Uop, check_liveness=True) -> tuple[list[str], "Storage"]:
code_list: list[str] = []
inputs: list[Local] = []
peeks: list[Local] = []
Expand All @@ -542,7 +544,7 @@ def for_uop(stack: Stack, uop: Uop) -> tuple[list[str], "Storage"]:
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)
return code_list, Storage(stack, inputs, outputs, check_liveness)

@staticmethod
def copy_list(arg: list[Local]) -> list[Local]:
Expand All @@ -554,8 +556,8 @@ def copy(self) -> "Storage":
inputs = [ variables[var.name] for var in self.inputs]
assert [v.name for v in inputs] == [v.name for v in self.inputs], (inputs, self.inputs)
return Storage(
new_stack, inputs,
self.copy_list(self.outputs), self.spilled
new_stack, inputs, self.copy_list(self.outputs),
self.check_liveness, self.spilled
)

def sanity_check(self) -> None:
Expand Down Expand Up @@ -586,7 +588,7 @@ def merge(self, other: "Storage", out: CWriter) -> None:
if len(self.inputs) != len(other.inputs):
self.clear_dead_inputs()
other.clear_dead_inputs()
if len(self.inputs) != len(other.inputs):
if len(self.inputs) != len(other.inputs) and self.check_liveness:
diff = self.inputs[-1] if len(self.inputs) > len(other.inputs) else other.inputs[-1]
raise StackError(f"Unmergeable inputs. Differing state of '{diff.name}'")
for var, other_var in zip(self.inputs, other.inputs):
Expand All @@ -605,7 +607,7 @@ def push_outputs(self) -> None:
if self.spilled:
raise StackError(f"Unbalanced stack spills")
self.clear_inputs("at the end of the micro-op")
if self.inputs:
if self.inputs and self.check_liveness:
raise StackError(f"Input variable '{self.inputs[-1].name}' is still live")
self._push_defined_outputs()
if self.outputs:
Expand Down Expand Up @@ -682,7 +684,7 @@ def close_variable(var: Local, overwrite: str) -> None:
self.stack.push(output)
self.stack.flush(out)
close_variable(self.inputs[0], "")
self.stack.drop(output.item)
self.stack.drop(output.item, self.check_liveness)
self.inputs = []
return
if var_size(lowest) != var_size(output):
Expand All @@ -696,7 +698,7 @@ def close_variable(var: Local, overwrite: str) -> None:
close_variable(self.inputs[0], "PyStackRef_NULL")
for input in reversed(self.inputs[1:]):
input.kill()
self.stack.drop(input.item)
self.stack.drop(input.item, self.check_liveness)
self.stack.pop(self.inputs[0].item)
output_in_place = self.outputs and output is self.outputs[0] and lowest.memory_offset is not None
if output_in_place:
Expand Down
Loading
0