Control flow divergence and The Belt

The ISA documentation on the site is woefully out of date and we have no volunteer to resume the work on it; please accept my apologies. Here’s a conAsm fragment (from the printf() function as it happens) that shows carrying branches in use:

    eql(b4 %46, 108) %435 ^0,
    eql(b4 %46, 104) %434 ^0,
    brtrs(b0 %434, "printf$17_75", b5 %51) ^0,
    brfls(b1 %435, "printf$17_9", b8 %48/460, b10 %50/461) ^0,
    brs("printf$17_75", b2 %399) ^0,
    rd(w(128)) %399 ^263;

You see that the two branches to ebb $17_75 are carrying two different arguments, %51 for one and %399 for the other.

Ebbs don’t really “produce results”, except in the sense that they contain store operations that update memory. I think you mean more a notion of liveness or in-flight operands, those produced by an operation but that have not yet been consumed by all consumers. Live operands are initially created on the belt, and are consumed from the belt. If at any point there are more simultaneously live operands than fit in the fixed capacity of the belt (16 positions on a Silver, from which the above fragment was drawn) then the code must spill the excess, initially to scratchpad and ultimately, if scratch itself fills up, to memory. The specializer uses heuristics to decide which operands to spill. Spill and fill are a fact of life for any machine because there are always codes that exceed local resource constraints, although the compiler algorithms to do spilling are very different on a belt machine than on a general register machine.

Spilling is also done in a few other situations. For example, if an operand is created in one ebb and not consumed until much later after a long chain of branches then it is better code to spill it at point of production and fill it at point of consumption than to pass it along across many value-carrying branches.

Yes, each side has three variable-sized blocks, and within each block the element sizes are statically fixed (though not necessarily the same). In the exu side each block has a different op set, with the sets partitioned by phase, and each operation is complete in its set.

The flow side is different: only the flowBlock has operation elements like on the exu side, while in the con block the elements are bytes and in the ext block the elements are morsels big enough to hold a belt position number. Those flow ops that take an argument list (besides the branches there are the calls and various special ops including rescue, retire, and con) encode as much as they can in the flow block entry and put the rest of the list in the con and ext blocks. Each flow block entry has two bits to indicate how much has been put in the other blocks: 0/1/2/4 bytes and 0/1/2/3 morsels.

If the list is long enough that it doesn’t fit in an entry plus 4 bytes and 3 morsels then the op is ganged with a flowArgs pseudo op in the next slot, which provides another 4 bytes and three morsels. Rinse repeat. The maximal sizes of the blocks (for each family member) are set so that it is possible to encode a belt list with entries for every position, or a con with enough bits to express the largest possible operand. The constraints of the ext and con blocks are recognized by the specializer, so that (for example) it may encode two calls with few arguments in a single instruction, but only one call with a long argument list even though there are two slots supporting call.

Close.

For polyadic arguments the arg list uses the bits in both the bytes in con block and the morsels in ext block, interleaved by flow slot. The decoder has a compositing buffer holding all these bits for all slots. For a four bit morsel machine, each slot provides 44 bits (4 bytes + three morsels) so with 7 slots (typical of a mid-range Mill) the compositor has 308 bits. As the maximal arg list for such a member has 16 args of four bits, the maximal list needs 64 bits and the buffer can hold almost five such lists. More to the point, two slots provide 88 bits, whereas the maximal list needs 64, so any arg list will need at most two slots, one with the main op and one with a flowArgs op for the extras.

Actually, composition demand is greatest for con ops (literals). If our member has 128-bit (quad) operands then the 308 compositing bits can hold two quad literals, each literal using three slots with a slot left over for lagniappe.

In operation, the decoder selects the pair of two-bit fields for each slot right out of the flow block in the instruction buffer. That can be done without even knowing how many flow slots the instruction uses; the decoder will just select garbage bits beyond the end. The selected pairs go through a priority decode to set up muxes to select which bytes/morsels in the con/ext blocks belong to each slot. That decode/select takes a cycle, during which the con and ext blocks are being isolated by the instruction-level shifters. The following cycle the previously set up muxes route bits from the isolated con/ext blocks to the correct position in the compositing buffer, zero-filling as necessary. At this point we have the full 308 bits as one bit-array; any garbage bits are at the end of that array and are ignored because they belong to slots that the instruction doesn’t use.

The compositing buffer has a bunch of selector muxes to peel off particular fields that would be of interest to one or another op. Starting at each 44-bit slot boundary, there’s a selector that grabs a four-byte word that had come from the con block. Each of the three morsels that came from the ext block has its own selector. There a selector that starts at the slot and extends over the bits of adjacent slots that provides big con literals, and another that grabs big arg lists. Con’s are right-aligned on slot boundaries in the compositor, so leading zeroes happen; there’s a “complement” bit in the main opcode that causes the selected literal to be one’s complemented during selection so we can express negative literals (note: the encoding uses ones’ complement literals so we don’t need an adder in the decoder). Arg lists are left-aligned on slot boundaries in the compositor so garbage bits are at the end; we know from other arguments in the the operation how long the list is, so the decoder actually gives the FU a single maximal list (64 bits) plus a one-hot mask (16 bits) that says which list position is valid.

All the various selecting for all the slots takes place in parallel in the second decode cycle. During that same cycle we have decoded the main opcode (from the flow block that was isolated in the first cycle) enough to know which of the selected fields are meaningful for this particular op, so only the meaningful fields go to the FUs as operation arguments. Many of the FU arguments are belt numbers, either singly or as lists. Belt remapping is done by the flow and exu sides together, because both sides are evaluating or dropping operands concurrently. This takes place in the third decode cycle, a cycle ahead of use. That is, the remapper tracks what will be happening on the belt in the following cycle. Bulk rename (br/call/retn/rescue) arg lists are actually easier then simply belt eval/drop (add, LEA, etc) because they don’t happen until after still another instruction boundary. The tightest timing is for con, which drops a cycle ahead of everything else. To make that work at high clock the belt addresses the literal directly inside the compositing buffer without moving it someplace else. Of course, the compositor will be reused for a different instruction the following cycle, so the literal does get moved out too, but there’s a whole cycle for that.

Whew! Well, you wanted to know.