Using sysi · the backends

RV64 and C

sysi has two ways out. sysi asm writes RISC-V assembly itself, with no C compiler in between: this is the backend whose output sysi validate checks, and the one sysk's kernel is built with. sysi c writes C from the same sysi: a second, independent backend to compare against, and the way sysp's benchmark tests run sysi's code.

What the RV64 backend does

module->rv64 takes a sysi module and returns GNU assembly text, which clang assembles and ld.lld links. Each function goes through the same steps, all in lower-func:

A sysi value is a 64-bit word, so there is one register class and no type to choose instructions by. What the backend does choose is the form of each instruction:

• Immediates. A constant small enough for an immediate (12 bits signed) becomes one: addi, andi, ori, xori, slti, a shift by slli/srli/srai; a comparison for equality with a constant becomes seqz or snez (after an xori when the constant is not 0).
• Fused branches. A comparison (lt, le, gt, ge, eq, ne) whose result is used only by its own block's branch is not computed at all: the branch compares, with blt, bge, beq or bne (operands swapped for gt and le). A constant operand is the zero register when it is 0 and is built with li in t0 or t1 just before the branch otherwise.
• Division by a constant without the divider: a shift for a power of two, a multiplication by a magic number for the rest (below). A rem after the div of the same operands in the same block is x − q·y, a mul and a sub.
• Register-free constants. A constant that no instruction reads from a register (it is only a call argument, a jump's or branch edge's argument, a returned value, an immediate or a fused branch's operand) gets no live range and no register: li builds it where it is moved, straight into the argument register or the block parameter's location.

Nothing else is optimized: there is no inlining, no common subexpression elimination and no code motion. The sysi's instructions are emitted in order, block by block.

sum, line by line

Here is the docs' example as the last make docs compiled it: its sysi on the left, and on the right the assembly (or the C) that came out of it. Select a line, on either side, to see what it became and why; or step through the function. The page re-runs the backend in JavaScript, rule for rule (dead code, the forms, liveness, live ranges, the scan, retargeting and the emission), on the sysi shown, and checks that it reproduces the assembly line for line before it links lines; where it does not, it links whole blocks instead and says so.

Registers, as live ranges

Classic linear scan gives each value one interval, from its first position to its last, and frees a register when the interval ends. sysi's allocator keeps more detail. For each block it records where the value is live there, its live range: from its definition (or the block's start) to its last use (or the block's end, when the value is live out of the block or its terminator reads it). A block parameter also lives at the last position of each predecessor, where the jump writes it. Between a value's ranges are holes: a loop counter is not live in the block after the loop, and its register can hold something else there.

The conflict rule. Two values may share a register when none of their ranges meet, with one exception: they may meet at a single position where one of them is an operand read by the instruction that defines the other. The instruction reads its operands before it writes its result, so an address can die in the register its loaded byte is born in.

The scan takes the values in order of their start (ties by number). For each it tries the value's preferences, then t3–t6, a0–a7, s1–s11, and takes the first register in which nothing conflicts with it. A register may hold several values whose ranges never meet, so nothing has to be expired. A value live after a call (one that is not its own definition, by the liveness within each block) may take only s1–s11, which the callee keeps. When no register will do, the scan looks for a register in which exactly one value is in the way and that value ends later: that value goes to the stack for its whole life and this one takes its register (of several such registers, the one whose occupant ends last). Otherwise this value goes to the stack.

Preferences put a value where it will have to be anyway: a parameter in the a-register it arrives in, a call's result in the one it comes back in, and a value whose last use is as a call's or a return's k-th word in that word's a-register. A preference is only the first register tried; if something there conflicts, the scan goes on, and a move does the rest.

Retargeting comes after the scan. A value made only to be passed to a block parameter is moved into the parameter's register, so that the edge's move disappears, when all of this holds: the value is defined in the jumping block and used once; the parameter is neither live out of that block nor read by its terminator, and no instruction of the block reads it after the value is made (the instruction that makes the value may: it reads first); the register is callee-saved if the value lives across a call; and nothing else in the register conflicts with the value (the parameter itself does not count: the jump writes it from the value, so the two may meet at the jump).

In the figure each row is a value of the function chosen above, in scan order, with one bar per live range (a point when the range is one position) and a dotted line across its holes; grey bands are blocks, a red dashed line a call; a register's name in grey after a row is a preference. Play the scan, or pick two values (their names or bars) to test the conflict rule on them.

In the code

The live ranges and the conflict rule:

The scan, with its preferences and its one eviction:

Retargeting:

Division by a constant

On sysr's core (and its ISS, tools/rviss.rkt in sysr) a division or remainder takes 66 cycles, a multiplication 2 and most other instructions 1. When a div or rem has a constant divisor d, the backend asks div-plan in sysi/divconst.rkt for a plan. sysi's division truncates toward zero, as RISC-V's and C's do, and x is any 64-bit word read as signed.

• d = 2^k, 1 ≤ k ≤ 62: an arithmetic shift right by k rounds down, which is wrong for a negative x. So a bias of 2^k − 1 is added first when x is negative, computed without a branch as (x >>_a 63) >>_l (64 − k): srai, srli, add, srai.
• Any other d from 3 up to 2⁶² (Granlund and Montgomery's method): take the smallest s for which M = ⌈2^64+s/d⌉ is below 2⁶⁴ and the error e = M·d − 2^64+s satisfies 0 < e ≤ 2^s+1. Then the quotient is the high word of x·M (mulhsu: x signed, M unsigned), shifted right arithmetically by s, plus 1 when x is negative (srli by 63).
• The remainder is x − q·d in both cases: the quotient, then slli (or li and mul) and sub.

Every other divisor (1, a negative one, a large one) keeps div and rem. Why the magic plan is right for every x is a short argument in the header of divconst.rkt. sysi validate does not take the backend's word for it: with the same div-plan it checks the plan's side condition itself (plan-ok?), then has z3 prove the machine code equal to the plan's terms (div-term, rem-term); The machine code, checked explains that side. Try a divisor and a dividend: the page builds the plan as div-plan does, emits what the backend would (x in t3, the result in t4) and runs it.

The frame and the convention

The frame is laid out from the stack pointer up: the outgoing stack arguments (words past the eighth), the function's slots (memory sysi addresses with addr), the spill words, the callee-saved registers the function uses, and ra if it makes a call; rounded up to 16 bytes. A function with no calls, slots or spills, like sum, has no frame at all and never touches sp. run keeps values in s1 and s2 across its calls, so it saves and restores them.

Calls, returns, the entry and every edge into a block with parameters are parallel moves: a set of copies between locations that must look as if they happen at once. parallel! does any copy whose destination no other copy still reads; when only a cycle is left (say a0 ← a1 and a1 ← a0), it parks one source in t0 and goes on. A register-free constant is a source like any other, built with li in its destination. The convention is LP64's: arguments in a0–a7 and then on the stack, results in a0 and a1. A w32 crosses a call sign-extended, as the convention wants, though sysi keeps it zero-extended: the backend converts at each call, entry and return (addiw one way, slli/srli by 32 the other).

Blocks keep their labels in the output, sum.b1 and so on, as local symbols; the validator finds the blocks in the linked ELF by them. A jump to the block that follows is left out. A branch whose else side needs moves gets a local label of its own (.L, the function's name, _else and a count), where those moves go before the jump.

Custom instructions: --insn

sysr's core has custom instructions (an R-type with opcode 0x0b, for example). sysi asm --insn bsum=0x0b,0,0 makes every call to the extern bsum that instruction, in place: its two arguments are rs1 and rs2, its result rd, written with the assembler's .insn r directive. Such a call is not a call for the allocator: it does not force values into callee-saved registers, and its arguments are read from registers like any instruction's. sysr's custom-instruction demo, built so against the ULX3S platform file, prints on the ISS what its other builds print. The validator reads what the instruction does from custom-spec in sysr's custom.sysr, which isa.sysr's exec-spec runs for the custom-0 opcode.

A C file holding the assembly: --as-c

sysk's build compiles a kernel.c. --as-c (rv64-as-c) wraps the assembly in one top-level __asm__ statement, a string per line, so a build that compiles a .c file takes sysi's assembly unchanged. The start of sum's output, wrapped:

The C backend

module->c is a second backend from the same sysi, written to be obviously faithful rather than fast: each sysi function becomes a C function over uint64_t words named sysi_f_NAME, with one C variable per sysi value, a label per block and a goto per jump. Block parameters are assigned through temporaries (j0, j1, …), which is a parallel move in C. Memory goes through may_alias types (sysi_u8 … sysi_u64), so clang cannot reorder loads and stores by C's type rules, which sysi does not have. Signed comparisons, division and arithmetic shifts cast to int64_t. Toggle the figure above to C to see sum this way.

Around each function sits a wrapper with the signature sysp's own C backend would give it (int64_t sum(buf_u8 xs)), which splits sysp's values into words by the ABI and back. So the C test programs and assembly written against sysp's C call sysi's code unchanged. Externs go the other way, through adapters (sysi_x_sysp_alloc and so on). Hosted, the runtime is calloc and free; with --freestanding, the platform's prototypes only.

How the backends are tested

Cycles

Cycles on sysr's ISS, which counts them exactly. Each program is counted twice: the whole run, as tests/rv64-test.rkt prints it, and the run outside put_byte, the test runtime's routine that waits for the UART, as tools/profile.rkt (below) prints it. A faster program reaches the UART sooner and waits there longer, so the whole run understates a difference in the code. The middle column is sysi's RV64 before the changes this page describes (one interval per value, every division by the divider, comparisons computed and then branched on).

Outside put_byte, sysi's RV64 now takes 24% fewer cycles than before on the features program and 47% fewer on the benchmark. clang's code from the same sysi is still faster, mostly because it inlines: the driver's next ends in % m, and once next is inlined into a caller that passes a constant, clang divides by that constant with a multiplication. sysi's RV64 does not inline, and for now cannot: sysi validate matches the machine code's calls to the sysi's one to one.

sysk's kernel is built with sysi's RV64. With these changes the same kernel calls cost 17.6% fewer cycles in the functions sysi compiles, and that code has 6,693 instructions where it had 8,085. An earlier version of this page also compared sysk built three ways (sysp's C, sysi's C and sysi's RV64) on a run that booted, ran two shell commands and exited; that run cannot be repeated, because sysk no longer has an exit command, so the row is gone rather than carried over with numbers from an older kernel.

Where the cycles go. tools/profile.rkt builds sysp programs through sysi's RV64 (with --c, through sysi's C and clang -O2), links them with the test runtime and runs them on the ISS one instruction at a time, adding each instruction's cycles to its kind and to the function it is in. It prints the total, the cycles outside put_byte, the cycles by kind, and the functions that take the most, with their calls and cycles per call. With --elf it runs an executable already built, such as sysk's kernel, with --input's text arriving on the UART, until the console shows --until's text.

Whether the RV64 code is right is not left to these tests: The machine code, checked shows how each block of it is checked against its sysi.