summaryrefslogtreecommitdiffstats
path: root/Tools
diff options
context:
space:
mode:
authormpage <mpage@meta.com>2024-11-26 00:53:49 (GMT)
committerGitHub <noreply@github.com>2024-11-26 00:53:49 (GMT)
commit193890c1ccab4b398a218c6c8e91831477aa2ebb (patch)
tree28dc52defa3f5059b964dbcd3657dec47f88d2dd /Tools
parent26ff32b30553e1f7b0cc822835ad2da8890c180c (diff)
downloadcpython-193890c1ccab4b398a218c6c8e91831477aa2ebb.zip
cpython-193890c1ccab4b398a218c6c8e91831477aa2ebb.tar.gz
cpython-193890c1ccab4b398a218c6c8e91831477aa2ebb.tar.bz2
gh-126612: Include stack effects of uops when computing maximum stack depth (#126894)
Diffstat (limited to 'Tools')
-rw-r--r--Tools/cases_generator/opcode_metadata_generator.py98
-rw-r--r--Tools/cases_generator/stack.py58
2 files changed, 134 insertions, 22 deletions
diff --git a/Tools/cases_generator/opcode_metadata_generator.py b/Tools/cases_generator/opcode_metadata_generator.py
index 2ad7604..1a9849c 100644
--- a/Tools/cases_generator/opcode_metadata_generator.py
+++ b/Tools/cases_generator/opcode_metadata_generator.py
@@ -19,8 +19,9 @@ from generators_common import (
cflags,
)
from cwriter import CWriter
+from dataclasses import dataclass
from typing import TextIO
-from stack import get_stack_effect
+from stack import Stack, get_stack_effect, get_stack_effects
# Constants used instead of size for macro expansions.
# Note: 1, 2, 4 must match actual cache entry sizes.
@@ -107,6 +108,101 @@ def generate_stack_effect_functions(analysis: Analysis, out: CWriter) -> None:
emit_stack_effect_function(out, "popped", sorted(popped_data))
emit_stack_effect_function(out, "pushed", sorted(pushed_data))
+ generate_max_stack_effect_function(analysis, out)
+
+
+def emit_max_stack_effect_function(
+ out: CWriter, effects: list[tuple[str, list[str]]]
+) -> None:
+ out.emit("extern int _PyOpcode_max_stack_effect(int opcode, int oparg, int *effect);\n")
+ out.emit("#ifdef NEED_OPCODE_METADATA\n")
+ out.emit(f"int _PyOpcode_max_stack_effect(int opcode, int oparg, int *effect) {{\n")
+ out.emit("switch(opcode) {\n")
+ for name, exprs in effects:
+ out.emit(f"case {name}: {{\n")
+ if len(exprs) == 1:
+ out.emit(f"*effect = {exprs[0]};\n")
+ elif len(exprs) == 2:
+ out.emit(f"*effect = Py_MAX({exprs[0]}, {exprs[1]});\n")
+ else:
+ assert len(exprs) > 2
+ out.emit(f"int max_eff = Py_MAX({exprs[0]}, {exprs[1]});\n")
+ for expr in exprs[2:]:
+ out.emit(f"max_eff = Py_MAX(max_eff, {expr});\n")
+ out.emit(f"*effect = max_eff;\n")
+ out.emit(f"return 0;\n")
+ out.emit("}\n")
+ out.emit("default:\n")
+ out.emit(" return -1;\n")
+ out.emit("}\n")
+ out.emit("}\n\n")
+ out.emit("#endif\n\n")
+
+
+@dataclass
+class MaxStackEffectSet:
+ int_effect: int | None
+ cond_effects: set[str]
+
+ def __init__(self) -> None:
+ self.int_effect = None
+ self.cond_effects = set()
+
+ def add(self, stack: Stack) -> None:
+ top_off = stack.top_offset
+ top_off_int = top_off.as_int()
+ if top_off_int is not None:
+ if self.int_effect is None or top_off_int > self.int_effect:
+ self.int_effect = top_off_int
+ else:
+ self.cond_effects.add(top_off.to_c())
+
+ def update(self, other: "MaxStackEffectSet") -> None:
+ if self.int_effect is None:
+ if other.int_effect is not None:
+ self.int_effect = other.int_effect
+ elif other.int_effect is not None:
+ self.int_effect = max(self.int_effect, other.int_effect)
+ self.cond_effects.update(other.cond_effects)
+
+
+def generate_max_stack_effect_function(analysis: Analysis, out: CWriter) -> None:
+ """Generate a function that returns the maximum stack effect of an
+ instruction while it is executing.
+
+ Specialized instructions that are composed of uops may have a greater stack
+ effect during instruction execution than the net stack effect of the
+ instruction if the uops pass values on the stack.
+ """
+ effects: dict[str, MaxStackEffectSet] = {}
+
+ def add(inst: Instruction | PseudoInstruction) -> None:
+ inst_effect = MaxStackEffectSet()
+ for stack in get_stack_effects(inst):
+ inst_effect.add(stack)
+ effects[inst.name] = inst_effect
+
+ # Collect unique stack effects for each instruction
+ for inst in analysis.instructions.values():
+ add(inst)
+ for pseudo in analysis.pseudos.values():
+ add(pseudo)
+
+ # Merge the effects of all specializations in a family into the generic
+ # instruction
+ for family in analysis.families.values():
+ for inst in family.members:
+ effects[family.name].update(effects[inst.name])
+
+ data: list[tuple[str, list[str]]] = []
+ for name, effs in sorted(effects.items(), key=lambda kv: kv[0]):
+ exprs = []
+ if effs.int_effect is not None:
+ exprs.append(str(effs.int_effect))
+ exprs.extend(sorted(effs.cond_effects))
+ data.append((name, exprs))
+ emit_max_stack_effect_function(out, data)
+
def generate_is_pseudo(analysis: Analysis, out: CWriter) -> None:
"""Write the IS_PSEUDO_INSTR macro"""
diff --git a/Tools/cases_generator/stack.py b/Tools/cases_generator/stack.py
index a954bed..286f47d 100644
--- a/Tools/cases_generator/stack.py
+++ b/Tools/cases_generator/stack.py
@@ -1,8 +1,9 @@
import re
from analyzer import StackItem, StackEffect, Instruction, Uop, PseudoInstruction
+from collections import defaultdict
from dataclasses import dataclass
from cwriter import CWriter
-from typing import Iterator
+from typing import Iterator, Tuple
UNUSED = {"unused"}
@@ -385,31 +386,46 @@ class Stack:
self.align(other, out)
+def stacks(inst: Instruction | PseudoInstruction) -> Iterator[StackEffect]:
+ if isinstance(inst, Instruction):
+ for uop in inst.parts:
+ if isinstance(uop, Uop):
+ yield uop.stack
+ else:
+ assert isinstance(inst, PseudoInstruction)
+ yield inst.stack
+
+
+def apply_stack_effect(stack: Stack, effect: StackEffect) -> None:
+ locals: dict[str, Local] = {}
+ for var in reversed(effect.inputs):
+ _, local = stack.pop(var)
+ 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.push(local)
+
+
def get_stack_effect(inst: Instruction | PseudoInstruction) -> Stack:
stack = Stack()
+ for s in stacks(inst):
+ apply_stack_effect(stack, s)
+ return stack
- def stacks(inst: Instruction | PseudoInstruction) -> Iterator[StackEffect]:
- if isinstance(inst, Instruction):
- for uop in inst.parts:
- if isinstance(uop, Uop):
- yield uop.stack
- else:
- assert isinstance(inst, PseudoInstruction)
- yield inst.stack
+def get_stack_effects(inst: Instruction | PseudoInstruction) -> list[Stack]:
+ """Returns a list of stack effects after each uop"""
+ result = []
+ stack = Stack()
for s in stacks(inst):
- locals: dict[str, Local] = {}
- for var in reversed(s.inputs):
- _, local = stack.pop(var)
- if var.name != "unused":
- locals[local.name] = local
- for var in s.outputs:
- if var.name in locals:
- local = locals[var.name]
- else:
- local = Local.unused(var)
- stack.push(local)
- return stack
+ apply_stack_effect(stack, s)
+ result.append(stack.copy())
+ return result
+
@dataclass
class Storage: