CISC-V: an exploratory code compression for RISC-V

After months of trying to get around to it, I finally have a straw-man level system of compressing RISC-V code by squashing pairs of opcodes into a single 32-bit packet rather than squashing individual opcodes into 16-bit packets in order to address issues with unaligned 32-bit instruction words.

The intent is to make a minimal implementation possible which can decode the first slot easily while simultaneously reformatting the packet to expose the B slot for interpretation by the same decoder on the next step. But also to make compressed code more digestible for wide, multi-issue implementations.

Not to imply that performance cores want compressed code. Merely that if they’re stuck with it as a compatibility constraint then it shouldn’t be so painful.

It’s still not a fully defined thing. Just a thought experiment gone a little too far.

This takes 1/4 of the total instruction coding space, meaning it steals 1/3 of the space occupied by RVC. It’s assumed that the remaining 2/3 of RVC won’t be used in conjunction with this as that would undermine the objectives given below.

Why?

To make compressed code less of an impediment to high-end cores, while teasing a couple of side benefits. In particular:

To avoid the problems of unaligned 32-bit instructions
To avoid the other problems with mixed-size instructions
To exploit inter-opcode redundancies
To use much less opcode space
To dress up like a CISC architecture in order to gain its powers
To maintain the conventional 2-source, 1-destination data flow model by executing 32-bit packets sequentially as two separate instructions
To expose macro-op fusion opportunities within a 32-bit word when executing whole packets at once

Basically, I saw too many complaints about the various consequences of 16-bit aligned instructions mixed with 32-bit aligned instructions, and so I started thinking about it myself, and did some very rough hacking to see how I might solve it, and now I’m at the stage which I present here, which I hope is good enough to get the general idea across and demonstrate that the compression can work under the given constraints.

If you’re coming to this from the point of view of out-of-order wide multi-issue pipelines then I’m hoping you’ll be able to just chuck whole 32-bit packets through the front end as single instructions and then do µ-op fission in the usual way. Control flow only changes between whole packets.

Status

This is just an exploration, not a formal RISC-V proposal. All things are subject to change and much needs to be solidified before it can be implemented.

The results here are intended to establish the viability of the compression and to give a view on mindset and intent which motivated decisions, compromises, and blind hope.

Most of this document focuses on the cheap end, and how it might minimise the cost of implementation. Performance cores just get the occasional hint here and there about shortcuts they might take to avoid pain.

Packet structure

A packet comprises two instructions compressed into a 32-bit instruction word. There are four register fields (the three standard ones, plus one more in part of funct7) which are shared between two regular RISC-V instructions:

The mapping of fields to different instruction operands is described by a frame. Different frames and different opcode pairs within each frame are currently enumerated in the ten free bits in opcode, funct3, and two bits of funct7 (two bits of opcode are reserved to identify this encoding scheme). More on “enumeration” and its decoder implications later.

No new instruction semantics are introduced; some optional instructions are included. A frame merely compressed two consecutive instructions into one 32-bit packet. The first instruction (generally) has its source register fields aligned to the source register fields of 32-bit opcodes, but the usual destination register field is (generally) the register written by the second instruction. Other fields are recycled and repurposed according to the specific frame structure they follow.

For example, a frame may designate a source register as also the destination register to save encoding space, or elide the destination register slot the first instruction and a source register slot of the second instruction and hard-code them as a temporary register.

Immediates are 5-bit by default, aliasing with a register index. When this is insufficient the frame may repurpose another register field to make a ten-bit immediate. When ten bits is too many (e.g., the index for bit shifts on a 64-bit platform) the immediate-consuming instruction is duplicated in the list of opcodes the frame supports, and the choice between the two (or four, or eight) copies of the same instruction serves as an extra bit (or two or three).

For chain rules, temporary storage is used and not encoded in the packet at all. It’s left to the implementation to decide what kind of path this data takes, with the caveat that it must be exposed architecturally for exceptions. The possibility is held open for the decoder to hard-code the temporary register as x31 or x7 if this does not impede optimisation (see Exceptions and interrupts).

Frame structures are signalled by the opcode field. Each frame has a number of opcode pair configurations it supports, and these are enumerated and rounded up to a power of two.

