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>
358 lines
14 KiB
Python
358 lines
14 KiB
Python
import itertools
|
|
import random
|
|
import unittest
|
|
|
|
from topsort_asm import deps, rename, schedule, sim, toposort
|
|
from topsort_asm.isa import FLAGS, AsmError, parse
|
|
|
|
|
|
def edge_set(src):
|
|
return {(e.src, e.dst, e.kind, e.via) for e in deps.build_dag(parse(src)).edges}
|
|
|
|
|
|
def rand_dag(rng, n, p):
|
|
succ = {u: set() for u in range(n)}
|
|
for u in range(n):
|
|
for v in range(u + 1, n):
|
|
if rng.random() < p:
|
|
succ[u].add(v)
|
|
# Shuffle labels so "sorted by index" is not automatically topological.
|
|
perm = list(range(n))
|
|
rng.shuffle(perm)
|
|
return {perm[u]: {perm[v] for v in vs} for u, vs in succ.items()}
|
|
|
|
|
|
REGS = ["r1", "r2", "r3", "r4"]
|
|
BASES = ["r10", "r11"]
|
|
|
|
|
|
def rand_program(rng, n):
|
|
lines = []
|
|
for _ in range(n):
|
|
k = rng.random()
|
|
r = lambda: rng.choice(REGS)
|
|
if k < 0.15:
|
|
lines.append(f"li {r()}, {rng.randint(-3, 9)}")
|
|
elif k < 0.35:
|
|
lines.append(f"{rng.choice(['add', 'sub', 'mul'])} {r()}, {r()}, {r()}")
|
|
elif k < 0.40:
|
|
lines.append(f"mov {r()}, {r()}")
|
|
elif k < 0.55:
|
|
lines.append(f"load {r()}, [{rng.choice(BASES)}+{rng.randint(0, 2)}]")
|
|
elif k < 0.72:
|
|
lines.append(f"store {r()}, [{rng.choice(BASES)}+{rng.randint(0, 2)}]")
|
|
elif k < 0.80:
|
|
lines.append(f"cmp {r()}, {r()}")
|
|
elif k < 0.88:
|
|
lines.append(f"setlt {r()}")
|
|
else:
|
|
# Redefine a base register, so offset-based alias reasoning must
|
|
# notice that [r10+1] before and after are different addresses.
|
|
lines.append(f"li {rng.choice(BASES)}, {rng.choice([100, 101, 102])}")
|
|
return parse("\n".join(lines))
|
|
|
|
|
|
def rand_state(rng):
|
|
s = sim.State()
|
|
for r in REGS:
|
|
s.regs[r] = rng.randint(-5, 5)
|
|
s.regs["r10"] = 100
|
|
s.regs["r11"] = rng.choice([100, 101, 102, 200]) # often aliases r10
|
|
for a in range(98, 106):
|
|
s.mem[a] = rng.randint(-5, 5)
|
|
s.regs[FLAGS] = (rng.random() < 0.5, False)
|
|
return s
|
|
|
|
|
|
def outputs(instrs):
|
|
return sorted({r for i in instrs for r in i.writes} | set(REGS + BASES))
|
|
|
|
|
|
class ParseTest(unittest.TestCase):
|
|
def test_round_trip(self):
|
|
src = """li r1, -4
|
|
mov r2, r1
|
|
add r3, r1, r2
|
|
load r4, [r3-2]
|
|
store r4, [r3]
|
|
cmp r1, r2
|
|
setlt r5 ; comment"""
|
|
ins = parse(src)
|
|
self.assertEqual([i.text() for i in parse("\n".join(i.text() for i in ins))],
|
|
[i.text() for i in ins])
|
|
self.assertEqual(ins[3].imm, -2)
|
|
self.assertEqual(ins[5].writes, (FLAGS,))
|
|
self.assertEqual(ins[6].reads, (FLAGS,))
|
|
self.assertEqual(ins[4].reads, ("r4", "r3"))
|
|
self.assertEqual(ins[4].writes, ())
|
|
|
|
def test_errors(self):
|
|
for bad in ["jmp r1", "add r1, r2", "load r1, r2", "li r1, x",
|
|
"mov flags, r1", "store r1, [r2*4]"]:
|
|
with self.subTest(bad=bad), self.assertRaises(AsmError):
|
|
parse(bad)
|
|
|
|
|
|
class DepsTest(unittest.TestCase):
|
|
def test_register_kinds(self):
|
|
self.assertEqual(edge_set("li r1, 1\nadd r2, r1, r1"), {(0, 1, "RAW", "r1")})
|
|
self.assertEqual(edge_set("add r2, r1, r1\nli r1, 1"), {(0, 1, "WAR", "r1")})
|
|
self.assertEqual(edge_set("li r1, 1\nli r1, 2"), {(0, 1, "WAW", "r1")})
|
|
|
|
def test_only_nearest_writer(self):
|
|
# 0 -> 2 is implied by 0 -> 1 -> 2 and must not be listed.
|
|
self.assertEqual(edge_set("li r1, 1\nli r1, 2\nmov r2, r1"),
|
|
{(0, 1, "WAW", "r1"), (1, 2, "RAW", "r1")})
|
|
|
|
def test_war_from_every_reader(self):
|
|
got = edge_set("li r1, 1\nmov r2, r1\nmov r3, r1\nli r1, 2")
|
|
self.assertIn((1, 3, "WAR", "r1"), got)
|
|
self.assertIn((2, 3, "WAR", "r1"), got)
|
|
|
|
def test_hidden_flags(self):
|
|
self.assertEqual(edge_set("cmp r1, r2\nsetlt r3"), {(0, 1, "RAW", FLAGS)})
|
|
self.assertEqual(edge_set("setlt r3\ncmp r1, r2"), {(0, 1, "WAR", FLAGS)})
|
|
|
|
def test_memory(self):
|
|
self.assertEqual(edge_set("store r1, [r10]\nload r2, [r10]"),
|
|
{(0, 1, "RAW", "mem")})
|
|
self.assertEqual(edge_set("load r2, [r10]\nstore r1, [r10]"),
|
|
{(0, 1, "WAR", "mem")})
|
|
self.assertEqual(edge_set("store r1, [r10]\nstore r2, [r10]"),
|
|
{(0, 1, "WAW", "mem")})
|
|
self.assertEqual(edge_set("load r1, [r10]\nload r2, [r10]"), set())
|
|
|
|
def test_alias_analysis(self):
|
|
# Same base, same definition, different offsets: provably disjoint.
|
|
self.assertEqual(edge_set("store r1, [r10]\nload r2, [r10+1]"), set())
|
|
# Different base registers might hold the same address.
|
|
self.assertEqual(edge_set("store r1, [r10]\nload r2, [r11+1]"),
|
|
{(0, 1, "RAW", "mem")})
|
|
# Base redefined in between: the offsets no longer prove anything.
|
|
self.assertIn((0, 2, "RAW", "mem"),
|
|
edge_set("store r1, [r10]\nli r10, 99\nload r2, [r10+1]"))
|
|
|
|
def test_edges_point_forward(self):
|
|
rng = random.Random(0)
|
|
for _ in range(200):
|
|
dag = deps.build_dag(rand_program(rng, 20))
|
|
self.assertTrue(all(e.src < e.dst for e in dag.edges))
|
|
|
|
def test_transitive_reduction_preserves_reachability(self):
|
|
rng = random.Random(1)
|
|
for _ in range(100):
|
|
dag = deps.build_dag(rand_program(rng, 15))
|
|
keep = deps.transitive_reduction(dag)
|
|
self.assertLessEqual(keep, dag.pairs())
|
|
self.assertEqual(_closure(dag.n, dag.pairs()), _closure(dag.n, keep))
|
|
|
|
def test_dot(self):
|
|
dot = deps.to_dot(deps.build_dag(parse("li r1, 1\nmov r2, r1")))
|
|
self.assertIn('i0 -> i1 [label="RAW r1"', dot)
|
|
|
|
|
|
def _closure(n, pairs):
|
|
reach = {u: set() for u in range(n)}
|
|
for u, v in pairs:
|
|
reach[u].add(v)
|
|
for k in range(n):
|
|
for u in range(n):
|
|
if k in reach[u]:
|
|
reach[u] |= reach[k]
|
|
return reach
|
|
|
|
|
|
class TopoSortTest(unittest.TestCase):
|
|
def test_kahn_and_dfs_are_topological(self):
|
|
rng = random.Random(2)
|
|
for _ in range(300):
|
|
n = rng.randint(0, 25)
|
|
succ = rand_dag(rng, n, rng.random() * 0.5)
|
|
for order in (toposort.kahn(n, succ), toposort.dfs_order(n, succ),
|
|
toposort.kahn(n, succ, choose=rng.choice)):
|
|
self.assertTrue(toposort.is_topological(order, n, succ))
|
|
|
|
def test_count_and_enumeration_match_brute_force(self):
|
|
rng = random.Random(3)
|
|
for _ in range(60):
|
|
n = rng.randint(0, 7)
|
|
succ = rand_dag(rng, n, rng.random() * 0.6)
|
|
brute = [list(p) for p in itertools.permutations(range(n))
|
|
if toposort.is_topological(p, n, succ)]
|
|
orders = list(toposort.all_orders(n, succ))
|
|
self.assertEqual(sorted(orders), brute)
|
|
self.assertEqual(toposort.count_orders(n, succ), len(brute))
|
|
|
|
def test_known_counts(self):
|
|
self.assertEqual(toposort.count_orders(5, {u: set() for u in range(5)}), 120)
|
|
chain = {u: {u + 1} for u in range(5)}
|
|
chain[5] = set()
|
|
self.assertEqual(toposort.count_orders(6, chain), 1)
|
|
|
|
def test_cycles(self):
|
|
succ = {0: {1}, 1: {2}, 2: {3}, 3: {1}, 4: set()}
|
|
for fn in (toposort.kahn, toposort.dfs_order):
|
|
with self.subTest(fn=fn.__name__), self.assertRaises(toposort.CycleError) as cm:
|
|
fn(5, succ)
|
|
cyc = cm.exception.cycle
|
|
self.assertEqual(cyc[0], cyc[-1])
|
|
self.assertTrue(all(b in succ[a] for a, b in zip(cyc, cyc[1:])))
|
|
self.assertEqual(set(cyc), {1, 2, 3})
|
|
|
|
def test_kahn_trace(self):
|
|
trace = []
|
|
toposort.kahn(3, {0: {2}, 1: {2}, 2: set()}, trace=trace)
|
|
self.assertEqual(trace, [
|
|
{"ready": [0, 1], "chose": 0, "released": []},
|
|
{"ready": [1], "chose": 1, "released": [2]},
|
|
{"ready": [2], "chose": 2, "released": []},
|
|
])
|
|
|
|
|
|
class SemanticsTest(unittest.TestCase):
|
|
"""The reason any of this matters: every topological order is equivalent."""
|
|
|
|
def test_every_topological_order_preserves_meaning(self):
|
|
rng = random.Random(4)
|
|
for _ in range(300):
|
|
instrs = rand_program(rng, rng.randint(1, 18))
|
|
dag = deps.build_dag(instrs)
|
|
regs = outputs(instrs)
|
|
for _ in range(5):
|
|
init = rand_state(rng)
|
|
want = sim.observable(sim.run(instrs, None, init), regs)
|
|
order = toposort.kahn(dag.n, dag.succ, choose=rng.choice)
|
|
got = sim.observable(sim.run(instrs, order, init), regs)
|
|
self.assertEqual(got, want, (instrs, order))
|
|
|
|
def test_exhaustively_on_small_blocks(self):
|
|
rng = random.Random(5)
|
|
for _ in range(60):
|
|
instrs = rand_program(rng, 7)
|
|
dag = deps.build_dag(instrs)
|
|
regs = outputs(instrs)
|
|
init = rand_state(rng)
|
|
want = sim.observable(sim.run(instrs, None, init), regs)
|
|
for order in toposort.all_orders(dag.n, dag.succ):
|
|
self.assertEqual(sim.observable(sim.run(instrs, order, init), regs), want)
|
|
|
|
def test_violating_each_kind_of_edge_breaks_it(self):
|
|
init = sim.State({"r1": 2, "r2": 5, "r10": 100}, {100: 7})
|
|
cases = {
|
|
"RAW reg": "li r1, 9\nadd r3, r1, r1",
|
|
"WAR reg": "add r3, r1, r1\nli r1, 9",
|
|
"WAW reg": "li r1, 8\nli r1, 9",
|
|
"RAW flags": "cmp r1, r2\nsetlt r3",
|
|
"RAW mem": "store r2, [r10]\nload r3, [r10]",
|
|
"WAR mem": "load r3, [r10]\nstore r2, [r10]",
|
|
"WAW mem": "store r1, [r10]\nstore r2, [r10]",
|
|
}
|
|
for name, src in cases.items():
|
|
with self.subTest(name):
|
|
instrs = parse(src)
|
|
regs = outputs(instrs)
|
|
ok = sim.observable(sim.run(instrs, [0, 1], init), regs)
|
|
swapped = sim.observable(sim.run(instrs, [1, 0], init), regs)
|
|
self.assertNotEqual(ok, swapped)
|
|
|
|
|
|
class RenameTest(unittest.TestCase):
|
|
def test_removes_all_register_false_dependences(self):
|
|
rng = random.Random(6)
|
|
for _ in range(200):
|
|
renamed, _ = rename.rename(rand_program(rng, 20))
|
|
for e in deps.build_dag(renamed).edges:
|
|
if e.via != "mem":
|
|
self.assertEqual(e.kind, "RAW", e)
|
|
|
|
def test_renamed_orders_preserve_meaning(self):
|
|
rng = random.Random(7)
|
|
for _ in range(300):
|
|
instrs = rand_program(rng, rng.randint(1, 18))
|
|
renamed, rmap = rename.rename(instrs)
|
|
rdag = deps.build_dag(renamed)
|
|
regs = outputs(instrs)
|
|
for _ in range(5):
|
|
init = rand_state(rng)
|
|
want = sim.observable(sim.run(instrs, None, init), regs)
|
|
order = toposort.kahn(rdag.n, rdag.succ, choose=rng.choice)
|
|
got = sim.observable(sim.run(renamed, order, init), regs, rmap)
|
|
self.assertEqual(got, want)
|
|
|
|
def test_never_fewer_orders(self):
|
|
rng = random.Random(8)
|
|
for _ in range(100):
|
|
instrs = rand_program(rng, 10)
|
|
dag = deps.build_dag(instrs)
|
|
rdag = deps.build_dag(rename.rename(instrs)[0])
|
|
self.assertGreaterEqual(toposort.count_orders(rdag.n, rdag.succ),
|
|
toposort.count_orders(dag.n, dag.succ))
|
|
|
|
|
|
class ScheduleTest(unittest.TestCase):
|
|
def test_load_use_stall(self):
|
|
dag = deps.build_dag(parse("load r1, [r10]\nadd r2, r1, r1"))
|
|
t = schedule.time_order(dag, [0, 1])
|
|
self.assertEqual(t.issue, {0: 0, 1: 4})
|
|
self.assertEqual((t.cycles, t.stalls), (5, 3))
|
|
|
|
def test_list_schedule_fills_load_shadow(self):
|
|
dag = deps.build_dag(parse("load r1, [r10]\nadd r2, r1, r1\n"
|
|
"li r3, 1\nli r4, 2\nli r5, 3"))
|
|
t = schedule.list_schedule(dag)
|
|
self.assertEqual(t.order[:4], [0, 2, 3, 4])
|
|
self.assertEqual(t.stalls, 0)
|
|
|
|
def test_list_schedule_is_topological(self):
|
|
rng = random.Random(9)
|
|
for _ in range(300):
|
|
dag = deps.build_dag(rand_program(rng, rng.randint(1, 25)))
|
|
t = schedule.list_schedule(dag)
|
|
self.assertTrue(toposort.is_topological(t.order, dag.n, dag.succ))
|
|
# The schedule's own cycle counting agrees with re-timing it.
|
|
self.assertEqual(t.issue, schedule.time_order(dag, t.order).issue)
|
|
|
|
def test_list_schedule_near_optimal_on_small_blocks(self):
|
|
# List scheduling is a heuristic: check it is within the optimum found
|
|
# by brute force, and record how often it hits it exactly.
|
|
rng = random.Random(10)
|
|
hits = 0
|
|
for _ in range(40):
|
|
dag = deps.build_dag(rand_program(rng, 7))
|
|
best = min(schedule.time_order(dag, o).cycles
|
|
for o in toposort.all_orders(dag.n, dag.succ))
|
|
got = schedule.list_schedule(dag).cycles
|
|
self.assertGreaterEqual(got, best)
|
|
hits += got == best
|
|
self.assertGreater(hits, 30)
|
|
|
|
def test_example_numbers(self):
|
|
import os
|
|
path = os.path.join(os.path.dirname(__file__), "..", "examples", "struct.s")
|
|
with open(path) as f:
|
|
instrs = parse(f.read())
|
|
dag = deps.build_dag(instrs)
|
|
rdag = deps.build_dag(rename.rename(instrs)[0])
|
|
self.assertEqual(schedule.time_order(dag, range(dag.n)).cycles, 20)
|
|
self.assertEqual(schedule.list_schedule(dag).cycles, 15)
|
|
self.assertEqual(schedule.list_schedule(rdag).cycles, 13)
|
|
self.assertEqual(toposort.count_orders(dag.n, dag.succ), 720)
|
|
self.assertEqual(toposort.count_orders(rdag.n, rdag.succ), 5040)
|
|
|
|
|
|
class DemoTest(unittest.TestCase):
|
|
def test_runs(self):
|
|
import contextlib
|
|
import io
|
|
from topsort_asm import demo
|
|
buf = io.StringIO()
|
|
with contextlib.redirect_stdout(buf):
|
|
demo.main([])
|
|
out = buf.getvalue()
|
|
self.assertIn("all 720 topological orders give the original result", out)
|
|
self.assertIn("cycle:", out)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
unittest.main()
|