[igodard]

It's actually rather easy to allocate belt positions, because the belt is a FIFO and allocates them itself :-)

However, the scheduler must track lifetimes and make sure that nothing still live falls off the end. This is also (not quite so) easy to do, because the scheduler knows exactly what is the belt behavior of each operation it schedules (the Mill is exposed-pipeline), so it is sufficient to symbolically execute a candidate schedule to know if it is feasible.

If not, the scheduler inserts a spill/fill pair at appropriate places and reschedules. This is guaranteed to terminate, and in practice usually is immediately feasible and rarely takes more than one iteration.

The operation scheduling itself is the standard time-reversed tableau scheduler used in VLIWs, probably 40 years old at this point.