Instruction pairs only allow control flow changes in the second slot. Branch targets are always 32-bit aligned.

A frame might pose a question like “how do we implement load with base address write-back?” and then encapsulate the two instructions which implement that (load and addi) by re-using operands from the first instruction in the second (rbase -> rdest, rbase -> rs1, offset -> immediate), and then unroll that across all the opcodes (lb, lbu, lh, etc..) it needs to complete the set.

Typical savings come from sharing rd and rs1 (as rsd) encoding, and from ‘chain’ rules where the first result is used only by the second operation before being discarded, and so neither the destination register nor its reference in the next op need to be encoded explicitly. Implicit sp is used a lot as well, but that saving is usually spent on a longer offset for large stack frames.

Decoding and execution

In the simplest implementation an instruction decoder would decode the first slot normally (with the caveat that the destination register is not in the usual location), while also preparing another conventional 32-bit instruction word to feed back to the same instruction decoder for the next decode step.

Alternatively, an implementation might ingest the packet as a single instruction and split it into µ-ops at a more convenient stage in the pipeline. A more aggressively optimised implementation could fuse them into a single operation when practical.

Regardless of the implementation a valid packet has the architectural effect of two ordinary RISC-V instructions executed sequentially, each consuming its operands and producing its normal architectural result in turn, with slot B observing the effects of slot A. Some combinations may have to be excluded from permitted encodings if they have problematic implications in high-performance implementations. The intent is to capture such cases explicitly if they’re common but not to leave them as performance landmines if they’re rare.

Similarly, some packets, like rsd-alu-pair, specify separate destination registers for each slot, meaning they’re able to encode cases where the second slot must use the result of the first. This might offer code density gains but could raise pipeline headaches, so encoding such dependencies should probably be prohibited. If it remains legal then it must still behave as if sequential.

At present there’s no optimisation for ease of decode, other than an attempt to align the operand fields consistently. The remaining ten bits are a naive enumeration of all the allowed permutations, with little organisation into bits. That’s to be addressed later, but ten bits is at least better than 32.

Exceptions and interrupts

If an exception occurs inside a packet then the architectural state must be properly resolved such that execution can resume at the appropriate slot within a packet, as needed. If the first slot did not cause the exception then architectural state must be updated accordingly, as if the two slots execute sequentially.

Since a restart needs to distinguish which instruction caused the fault, bit 1 of the PC can be used to signal slot B (dressing up as if we’re executing two 16-bit instructions). This mechanism is only required for restarts and doesn’t have to have optimal performance. Normal branch and jump targets are always 32-bit aligned, and for all purposes outside of exception and interrupt handling PC can safely be assumed to be 32-bit aligned.

Interrupts are assumed to follow the same protocol as exceptions. It is hoped (TBD) that an implementation would be able to meet the architectural model while deferring interrupts until completion of the whole packet in order to avoid complexity.

The other obvious state needed for a restart is the temporary value used in chain operations.

Logically one could hard-code this temporary during instruction decode as x31 (which doesn’t exist on RV32-E, so maybe x7 instead?) so it’s automatically saved; but some implementations may not appreciate this constraint, and it would be preferable for such a named register to not be guaranteed to retain a particular value after chain packets in normal operation. The intermediate value should only be considered reliably written back when forced by an exception or interrupt.

Alternatively, just expose it in a CSR. I’m not sure what’s best for the most economical implementations.

Another alternative for exceptions, if an implementation doesn’t want to deal with the complexity at all and has the necessary machinery, could be to cancel the whole packet (reversing the effects of slot A where necessary) and for the exception handler to simulate the pair of instructions one at a time.

Breakpoints

I assume these can be handled much the same way as exceptions, in the case of hardware breakpoints, or with a couple more rounds of rewriting in-place using standard 32-bit instructions.

The encoding (provisional)

Here’s what I came up with. Opcodes are enumerated simply to demonstrate that they can actually be encoded into 32 bits while the frames continue to evolve. The current assignment of the bit values is not how it should be done, just something expedient.

Bits marked p below are the bits used to enumerate the opcode combinations available in each frame. The values for the integer stored in the p bits are given in the tables following the frame structure. It’s just a provisional assignment and hasn’t been tuned for a realistic decoder.

