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>
34 lines
1.2 KiB
Python
34 lines
1.2 KiB
Python
"""Register renaming: give every write a fresh name to delete WAR/WAW edges.
|
|
|
|
The k-th write to architectural register ``r1`` becomes ``r1.k``; a read
|
|
uses whichever name currently holds the value. Live-in registers keep their
|
|
plain names. Afterwards each register is written at most once, so the only
|
|
register edges left are true (RAW) dependences.
|
|
|
|
Memory cannot be renamed this way -- an address is a computed value, not a
|
|
name -- so memory WAR/WAW edges survive. That is why hardware has store
|
|
buffers and compilers work hard on alias analysis.
|
|
"""
|
|
|
|
from collections import Counter
|
|
from dataclasses import replace
|
|
from typing import Dict, List, Tuple
|
|
|
|
from .isa import Instr
|
|
|
|
|
|
def rename(instrs: List[Instr]) -> Tuple[List[Instr], Dict[str, str]]:
|
|
"""Return the renamed block and the final arch -> physical name map."""
|
|
current: Dict[str, str] = {}
|
|
version: Counter = Counter()
|
|
out = []
|
|
for ins in instrs:
|
|
srcs = tuple(current.get(r, r) for r in ins.srcs)
|
|
dest = ins.dest
|
|
if dest is not None:
|
|
version[dest] += 1
|
|
current[dest] = f"{dest}.{version[dest]}"
|
|
dest = current[dest]
|
|
out.append(replace(ins, srcs=srcs, dest=dest))
|
|
return out, current
|