Bundling Instructions for VLIW Issue Slots

A very long instruction word processor issues a fixed number of operations per cycle, and the encoding of a cycle is a single wide instruction with one field per issue slot. The hardware does no reordering and, on the pure form of the model, no interlocking: it executes the bundle as written, and an operation that reads a register in the same bundle that writes it receives the old value. All the work of finding parallelism, respecting latencies, and respecting functional-unit availability moves from hardware to the compiler.

The consequence is that the compiler’s scheduler and its instruction packer are no longer separate concerns. The scheduler decides which operations can occupy the same cycle, and the packer decides how those operations are encoded into slots. On a target where each slot is tied to a functional unit, the packer’s constraints feed back into the scheduler: an operation that can only go in slot 0 cannot be paired with another operation that also requires slot 0, even if the two are independent and the latencies permit, a restriction that has no counterpart in the unconstrained ordering of List Scheduling and the Critical Path.

The Bundle as the Unit of Encoding

A bundle is W bits wide, containing S slots, with W/S bits per slot if the slots are uniform. Uniform slots make the encoding simple and the decode cheap; the price is that every slot must be able to encode every operation, or the slot count must be multiplied by the number of operation classes.

Real designs split the difference. A slot may be general-purpose or restricted to a class — memory, floating point, branch — and the restriction is visible to the compiler as a per-opcode slot mask. The scheduler then has a resource-constrained problem with a constraint per bundle: for each class, the number of operations of that class in the bundle must not exceed the number of slots that accept the class.

The bundle is also the unit of the branch and the unit of the stop. All slots of a bundle issue in the same cycle, so a branch that occupies a slot takes effect only after the whole bundle has issued: operations in the same bundle as the branch are not squashed, and an operation that must not execute when the branch is taken has to be placed in a later bundle. On machines with explicit stop bits, the compiler inserts a stop at a bundle boundary to tell the hardware that the next bundle’s operations do not depend on this one, which lets the hardware skip a hazard check. A missing stop is a correctness bug, not an inefficiency.

Empty slots are the defining cost of the model. When the scheduler cannot fill a slot, the bundle contains a no-op in that position, and the no-op occupies the full slot width in the encoding. A loop with an average of 2.5 useful operations per four-slot bundle wastes 37 percent of its instruction bandwidth and, worse, 37 percent of its instruction cache. The waste is visible in the binary, which is why VLIW code is typically larger than superscalar code for the same program.

Slot Assignment as a Matching Problem

Given a bundle’s worth of operations and a set of slots with masks, assigning operations to slots is a bipartite matching: operations on one side, slots on the other, an edge where the slot accepts the operation. A perfect matching exists exactly when Hall’s condition holds for every subset of operations, and a greedy assignment can fail to find one even when it exists.

The practical algorithms are greedy with a repair step. Assign the most constrained operations first — those with a single legal slot — then the next most constrained, and so on. If an assignment fails, swap an already-assigned operation into a different slot to make room. The swap is cheap because bundle sizes are small, typically four to eight slots, so an exhaustive search over the bundle is affordable at the sizes involved.

A greedy pass over a bundle, checking the slot mask and the register conflict for each candidate:

/* Fill one bundle; ops[] holds up to NSLOT candidates in priority order. */
for (int i = 0; i < nops; i++) {
    int op = ops[i];
    for (int s = 0; s < NSLOT; s++) {
        if (slot_taken[s] || !(slot_mask[s] & class_bit(op))) continue;
        if (writes_register_in_slot(op, s)) continue;   /* WAR/WAW within bundle */
        slot_taken[s] = 1;
        bundle[s] = op;
        break;
    }
    /* An operation with no free slot stays for the next bundle. */
}

There is a second constraint that makes the problem harder than matching: register reads and writes within a bundle. If two operations in the same bundle write the same register, the bundle’s semantics are ambiguous unless the architecture defines an order, and most do not. The scheduler must therefore ensure that operations in a bundle have no write-after-write or read-after-write conflict, which is a constraint on the bundle as a whole rather than on individual slots. A scheduler that works cycle by cycle must check this constraint when it adds an operation to a partially filled bundle, and a scheduler that works with a fixed cycle assignment must verify it after packing.

