zzgandClaude Opus 5.5
2a3a0284c5
A walkthrough of how a dependence DAG over a straight-line block decides which instruction orders are legal, and how a scheduler picks among them. Includes a property test that every topological order of a random program computes the same result as program order. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
65 lines
2.2 KiB
Python
65 lines
2.2 KiB
Python
"""An interpreter, used to check that reordering preserves meaning."""
|
|
|
|
from dataclasses import dataclass, field
|
|
from typing import Dict, Iterable, List, Optional, Sequence
|
|
|
|
from .isa import FLAGS, Instr
|
|
|
|
|
|
@dataclass
|
|
class State:
|
|
regs: Dict[str, object] = field(default_factory=dict)
|
|
mem: Dict[int, int] = field(default_factory=dict)
|
|
|
|
def copy(self) -> "State":
|
|
return State(dict(self.regs), dict(self.mem))
|
|
|
|
def reg(self, r: str) -> object:
|
|
if r in self.regs:
|
|
return self.regs[r]
|
|
return (False, False) if r.split(".")[0] == FLAGS else 0
|
|
|
|
|
|
def step(ins: Instr, s: State) -> None:
|
|
op, r = ins.op, s.reg
|
|
if op == "li":
|
|
s.regs[ins.dest] = ins.imm
|
|
elif op == "mov":
|
|
s.regs[ins.dest] = r(ins.srcs[0])
|
|
elif op == "add":
|
|
s.regs[ins.dest] = r(ins.srcs[0]) + r(ins.srcs[1])
|
|
elif op == "sub":
|
|
s.regs[ins.dest] = r(ins.srcs[0]) - r(ins.srcs[1])
|
|
elif op == "mul":
|
|
s.regs[ins.dest] = r(ins.srcs[0]) * r(ins.srcs[1])
|
|
elif op == "load":
|
|
s.regs[ins.dest] = s.mem.get(r(ins.srcs[0]) + ins.imm, 0)
|
|
elif op == "store":
|
|
s.mem[r(ins.srcs[1]) + ins.imm] = r(ins.srcs[0])
|
|
elif op == "cmp":
|
|
a, b = r(ins.srcs[0]), r(ins.srcs[1])
|
|
s.regs[ins.dest] = (a < b, a == b)
|
|
elif op == "setlt":
|
|
s.regs[ins.dest] = 1 if r(ins.srcs[0])[0] else 0
|
|
else: # pragma: no cover
|
|
raise ValueError(op)
|
|
|
|
|
|
def run(instrs: Sequence[Instr], order: Optional[Iterable[int]] = None,
|
|
init: Optional[State] = None) -> State:
|
|
"""Execute ``instrs`` in the given order of indices (default: as listed)."""
|
|
s = init.copy() if init else State()
|
|
for i in (order if order is not None else range(len(instrs))):
|
|
step(instrs[i], s)
|
|
return s
|
|
|
|
|
|
def observable(s: State, regs: List[str], rename_map: Optional[Dict[str, str]] = None):
|
|
"""The architecturally visible result: chosen registers plus all memory.
|
|
|
|
``rename_map`` maps an architectural register to the physical register
|
|
holding its final value, for comparing a renamed program to the original.
|
|
"""
|
|
m = rename_map or {}
|
|
return ({r: s.reg(m.get(r, r)) for r in regs}, dict(sorted(s.mem.items())))
|