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 |

```mermaid
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.