top-sort-asm/README.md

top-sort-asm

How topological sorting decides which orders a CPU or compiler may run instructions in, shown on a small assembly block. The code is Python, standard library only (3.9+).

python3 -m topsort_asm                        # walk through examples/struct.s
python3 -m topsort_asm my.s --dot deps.dot    # your own block, plus a Graphviz graph
python3 -m unittest discover -s tests -t .    # tests

The idea

A straight-line block of instructions is written in one order, but most of that order is arbitrary. Instruction v must follow instruction u only if swapping them could change the result. Those pairs make a directed graph. Any topological order of that graph computes the same answer, and picking the fastest one is what instruction scheduling means.

The example (examples/struct.s):

 0: load  r1, [r10]        ; x
 1: load  r2, [r10+1]      ; y
 2: mul   r3, r1, r1       ; x*x
 3: mul   r4, r2, r2       ; y*y
 4: add   r3, r3, r4       ; x*x + y*y
 5: store r3, [r10+2]      ; p->z
 6: load  r1, [r10+3]      ; w  (reuses r1)
 7: li    r2, 3            ;    (reuses r2)
 8: mul   r1, r1, r2       ; q = 3w
 9: cmp   r1, r3           ; writes the hidden flags register
10: setlt r5               ; reads it
11: store r1, [r11]        ; r11 might point into the same struct

1. Edges: what must stay ordered

Each register, the implicit flags register, and memory can produce three kinds of edge:

kind	meaning	example	real?
RAW (true)	v reads what u wrote	0 → 2 on r1	yes: a value flows from u to v
WAR (anti)	v overwrites something u still reads	2 → 6 on r1	no: it exists only because a name was reused
WAW (output)	v overwrites what u wrote	1 → 7 on r2	no: it exists only because a name was reused

graph TD
  i0["0: load r1,[r10]"] -->|RAW r1| i2["2: mul r3,r1,r1"]
  i1["1: load r2,[r10+1]"] -->|RAW r2| i3["3: mul r4,r2,r2"]
  i2 -->|RAW r3| i4["4: add r3,r3,r4"]
  i3 -->|RAW r4| i4
  i2 -.->|WAR r1| i6["6: load r1,[r10+3]"]
  i3 -.->|WAR r2| i7["7: li r2,3"]
  i4 -->|RAW r3| i5["5: store r3,[r10+2]"]
  i4 -->|RAW r3| i9["9: cmp r1,r3"]
  i6 -->|RAW r1| i8["8: mul r1,r1,r2"]
  i7 -->|RAW r2| i8
  i8 -->|RAW r1| i9
  i9 -->|RAW flags| i10["10: setlt r5"]
  i8 -->|RAW r1| i11["11: store r1,[r11]"]
  i5 -.->|WAW mem| i11

(Edges implied by a longer path are left out. python3 -m topsort_asm lists all 21.)

Some details matter here:

• Hidden operands. cmp and setlt never name flags, but they talk through it. The parser makes flags an explicit operand, so the edge 9 → 10 exists. A scheduler that forgets implicit operands reorders code incorrectly without any warning.
• Memory needs alias analysis. store [r10+2] and load [r10+3] use the same base register with different offsets, so they cannot touch the same word and need no edge. store [r11] might hit anything r10 points at, so it is ordered after every earlier access. The verification below runs once with r11 = 102, which really does alias p->z.
• Only the nearest writer counts. li r1,1; li r1,2; mov r2,r1 gets edges 0→1→2, not also 0→2. That edge is implied, and leaving it out keeps the graph small.

All edges point forward in program order, so the graph is always acyclic and program order is always one valid topological order.

2. Kahn's algorithm

Keep the ready set: instructions whose predecessors have all been emitted. Emit one, remove its outgoing edges, and add any instruction that becomes ready.

step  0  ready {0, 1}         emit  0   releases 2
step  1  ready {1, 2}         emit  1   releases 3
step  2  ready {2, 3}         emit  2   releases 6
step  3  ready {3, 6}         emit  3   releases 4, 7
step  4  ready {4, 6, 7}      emit  4   releases 5
...

Always choosing the lowest index gives back program order. The ready set is the freedom available: every way of choosing from it gives a valid order. This block has 720 valid orders out of 12! ≈ 479 million permutations (count_orders uses a DP over subsets). The demo runs all 720 in the interpreter on two initial states, one of them with aliasing pointers, and each one produces the original registers and memory. If one edge is broken (4 run before 3), p->z comes out as 81 instead of 25.

dfs_order (reverse DFS post-order) is the other classic algorithm. Both report a cycle if one exists. Straight-line code cannot contain one, so the demo adds a bogus backward edge to show what the report looks like.

3. Picking a good order: list scheduling

Latencies are load 4, mul 3, and 1 for everything else, on a single-issue, in-order pipeline. In program order, each load or multiply is followed immediately by its consumer, which stalls:

program order: 20 cycles, 8 stalls

A list scheduler is Kahn's algorithm with a clock. An instruction is ready only once its producers' results have arrived. Among ready instructions it picks the one with the longest latency-weighted path to the end of the block, because delaying that one delays everything after it.

list schedule: 15 cycles, 3 stalls

It is still limited: load r1, [r10+3] cannot move to the top, because of the WAR edge 2 → 6. The first mul still needs to read the old r1.

4. Renaming removes the false edges

Give each write its own register (r1.1, r1.2, …). WAR and WAW edges only exist because names are reused, so they vanish:

 0: load  r1.1, [r10]
 1: load  r2.1, [r10+1]
 2: mul   r3.1, r1.1, r1.1
 ...
 6: load  r1.2, [r10+3]
 7: li    r2.2, 3
 8: mul   r1.3, r1.2, r2.2

The edge count drops from 21 to 15. The remaining non-RAW edges are all on memory: an address is computed at run time, so it cannot be renamed like a register. Valid orders go from 720 to 5,040, and the schedule improves again:

list schedule after renaming: 13 cycles, 1 stall (was 15 / 20 in program order)
cycle  0:  0: load  r1.1, [r10]
cycle  1:  1: load  r2.1, [r10+1]
cycle  2:  6: load  r1.2, [r10+3]     <- hoisted above both multiplies
cycle  3:  7: li    r2.2, 3
cycle  4:  2: mul   r3.1, r1.1, r1.1
...

An out-of-order CPU does the same work in hardware. The register renamer removes WAR/WAW hazards, the reservation stations hold the ready set, and the issue logic chooses from it every cycle.

Layout

file	what
topsort_asm/isa.py	tiny ISA and parser; implicit flags operand made explicit
topsort_asm/deps.py	dependence DAG (RAW/WAR/WAW on registers, flags and memory), alias test, transitive reduction, DOT output
topsort_asm/toposort.py	Kahn (with a choice hook and step trace), DFS, enumeration, counting, cycle reporting; knows nothing about assembly
topsort_asm/schedule.py	pipeline timing model and list scheduler
topsort_asm/rename.py	register renaming
topsort_asm/sim.py	interpreter used to check reorderings preserve meaning
topsort_asm/demo.py	the walkthrough

Tests

tests/test_topsort_asm.py covers:

• Kahn and DFS output is always topological on random DAGs. Enumeration and counting match a brute-force filter over all permutations.
• Every topological order of a random program computes the same result as program order. The random programs redefine base registers, and the initial states make r10/r11 alias. Small blocks are checked exhaustively over every order. The same holds for renamed programs.
• For each of the seven edge kinds, swapping a two-instruction example changes the result, so none of the edges is unnecessary.
• The list schedule is topological, and on small blocks it is compared with the brute-force optimum. It is a heuristic and not always optimal.