Latency constraints add a third dimension. An operation’s result is not available to an operation in the same bundle, because both issue in the same cycle. An operation with latency L can feed an operation L bundles later. If the scheduler assigned the consumer too early, the packer cannot fix it; the bundle boundary is a hard barrier that no amount of clever slot assignment can cross. This is why the packer is usually integrated into the scheduler rather than run after it: a schedule that is feasible as a list of cycle assignments may be infeasible as a sequence of bundles, because the bundle granularity is coarser than the cycle granularity.

The Nop and the Code Size Problem

The cost of an empty slot is not only the wasted issue opportunity. It is also the bytes. A four-slot bundle of 32-bit slots is 16 bytes regardless of whether one slot is useful. A program with many partially filled bundles has an instruction footprint proportional to the bundle count rather than to the operation count, and instruction cache misses rise accordingly.

Compilers reduce the waste in three ways.

The first is to schedule for density as well as for latency: when two schedules have equal critical-path length, prefer the one that fills more slots. A list scheduler with a density-aware priority will pack independent operations into the same bundle rather than spreading them across cycles, which is the opposite of what a latency-first priority does on a machine with unlimited issue. On a VLIW, the issue width is the binding constraint, so density is the objective.

The second is to use compressed encodings. Some VLIW designs allow a bundle to be shortened when trailing slots are empty, with a length field in the header. The compression is only legal if the empty slots are at the end, so the packer’s slot assignment must put useful operations first. This is a constraint that a matching-based assignment does not naturally respect, and it is the reason some compilers treat the last slots as more valuable than the first.

The third is loop-level scheduling, which amortizes the fill and drain of the pipeline over many iterations. A software-pipelined loop has a steady state in which every bundle is full, and the waste is confined to the prologue and epilogue. This is the strongest argument for modulo scheduling on VLIW targets, and the technique is described in Modulo Scheduling and Software Pipelining.

Stop Bits and the Semantics of a Bundle

An explicit stop bit changes the meaning of the instruction stream from “one bundle per cycle” to “one bundle per stop-delimited group”. Without a stop, the hardware may execute the bundle with the next one overlapped, or may treat the pair as a single long bundle; with a stop, the boundary is a scheduling barrier.

The compiler inserts a stop when the next bundle’s operations depend on the current one’s, or when a resource conflict requires a gap. An extra stop costs a cycle, so the scheduler tries to place independent operations after a bundle without a stop. The decision is per boundary, which makes the stop bit an explicit scheduling resource: the number of stops in a loop is the number of cycles the loop takes, and minimizing stops is minimizing cycles.

This is a different cost model from the one used on a superscalar machine, where the hardware’s own scheduler decides the effective cycle count. On a VLIW, the compiler’s stop placement is the cycle count, and a missed opportunity to remove a stop is a direct slowdown. Compilers therefore treat stop placement as part of scheduling rather than as a post-pass, and the scheduler’s priority function includes a term for whether the boundary can be left open.

The failure mode is subtle. A stop placed too early costs a cycle; a stop omitted where one was needed produces code that executes a dependent operation before its input is ready, which on a machine without interlocks produces a wrong answer silently. VLIW architectures without interlocks therefore depend on the compiler being correct about every dependence, and a single missed memory dependence produces a bug that appears only for particular alignments or particular inputs.

Why the Model Persists

The pure VLIW model lost the commercial argument to superscalar designs that reorder in hardware, because hardware reordering adapts to the actual run-time behaviour while a compiler’s schedule adapts only to its static model. A compiler that assumed a four-cycle load latency produced code that stalled, or produced a wrong result on a machine without interlocks, when the real latency differed, and a binary tuned for one implementation of an architecture did not transfer to another. Binary compatibility across implementations, which the superscalar model provides because the hardware resolves dependencies at run time, is the argument that decided the market.

The model survives in three places. Digital signal processors use it because their workloads are regular loops with predictable latencies, and because the compiler can be given exact pipeline tables. Graphics and machine-learning accelerators use a related model, where a wide instruction controls many lanes and the compiler’s job is to keep the lanes busy. And the ideas persist inside superscalar compilers, where the packer’s slot constraints reappear as port pressure: the modern equivalent of slot assignment is choosing which execution port each operation uses, and the equivalent of the empty slot is a cycle where a port sits idle.

The transferable lesson is about the interface between scheduling and encoding. Any machine with a fixed-width instruction and a fixed number of issue slots forces the scheduler to think in units of the encoding, not in units of time. The compiler that gets this wrong produces a schedule that is optimal as a cycle assignment and impossible to encode, and the repair — moving operations between bundles — invalidates the latencies the schedule was built on.