Where the enumeration jumps by more than one, and where instructions are marked “×n”, that’s where bits of the opcode enumeration have been taken to extend the immediate range. The plan, here, is to align the bits which choose between duplicate opcodes to always land in the same positions in every frame, so that immediates decode consistently (give or take masking to the proper length).

frame layouts

alu-alu-chain

Two ALU operations, the second consuming the first’s result.

slot B	slot A
	addi ×2	add	andi	slli	sltu	srliw	sub
addi ×2	0	2	3	4	5	6	7
add	16	18	19	20	21	22	23
and	24	26	27	28	29	30	31
or	32	34	35	36	37	38	39
slli	40	42	43	44	45	46	47
srli	48	50	51	52	53	54	55
sub	56	58	59	60	61	62	63

slot B	slot A
	addi ×2	and	or	sltiu	srli	xor	xori
addi ×2	64	66	67	68	69	70	71
add	80	82	83	84	85	86	87
andi	88	90	91	92	93	94	95
or	96	98	99	100	101	102	103
slli	104	106	107	108	109	110	111
sltiu	112	114	115	116	117	118	119
xor	120	122	123	124	125	126	127

index-mem-chain

Scaled-index addressing: compute base + i*width and access it.

slot B	slot A
	add
lbu	0
sb	1

slot B	slot A
	sh1add
lhu	2
sh	3

slot B	slot A
	sh2add
lw	4
sw	5

slot B	slot A
	sh3add
ld	6
sd	7

pre-inc-pair

Advance a pointer, then access through it (pre-increment).

slot B	slot A
	addi
ld	0
sd	1

slot B	slot A
	addi
lw	2
sw	3

slot B	slot A
	sh3add
ld	4
sd	5

slot B	slot A
	sh2add
lw	6
sw	7

post-inc-pair

Access through a pointer, then advance it (post-increment).

slot B	slot A
	ld	sd
addi	0	1

slot B	slot A
	lw	sw
addi	2	3

mem-sp-pair

Two adjacent stack accesses one word apart – a spill or reload pair.

slot A	slot B
lx	lx	0
sx	sx	1

mem-base-pair

Two adjacent accesses through one base register, one data width apart.

slot A	slot B
lbu	lbu	0
lhu	lhu	1
lw	lw	2
ld	ld	3
sb	sb	4
sh	sh	5
sw	sw	6
sd	sd	7

load-alu-chain

Load a value and immediately compute with it.

slot B	slot A
	lw ×2	ld ×2
addi ×2	0	2
add	8	10
addw	12	14
and	16	18
andi	20	22
maxu	24	26
or	28	30
slli	32	34
sltiu	36	38
sltu	40	42
srli	44	46
srliw	48	50
sub	52	54
xor	56	58
xori	60	62

alu-store-chain

Compute a value and store it.

slot B	slot A
	addi ×2	add	addw	and	andi	maxu	or	slli	sltiu	sltu	srli	srliw	sub	xor	xori
sw	0	2	3	4	5	6	7	8	9	10	11	12	13	14	15
sd	16	18	19	20	21	22	23	24	25	26	27	28	29	30	31

addi-store-chain

Form a value – constant, copy or sp-relative address – and store it.

slot B	slot A
	addi
sb	0
sh	1
sw	2
sd	3

addi-store-off-chain

Compute a value from one base and store it at an offset from another.

slot B	slot A
	addi
sb ×2	0
sh ×2	2
sw ×2	4
sd ×2	6

load-store-chain

Copy a value from one memory location to another.

slot A	slot B
lbu	sb ×4	0
lhu	sh ×4	4
lw	sw ×4	8
ld	sd ×4	12

load0-load10-chain

Pointer chase: bare first load, the second carries a wide offset.

slot B	slot A
	lx
lb	0
lbu	1
lh	2
lhu	3
lw	4
lwu	5
ld	6

load5-load5-chain

Pointer chase with BOTH loads offset: a pointer in a slot, then indexed.

slot B	slot A
	lx
lb	0
lbu	1
lh	2
lhu	3
lw	4
lwu	5
ld	6

load-base-branch-pair

Load a value and branch on whether it is zero; the value survives.

slot B	slot A
	lb	lbu	lh	lhu	lw	lwu	ld
