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>
218 lines
8.7 KiB
Python
218 lines
8.7 KiB
Python
"""Walk through topological sorting of an assembly block, step by step.
|
|
|
|
python3 -m topsort_asm # the built-in example
|
|
python3 -m topsort_asm prog.s --dot g.dot # your own block
|
|
"""
|
|
|
|
import argparse
|
|
import os
|
|
import random
|
|
from typing import List, Optional
|
|
|
|
from . import deps, rename, schedule, sim, toposort
|
|
from .isa import Instr, parse
|
|
|
|
EXAMPLE = os.path.join(os.path.dirname(__file__), "..", "examples", "struct.s")
|
|
EXHAUSTIVE_LIMIT = 50_000
|
|
|
|
|
|
def h(title: str) -> None:
|
|
print()
|
|
print(title)
|
|
print("=" * len(title))
|
|
|
|
|
|
def listing(instrs: List[Instr]) -> str:
|
|
return "\n".join(f" {i.index:>2}: {i.text()}" for i in instrs)
|
|
|
|
|
|
def fmt_order(order: List[int]) -> str:
|
|
return " ".join(map(str, order))
|
|
|
|
|
|
def initial_states(instrs: List[Instr]) -> List[sim.State]:
|
|
"""A few starting states, including one where r11 aliases r10's struct."""
|
|
regs = sorted({r for i in instrs for r in i.reads if r != "flags"})
|
|
out = []
|
|
for r11 in (200, 102):
|
|
s = sim.State()
|
|
for k, r in enumerate(regs):
|
|
s.regs[r] = 7 + 13 * k
|
|
s.regs.update({"r10": 100, "r11": r11})
|
|
s.mem.update({100: 3, 101: 4, 102: 0, 103: 5, 200: 0})
|
|
out.append(s)
|
|
return out
|
|
|
|
|
|
def live_out(instrs: List[Instr]) -> List[str]:
|
|
return sorted({w for i in instrs for w in i.writes if w != "flags"})
|
|
|
|
|
|
def check_orders(dag: deps.DAG, instrs: List[Instr], regs: List[str],
|
|
rmap: Optional[dict], rng: random.Random, reference) -> str:
|
|
n_orders = toposort.count_orders(dag.n, dag.succ)
|
|
if n_orders <= EXHAUSTIVE_LIMIT:
|
|
orders = toposort.all_orders(dag.n, dag.succ)
|
|
how = f"all {n_orders:,}"
|
|
else:
|
|
orders = (toposort.kahn(dag.n, dag.succ, choose=rng.choice)
|
|
for _ in range(2000))
|
|
how = "2,000 random"
|
|
checked = 0
|
|
for order in orders:
|
|
for init, want in zip(initial_states(instrs), reference):
|
|
got = sim.observable(sim.run(instrs, order, init), regs, rmap)
|
|
if got != want:
|
|
raise AssertionError(f"order {order} changed the result")
|
|
checked += 1
|
|
return f"{how} topological orders give the original result " \
|
|
f"(on {len(reference)} initial states, {checked:,} orders run)"
|
|
|
|
|
|
def main(argv: Optional[List[str]] = None) -> None:
|
|
ap = argparse.ArgumentParser(description=__doc__,
|
|
formatter_class=argparse.RawDescriptionHelpFormatter)
|
|
ap.add_argument("file", nargs="?", default=EXAMPLE)
|
|
ap.add_argument("--dot", help="write the dependence graph as Graphviz")
|
|
ap.add_argument("--seed", type=int, default=1)
|
|
args = ap.parse_args(argv)
|
|
rng = random.Random(args.seed)
|
|
|
|
with open(args.file) as f:
|
|
instrs = parse(f.read())
|
|
dag = deps.build_dag(instrs)
|
|
regs = live_out(instrs)
|
|
reference = [sim.observable(sim.run(instrs, None, s), regs)
|
|
for s in initial_states(instrs)]
|
|
|
|
h("1. The block")
|
|
print(listing(instrs))
|
|
|
|
h("2. Dependences (u -> v: u must run before v)")
|
|
print("Every edge points forward, so the graph is a DAG and program order")
|
|
print("is one valid topological order. The question is which others are.\n")
|
|
for e in sorted(dag.edges, key=lambda e: (e.dst, e.src)):
|
|
print(f" {e.src:>2} -> {e.dst:<2} {e.kind} {e.via:<5} "
|
|
f"{instrs[e.src].text():<20} before {instrs[e.dst].text()}")
|
|
kinds = {k: sum(e.kind == k for e in dag.edges) for k in ("RAW", "WAR", "WAW")}
|
|
print(f"\n {len(dag.edges)} edges: " +
|
|
", ".join(f"{v} {k}" for k, v in kinds.items()))
|
|
if args.dot:
|
|
with open(args.dot, "w") as f:
|
|
f.write(deps.to_dot(dag) + "\n")
|
|
print(f" (graph written to {args.dot}; render with `dot -Tsvg`)")
|
|
|
|
h("3. Kahn's algorithm")
|
|
print("Keep a ready set of instructions whose predecessors have all been")
|
|
print("emitted. Emit one, decrement its successors' in-degrees, and add any")
|
|
print("that reach zero. Choosing the lowest index each time gives:\n")
|
|
trace: List[dict] = []
|
|
order = toposort.kahn(dag.n, dag.succ, trace=trace)
|
|
for k, step in enumerate(trace):
|
|
rel = ", ".join(map(str, step["released"])) or "-"
|
|
ready = "{" + ", ".join(map(str, step["ready"])) + "}"
|
|
print(f" step {k:>2} ready {ready:<14} emit {step['chose']:>2}"
|
|
f" releases {rel}")
|
|
print(f"\n order: {fmt_order(order)} (program order, as promised)")
|
|
print(f" DFS reverse post-order gives another: "
|
|
f"{fmt_order(toposort.dfs_order(dag.n, dag.succ))}")
|
|
|
|
h("4. How much freedom is there?")
|
|
n_orders = toposort.count_orders(dag.n, dag.succ)
|
|
print(f" {n_orders:,} of {_fact(dag.n):,} permutations of {dag.n} instructions "
|
|
"respect every edge.")
|
|
print(" Three picked at random (choose = random ready instruction):")
|
|
for _ in range(3):
|
|
print(" ", fmt_order(toposort.kahn(dag.n, dag.succ, choose=rng.choice)))
|
|
print(" ", check_orders(dag, instrs, regs, None, rng, reference))
|
|
bad = _violating_order(dag, instrs, regs, reference)
|
|
if bad:
|
|
(u, v), order, got, want = bad
|
|
e = dag.edges_between(u, v)[0]
|
|
print(f"\n Break one edge -- run {v} before {u} ({e.kind} on {e.via}):")
|
|
print(f" order {fmt_order(order)}")
|
|
print(f" expected {_diff(want, got)[0]}")
|
|
print(f" got {_diff(want, got)[1]}")
|
|
|
|
h("5. Choosing among the orders: list scheduling")
|
|
print("Latencies: load 4, mul 3, everything else 1. Single issue, in order;")
|
|
print("an instruction waits until its RAW producers' results are ready.\n")
|
|
base = schedule.time_order(dag, list(range(dag.n)))
|
|
best = schedule.list_schedule(dag)
|
|
print(f" program order: {base.cycles} cycles, {_n(base.stalls, 'stall')}")
|
|
print(base.timeline(dag))
|
|
print(f"\n list schedule (highest latency-weighted height first): "
|
|
f"{best.cycles} cycles, {_n(best.stalls, 'stall')}")
|
|
print(best.timeline(dag))
|
|
|
|
h("6. Renaming away the false dependences")
|
|
renamed, rmap = rename.rename(instrs)
|
|
rdag = deps.build_dag(renamed)
|
|
print("WAR and WAW edges exist only because a register name was reused.")
|
|
print("Give each write its own name and they disappear:\n")
|
|
print(listing(renamed))
|
|
rk = {k: sum(e.kind == k for e in rdag.edges) for k in ("RAW", "WAR", "WAW")}
|
|
print(f"\n {len(rdag.edges)} edges: " + ", ".join(f"{v} {k}" for k, v in rk.items()))
|
|
left = [e for e in rdag.edges if e.kind != "RAW"]
|
|
if left:
|
|
print(" remaining non-RAW edges are memory, which renaming cannot touch:")
|
|
for e in left:
|
|
print(f" {e}")
|
|
print(f" topological orders: {n_orders:,} -> "
|
|
f"{toposort.count_orders(rdag.n, rdag.succ):,}")
|
|
print(" ", check_orders(rdag, renamed, regs, rmap, rng, reference))
|
|
rbest = schedule.list_schedule(rdag)
|
|
print(f"\n list schedule after renaming: {rbest.cycles} cycles, "
|
|
f"{_n(rbest.stalls, 'stall')} (was {best.cycles} / {base.cycles} in program order)")
|
|
print(rbest.timeline(rdag))
|
|
|
|
h("7. Why a cycle is impossible here -- and what happens if one appears")
|
|
print("Dependences in straight-line code always point forward. Add a single")
|
|
print("backward edge (say a buggy alias analysis claimed the last")
|
|
print("instruction feeds the first) and no valid order exists:\n")
|
|
last = dag.n - 1
|
|
succ = {u: set(vs) for u, vs in dag.succ.items()}
|
|
succ[last].add(0)
|
|
for name, fn in (("kahn", toposort.kahn), ("dfs ", toposort.dfs_order)):
|
|
try:
|
|
fn(dag.n, succ)
|
|
except toposort.CycleError as err:
|
|
print(f" {name}: {err}")
|
|
|
|
|
|
def _n(k: int, word: str) -> str:
|
|
return f"{k} {word}" + ("" if k == 1 else "s")
|
|
|
|
|
|
def _fact(n: int) -> int:
|
|
out = 1
|
|
for k in range(2, n + 1):
|
|
out *= k
|
|
return out
|
|
|
|
|
|
def _violating_order(dag, instrs, regs, reference):
|
|
"""Find a single adjacent swap across an edge that changes the result."""
|
|
base = list(range(dag.n))
|
|
for u, v in sorted(dag.pairs(), key=lambda p: (p[1] - p[0], p)):
|
|
order = base[:u] + [v] + [x for x in base[u:] if x != v]
|
|
for init, want in zip(initial_states(instrs), reference):
|
|
got = sim.observable(sim.run(instrs, order, init), regs)
|
|
if got != want:
|
|
return (u, v), order, got, want
|
|
return None
|
|
|
|
|
|
def _diff(want, got):
|
|
wr, wm = want
|
|
gr, gm = got
|
|
keys = [k for k in wr if wr[k] != gr[k]]
|
|
addrs = [a for a in sorted(set(wm) | set(gm)) if wm.get(a) != gm.get(a)]
|
|
fmt = lambda r, m: ", ".join([f"{k}={r[k]}" for k in keys] +
|
|
[f"mem[{a}]={m.get(a, 0)}" for a in addrs])
|
|
return fmt(wr, wm), fmt(gr, gm)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|