beqz	0	1	2	3	4	5	6
bnez	7	8	9	10	11	12	13

load-sp-branch-pair

Load a stack slot and branch on whether it is zero; the value survives.

slot B	slot A
	lw	ld	lbu
beqz	0	1	2
bnez	3	4	5

inc-branch-pair

Step a loop counter by one and branch on the comparison.

slot B	slot A
	inc
beq	0
bne	1
blt	2
bltu	3
bltu_r	4
bge	5
bgeu	6
bgeu_r	7

slot B	slot A
	dec
beq	8
bne	9
blt	10
bltu	11
bltu_r	12
bge_r	13
bgeu	14
bgeu_r	15

bit-test-branch-chain

Test a bit or bit-field and branch on the result.

slot B	slot A
	andi ×2	slli ×2	srli ×2
beqz	0	2	4
bnez	6	8	10
beq	12	14	16
bne	18	20	22

li-branch-chain

Compare a register against a constant and branch.

slot B	slot A
	li ×8
beq	0
bne	8
blt	16
bge	24
bltu	32
bgeu	40

li-czero-chain

Materialise a constant and conditionally zero it – one arm of a select.

slot B	slot A
	li
czero.eqz	0
czero.nez	1

czero-or-chain

Finish a conditional select: merge the surviving arm into the result.

slot B	slot A
	czero.eqz	czero.nez
or	0	1

macro-op-pair

Both halves of ONE computation over the same operands (mul/mulh, div/rem), declared as a pair so an implementation can fuse them.

slot B	slot A
	mulh	mulhu	mulhsu
mul	0	1	2

slot B	slot A
	add	addw
sltu	4	5

slot B	slot A
	div
rem	6

slot B	slot A
	divu
remu	7

slot B	slot A
	divw
remw	8

slot B	slot A
	divuw
remuw	9

rsd-alu-pair

Two in-place ALU updates, each rewriting its own source register.

slot B	slot A
	slli ×2	addi	li	addiw	andi	slliw	srli	add	sub	mul	or	sh1add	sh2add	sh3add	czero.nez
li ×8	0	2	3	4	5	6	7	8	9	10	11	12	13	14	15
addi ×4	128	130	131	132	133	134	135	136	137	138	139	140	141	142	143
slli	192	194	195	196	197	198	199	200	201	202	203	204	205	206	207
add	208	210	211	212	213	214	215	216	217	218	219	220	221	222	223
or	224	226	227	228	229	230	231	232	233	234	235	236	237	238	239
czero.eqz	240	242	243	244	245	246	247	248	249	250	251	252	253	254	255

prologue-pair

Function prologue: reserve the stack frame and save the return address.

slot B	slot A
	addi
sw	0
sd	1

epilogue-pair

Function epilogue: release the stack frame and return.

slot B	slot A
	addi
jr	0
ret	1

dual-setup-pair

Two independent small moves or constants – argument marshalling.

slot B	slot A
	mv
addi4spn ×2	8
mv	10
li	11

slot B	slot A
	li ×2
addi4spn ×2	0
mv	4
li	6

slot B	slot A
	addi4spn
addi4spn ×2	12

load-call-chain

Load a function pointer and call through it (virtual dispatch).

slot B	slot A
	lw	ld
jalr ra	0	1
jalr t1	2	3

arg-call-pair

Set up an argument, then call through a hard-coded base register.

slot B	slot A
	mv	li	addi4spn	lw	ld	sw	sd	addi
jalr ra	0	1	2	3	4	5	6	7
jr t1	8	9	10	11	12	13	14	15

setup-jump-pair

Set up an argument or return value, then transfer control.

slot B	slot A
	mv	lbu	lw	ld
ret	0	1	2	3
jalr ra	4	5	6	7
jr	8	9	10	11

slot B	slot A
	li
ret	16
jalr ra	17
jr	18

slot B	slot A
	mv	lbu	lw	ld
j	20	21	22	23

slot B	slot A
	li
j	24

arith-jump-pair

A last in-place computation, then a control transfer.

slot B	slot A
	addi ×2	li ×2	addiw ×2	andi ×2	slli ×2	srli ×2	add	and	or	xor
ret	0	2	4	6	8	10	12	13	14	15
jalr ra	16	18	20	22	24	26	28	29	30	31
jr	32	34	36	38	40	42	44	45	46	47
j	48	50	52	54	56	58	60	61	62	63

The results

Random test files, compiled with RVC and run through a scheduler to try to pick out viable instruction pairs gives these results:

corpus          insns   pairs  packet%  realRVC%   vsRVC  to parity
testcase0       21875    4185    80.9%     81.6%   99.1%      -167
godot           90171   15823    82.5%     76.3%  108.1%     +5545
cpp-rv32       418345   92667    77.8%     71.0%  109.7%    +28786
cpp-rv64       409200   87664    78.6%     71.2%  110.4%    +30274
musl-rv32      118990   27712    76.7%     74.9%  102.4%     +2159
musl-rv64      102010   22208    78.2%     72.7%  107.6%     +5608
sqlite-rv32    192688   45512    76.4%     72.1%  105.9%     +8258
sqlite-rv64    189602   42689    77.5%     72.1%  107.5%    +10266
---------------------------------------------------------------------
RV32 aggregate 751898  170076    77.4%     72.2%  107.2%    +39036
RV64 aggregate 790983  168384    78.7%     72.2%  109.1%    +51693
COMBINED      1542881  338460    78.1%     72.2%  108.1%    +90729

This is suboptimal because it’s not using a compiler which optimises for the instruction set I’ve created. It’s also suboptimal because I’m using code compiled for RVC, which has register pressure that does not apply here, and so it uses more instructions than strictly necessary (at least in Clang’s case – GCC finds excuses to use more instructions regardless). I have some other test cases but the tabulation got mucky, so let’s just run with the above for now.

Development process

I vibe-coded an instruction scheduler which scans a corpus of assembly and attempts to find and fuse pairable instructions according to rules describing what a legitimate instruction pair would look like; just to get a feel for what sorts of pairing rules I could introduce. It simply looks at register usage to determine when a result is no longer needed, and which instructions can move past which other instructions.

This seemed easier than writing my own compiler to optimise a made-up instruction set which I hadn’t designed yet, but it also has limitations. There’s no expectation for it to yield runnable code; merely to give a feel for how things would pack if the nits can be worked out.

Then I randomly threw rules at it to see what would stick.

And I pivoted to laying out the bit patterns by hand in order to prove that the budgets were being met.

Attempting to draw things around the standard RISC-V frames brought out the four-register-field pattern shown above, while sweeping up the remaining bits for an unregulated mix of frame selection and opcode selection.

Then, I did a bad thing: I ran optimisers against an irresponsibly small corpus to see what could be squeezed out.

Here’s the tooling, such as it is: CISC-V experiment (content-warning: unchecked AI output)

It’s no longer human-readable. Claude has taken things in its own direction. Much of what it does is flaky and unreliable, and most of the code is only there as a toolkit for “what if?” queries posed to the AI. I don’t really want to think about working with that code by hand.

But it’s sufficient to get a gist of whether the ideas make sense and how they map to real code.

Pairing rule selection

I drew inspiration from classic CISC operations, proposals for macro-op fusion, and things other architectures do. And just kind of threw them all in there and mused openly to Claude about how that looked to me and asked it for feedback.

Claude was not a reliable witness, and led me down many garden paths of faulty analyses and losses of comprehension. But it was an exploration I could pick up on a whim with my phone, so it won on convenience.

It feels like it’s come out with a lot of redundancies; though often the apparent redundancies are just redistributions of immediate sizes to suit different idioms.

Biclique optimisation

Some (many?) instructions pair naturally with only a limited set of other instructions. Attempting to pair a free choice of any operation with free choice of any other operation isn’t fruitful. By cutting the frames into different sections with different purposes (often emulating different CISC instructions) it becomes easy to minimise the combinations which are worth making space for. Possibly (TBD) at the cost of decode complexity.

Conversely, rules like rsd-alu-pair avoid relationships between slots and so encoding freedom of operation order wastes nearly one bit, and removing that freedom realises more opportunities for tuning.

All this optimisation risks over-fitting and adding complexity to the decoder, so it must be done thoughtfully (Narrator: it has not been done thoughtfully).

Immediate sizing

This is gnarly. You get 5 bits by default, aliasing with a register index. Five bits can’t fully specify a bit shift on a 64-bit target. Five bits is often not enough for a lot of things. And you have to decide whether it’s signed or not.

In a lot of cases the thing to do is sacrifice another register operand to get a 10-bit immediate. Implicit SP with a 10-bit offset means you can get to a lot of local variables.

Also, the value of the immediate in one slot will often be scaled by the instruction choice in the other slot (e.g., addi gets its immediate scaled by 4 if it’s paired with lw), and of course memory access also uses its own implicit scaling.

Otherwise, duplicate the opcode in the opcode list to extend the immediate range by one bit.

Trawling through code there are patterns of step changes in immediate requirements. The specific corpus is an obvious source of this effect, and some artefacts of the original immediate limits of the existing architecture, but other things appear to be a legitimate reflection of the way code tends to work. I just kind of guessed. Claude helped. It did lead to a lot of redundancy, but I didn’t have many better ideas, so immediate shaping became a big factor in the design choices.

Enumeration

For the sake of a quick POC I just enumerated all the frames according to their population counts rounded up to powers of two, and hoped I wouldn’t run out of space. There’s scope to do this more intelligently, signalling specific conditions relevant to the instruction decoder in specific bits of the enumeration, but I haven’t put the effort in at this stage.

Load/store pairings

I was initially very reluctant to merge load/store data operands into interdependent arrangements with arithmetic, because it leaves no space for scheduling around memory delays. Eventually I resigned myself to accepting it, though, because without that there’s going to be a lot less compression.

Also, it opened up opportunities to hint at things that could be left out of direct ALU paths. Things like indirect branching via memory; where branch prediction (when present) typically goes ahead with its decision without seeing the data, and the data is only there to cancel the prediction after the fact if it was inconsistent.

Chaining with a base-register operand was less painful. In particular filling the gap RISC-V leaves with rb+k*ri address generation which, it turns out, can be done via temporary register without needing to save the intermediate result.

Future work

decode complexity

A major problem right now is that the enumeration of frames and opcodes within frames doesn’t really attempt to match established conventions about how the decoder can resolve details quickly. It does (generally) put rs1 and rs2 for the first instruction in the same slots, so they can be prepared early, but there are other details one wants to know soonish which could be surfaced but have not been.

With a bit of massaging it appears to be possible to reduce the signature of each frame type down to a handful of bits in the opcode field, and squeeze a signature for the transform required to turn the slot-B parameters into a slot-A frame in another handful of bits. But I have not written (or vibed) such an allocator yet.

how to approach that

What we have right now is ten bits of “deal with it later”, and 20 bits corresponding to operand fields in fairly regular positions. 1024 codepoints, only about 3/4 populated after rounding each frame up to a power of two.

What I believe is needed is to collate every codepoint by its slot-A operand patterns (including immediate sizes and positions) and to pack these bits together as a convenient decoder index. I think Claude said this was doable in about three or four bits.

Then, without regard to those bits, we need to sort the codepoints by the slot B operands in the same way, and pack these together in the same way, but in some different bits, so that we can begin the re-format of slot B into a shape the normal instruction decoder can ingest. One would also want a clear signal for branches and jumps, for the instruction prefetch pipeline.

There’s no guarantee that will resolve into a sensible number of bits, but I asked Claude to try and it said it might get away with three more bits, but I haven’t verified.

And in the cases where a list of opcodes contains repetitions of an opcode to make up extra immediate bits, that enumeration should be swizzled to put the redundant opcode selector at bit 30 or 31 of the word, so immediate decode is relatively consistent. This seems like the least hard problem, but it should be done.

quality

Another problem is lack of thoughtful optimisation and, conversely, gross overfitting to my limited test corpus.

And, of course, the regularity needs to be improved. Balancing regularity and generality against compression. And then factoring the cost model of a realistic compiler in and then fitting more tightly to that, and then reasserting regularity and generality all over again. Around and around and around…

That said, this adventure promotes itself as being CISC-inspired, so being a random bucket of overlapping things that seemed like good ideas is pretty on-brand.

sundries

And a toolchain would be nice, too. And an implementation. And from those, feedback into what makes a better target, and back around the tuning loops again with that insight in mind.

AI disclosure statement

Yep.