Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #118183 > unrolled thread

Really compressed instruction streams

Back to article view | Back to comp.arch

Contents

  Really compressed instruction streams Thomas Koenig <tkoenig@netcologne.de> - 2026-09-24 20:04 +0000
    Re: Really compressed instruction streams MitchAlsup <user5857@newsgrouper.org.invalid> - 2026-09-24 22:17 +0000
      Re: Really compressed instruction streams BGB <cr88192@gmail.com> - 2026-09-24 18:00 -0500
      Re: Really compressed instruction streams scott@slp53.sl.home (Scott Lurndal) - 2026-09-25 14:39 +0000
        Re: Really compressed instruction streams cross@spitfire.i.gajendra.net (Dan Cross) - 2026-09-25 20:53 +0000
        Re: Really compressed instruction streams antispam@fricas.org (Waldek Hebisch) - 2026-10-05 23:10 +0000
          Re: Really compressed instruction streams John Levine <johnl@taugh.com> - 2026-10-06 02:46 +0000
    Re: Really compressed instruction streams quadibloc@invalid.com (John Savard) - 2026-09-24 22:37 +0000
      Re: Really compressed instruction streams MitchAlsup <user5857@newsgrouper.org.invalid> - 2026-09-25 00:37 +0000
        Re: Really compressed instruction streams scott@slp53.sl.home (Scott Lurndal) - 2026-09-25 14:42 +0000
    Re: Really compressed instruction streams Robert Finch <robfi680@gmail.com> - 2026-09-24 20:56 -0400
      Re: Really compressed instruction streams Thomas Koenig <tkoenig@netcologne.de> - 2026-09-25 18:56 +0000
    Re: Really compressed instruction streams Michael S <already5chosen@yahoo.com> - 2026-09-25 11:54 +0300
      Re: Really compressed instruction streams Thomas Koenig <tkoenig@netcologne.de> - 2026-09-25 15:05 +0000
    Re: Really compressed instruction streams Michael S <already5chosen@yahoo.com> - 2026-09-25 17:39 +0300
    Re: Really compressed instruction streams Stefan Monnier <monnier@iro.umontreal.ca> - 2026-09-25 11:46 -0400
      Re: Really compressed instruction streams BGB <cr88192@gmail.com> - 2026-09-25 16:09 -0500
        Re: Really compressed instruction streams MitchAlsup <user5857@newsgrouper.org.invalid> - 2026-09-25 22:59 +0000
          Re: Really compressed instruction streams BGB <cr88192@gmail.com> - 2026-09-25 18:51 -0500
            Re: Really compressed instruction streams scott@slp53.sl.home (Scott Lurndal) - 2026-09-28 15:26 +0000
              Re: Really compressed instruction streams BGB <cr88192@gmail.com> - 2026-09-28 17:42 -0500
        Re: Really compressed instruction streams BGB <cr88192@gmail.com> - 2026-09-26 03:21 -0500
      Re: Really compressed instruction streams Paul Clayton <paaronclayton@gmail.com> - 2026-09-27 21:12 -0400
        Re: Really compressed instruction streams BGB <cr88192@gmail.com> - 2026-10-01 15:42 -0500

Page 1 of 2  [1] 2  Next page →

#118183 — Really compressed instruction streams

It seems that the different CISC and compressed instruction sets
are ad-hoc (and not very good) attempts at compression of the
actual instructions that machines execute.  Pure RISCS have very
little compression, RISC-V has some, CISC has some more.  AMD's
micro-op cache goes some way towards this when it splits
x86_64 instructions into micro-ops.

So, the idea of using actual compression seems interesting.
This has been tried in the past, but it didn't catch on.

There are a few basic problems to be solved.  One that comes to
mind immediately is branch addresses.  If the instruction stream
is compressed, any bit of the compressed stream can start an
instruction, and calculating the target of a branch instruction
is not straightforward.  To avoid having to decode the whole
program, it would be necessary to create blocks of some sort,
which could be decoded on loading into a suitable cache level.

For example, one could make the Icache into a micro-op-store
and decode on fetching from L2.

Branch targets could then be in the form block,instruction in
block.  There would have to be an upper limit on the number
of instructions per block, leading to some waste for easily
compressible instructions.  Also, instructions which no
longer fit in a block would reduce the efficieny.

One would also have to look at PC-relative branches; these
would probably become block-relative + instruction in block.

Writing binutils for this kind of architecture would be fun,
in the sense of absoutely no fun at all.  Object code would
probably be uncompressed, with the poor guy implementing the
linker having to do all the dirty work.

The ISA to be compressed would not be limited by having to
fit into a container determined by byte or word sizes.
If one so desired, one could chose an ISA based on any
bit size, although having instructions based on an n-bit
package size (with multiples) would still make sense for
further decoding of the micro-ops.

Other thoughts?
-- 
This USENET posting was made without artificial intelligence,
artificial impertinence, artificial arrogance, artificial stupidity,
artificial flavorings or artificial colorants.

[toc] | [next] | [standalone]

#118187

Thomas Koenig <tkoenig@netcologne.de> posted:

> It seems that the different CISC and compressed instruction sets
> are ad-hoc (and not very good) attempts at compression of the
> actual instructions that machines execute.  Pure RISCS have very
> little compression, RISC-V has some, CISC has some more.  AMD's
> micro-op cache goes some way towards this when it splits
> x86_64 instructions into micro-ops.
> 
> So, the idea of using actual compression seems interesting.
> This has been tried in the past, but it didn't catch on.

Pitfalls...
 
> There are a few basic problems to be solved.  One that comes to
> mind immediately is branch addresses.  If the instruction stream
> is compressed, any bit of the compressed stream can start an
> instruction, and calculating the target of a branch instruction
> is not straightforward.  To avoid having to decode the whole
> program, it would be necessary to create blocks of some sort,
> which could be decoded on loading into a suitable cache level.

Realistically, adding 3-or-4-bits to IP (or equally restricting
IP to 60-DoubleWord address-bits would allow bit indexing at
FETCH.
 
> For example, one could make the Icache into a micro-op-store
> and decode on fetching from L2.

What happens when somebody (ld.so) writes into code space ??
What happens when SSD writes into code space ??
 
> Branch targets could then be in the form block,instruction in
> block. 

Or bit addresses (see above) and leave out blocks altogether.

>         There would have to be an upper limit on the number
> of instructions per block, leading to some waste for easily
> compressible instructions.  Also, instructions which no
> longer fit in a block would reduce the efficieny.

Packet and trace caches have this problem. After building a
packet-cache (1991) and seeing the instruction density (60%
filled and less than 1/2 as dense as normal instruction 
cache--I decided to go a different direction for my current
6-wide machine.
 
> One would also have to look at PC-relative branches; these
> would probably become block-relative + instruction in block.

Bit addressing solves this, too !!
 
> Writing binutils for this kind of architecture would be fun,

For a perverse definition of "fun".

> in the sense of absoutely no fun at all.  Object code would
> probably be uncompressed, with the poor guy implementing the
> linker having to do all the dirty work.

Imaging the poor guy trying to debug::

     ADD  IP,R7,#1234567
 
> The ISA to be compressed would not be limited by having to
> fit into a container determined by byte or word sizes.

Not at all--see Mill.

> If one so desired, one could chose an ISA based on any
> bit size, although having instructions based on an n-bit
> package size (with multiples) would still make sense for
> further decoding of the micro-ops.
> 
> Other thoughts?

[toc] | [prev] | [next] | [standalone]

#118191

On 9/24/2026 5:17 PM, MitchAlsup wrote:
> 
> Thomas Koenig <tkoenig@netcologne.de> posted:
> 
>> It seems that the different CISC and compressed instruction sets
>> are ad-hoc (and not very good) attempts at compression of the
>> actual instructions that machines execute.  Pure RISCS have very
>> little compression, RISC-V has some, CISC has some more.  AMD's
>> micro-op cache goes some way towards this when it splits
>> x86_64 instructions into micro-ops.
>>
>> So, the idea of using actual compression seems interesting.
>> This has been tried in the past, but it didn't catch on.
> 
> Pitfalls...
>   

Yes.

Fixed length: Cheapest;
16/32: Affordable;
Variable Bytes: Expensive;
Variable Bits: Impractical.

Often, one can get part of the way to the results of a more expensive 
solution by being more clever with the cheaper solution.


The stronger tools may seem like magic, but they don't come free.



>> There are a few basic problems to be solved.  One that comes to
>> mind immediately is branch addresses.  If the instruction stream
>> is compressed, any bit of the compressed stream can start an
>> instruction, and calculating the target of a branch instruction
>> is not straightforward.  To avoid having to decode the whole
>> program, it would be necessary to create blocks of some sort,
>> which could be decoded on loading into a suitable cache level.
> 
> Realistically, adding 3-or-4-bits to IP (or equally restricting
> IP to 60-DoubleWord address-bits would allow bit indexing at
> FETCH.
>   

If the bit lengths are variable, branch displacements and relocs are 
going to be straight up evil.


>> For example, one could make the Icache into a micro-op-store
>> and decode on fetching from L2.
> 
> What happens when somebody (ld.so) writes into code space ??
> What happens when SSD writes into code space ??
>   
>> Branch targets could then be in the form block,instruction in
>> block.
> 
> Or bit addresses (see above) and leave out blocks altogether.
> 
>>          There would have to be an upper limit on the number
>> of instructions per block, leading to some waste for easily
>> compressible instructions.  Also, instructions which no
>> longer fit in a block would reduce the efficieny.
> 
> Packet and trace caches have this problem. After building a
> packet-cache (1991) and seeing the instruction density (60%
> filled and less than 1/2 as dense as normal instruction
> cache--I decided to go a different direction for my current
> 6-wide machine.
>   
>> One would also have to look at PC-relative branches; these
>> would probably become block-relative + instruction in block.
> 
> Bit addressing solves this, too !!
>   
>> Writing binutils for this kind of architecture would be fun,
> 
> For a perverse definition of "fun".
> 
>> in the sense of absoutely no fun at all.  Object code would
>> probably be uncompressed, with the poor guy implementing the
>> linker having to do all the dirty work.
> 
> Imaging the poor guy trying to debug::
> 
>       ADD  IP,R7,#1234567
>   

Looks at hex dump of memory: White noise.

Branch goes wrong: White noise.
Or, if you compression is good enough, the instruction stream looks like 
something plausible, but completely wrong. Like if an LLM hallucinated 
ones' disassembler output.


>> The ISA to be compressed would not be limited by having to
>> fit into a container determined by byte or word sizes.
> 
> Not at all--see Mill.
> 
>> If one so desired, one could chose an ISA based on any
>> bit size, although having instructions based on an n-bit
>> package size (with multiples) would still make sense for
>> further decoding of the micro-ops.
>>
>> Other thoughts?

[toc] | [prev] | [next] | [standalone]

#118206

MitchAlsup <user5857@newsgrouper.org.invalid> writes:
>
>Thomas Koenig <tkoenig@netcologne.de> posted:
 <snip>
> 
>> For example, one could make the Icache into a micro-op-store
>> and decode on fetching from L2.
>
>What happens when somebody (ld.so) writes into code space ??

Generally it doesn't.   The code space is mapped into
read-only pages.   The RTLD updates the PLT and GOT, not
the code.

[toc] | [prev] | [next] | [standalone]

#118217

In article <NIvtS.6$MR2.5@fx39.iad>, Scott Lurndal <slp53@pacbell.net> wrote:
>MitchAlsup <user5857@newsgrouper.org.invalid> writes:
>>
>>Thomas Koenig <tkoenig@netcologne.de> posted:
> <snip>
>> 
>>> For example, one could make the Icache into a micro-op-store
>>> and decode on fetching from L2.
>>
>>What happens when somebody (ld.so) writes into code space ??
>
>Generally it doesn't.   The code space is mapped into
>read-only pages.   The RTLD updates the PLT and GOT, not
>the code.

Right.  The GOT is mapped into private R/W data space
specifically to avoid having to mutate R/O text.

I think 32-bit SPARC was an exception.

	- Dan C.

[toc] | [prev] | [next] | [standalone]

#118483

Scott Lurndal <scott@slp53.sl.home> wrote:
> MitchAlsup <user5857@newsgrouper.org.invalid> writes:
>>
>>Thomas Koenig <tkoenig@netcologne.de> posted:
>  <snip>
>> 
>>> For example, one could make the Icache into a micro-op-store
>>> and decode on fetching from L2.
>>
>>What happens when somebody (ld.so) writes into code space ??
> 
> Generally it doesn't.   The code space is mapped into
> read-only pages.   The RTLD updates the PLT and GOT, not
> the code.

AFAICS on popular architectures PLT is code.

-- 
                              Waldek Hebisch

[toc] | [prev] | [next] | [standalone]

#118485

According to Waldek Hebisch <antispam@fricas.org>:
>>>What happens when somebody (ld.so) writes into code space ??
>> 
>> Generally it doesn't.   The code space is mapped into
>> read-only pages.   The RTLD updates the PLT and GOT, not
>> the code.
>
>AFAICS on popular architectures PLT is code.

It is, but it's position independent read-only code
that jumps through an indirect address in the GOT.

-- 
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

[toc] | [prev] | [next] | [standalone]

#118190

On Thu, 24 Sep 2026 20:04:24 -0000 (UTC), Thomas Koenig
<tkoenig@netcologne.de> wrote:

>It seems that the different CISC and compressed instruction sets
>are ad-hoc (and not very good) attempts at compression of the
>actual instructions that machines execute.

That's certainly true of the schemes I've been coming up with.

But since it takes so much time to fetch stuff from DRAM, some
machines offer a mode where instructions are actually decrypted using
a block cipher after being fetched!
Given that, presumably the time cost of doing "real" compression on
program code is not excessive.
So, why doesn't anyone do this? I can think of many reasons why such a
scheme could cause agony... but I also see a simple, plain
alternative.
Why not just have a compressed disk format for executable files in an
operating system? Unpack them into conventional format when loading
them into memory. That saves space where it is more doable, where the
programs are lying idle, so they can be compressed with context
obtained from their whole length.

It doesn't achieve as much, but it avoids all the branching headaches.

John Savard

[toc] | [prev] | [next] | [standalone]

#118194

quadibloc@invalid.com (John Savard) posted:

> On Thu, 24 Sep 2026 20:04:24 -0000 (UTC), Thomas Koenig
> <tkoenig@netcologne.de> wrote:
> 
> >It seems that the different CISC and compressed instruction sets
> >are ad-hoc (and not very good) attempts at compression of the
> >actual instructions that machines execute.
> 
> That's certainly true of the schemes I've been coming up with.
> 
> But since it takes so much time to fetch stuff from DRAM, some
> machines offer a mode where instructions are actually decrypted using
> a block cipher after being fetched!

I remember (I think) IBM compressing pages, but not cache lines.

> Given that, presumably the time cost of doing "real" compression on
> program code is not excessive.

Once you have the HW budget, LemplZiv is quite efficient.

> So, why doesn't anyone do this?

Big memory became cheap enough; disks (and SSDs) became big enough.
Also I/O busses became fast enough that saving 40% memory cycles no 
longer paid off, once SW had to read the stuff in and convert it.

>                                 I can think of many reasons why such a
> scheme could cause agony... but I also see a simple, plain
> alternative.

> Why not just have a compressed disk format for executable files in an
> operating system? Unpack them into conventional format when loading
> them into memory.

How do you page the code directly from the disk into executable memory ?

>                   That saves space where it is more doable, where the
> programs are lying idle, so they can be compressed with context
> obtained from their whole length.

Programs lying idle can rest on the disk in memory format.
 
> It doesn't achieve as much, but it avoids all the branching headaches.
> 
> John Savard

[toc] | [prev] | [next] | [standalone]

#118208

MitchAlsup <user5857@newsgrouper.org.invalid> writes:
>
>quadibloc@invalid.com (John Savard) posted:
>
>> On Thu, 24 Sep 2026 20:04:24 -0000 (UTC), Thomas Koenig
>> <tkoenig@netcologne.de> wrote:
>> 
>> >It seems that the different CISC and compressed instruction sets
>> >are ad-hoc (and not very good) attempts at compression of the
>> >actual instructions that machines execute.
>> 
>> That's certainly true of the schemes I've been coming up with.
>> 
>> But since it takes so much time to fetch stuff from DRAM, some
>> machines offer a mode where instructions are actually decrypted using
>> a block cipher after being fetched!
>
>I remember (I think) IBM compressing pages, but not cache lines.

https://www.marvell.com/blogs/structera-xa-cxl-compression-every-gigabyte-counts.html

[toc] | [prev] | [next] | [standalone]

#118196

On 2026-09-24 4:04 p.m., Thomas Koenig wrote:
> It seems that the different CISC and compressed instruction sets
> are ad-hoc (and not very good) attempts at compression of the
> actual instructions that machines execute.  Pure RISCS have very
> little compression, RISC-V has some, CISC has some more.  AMD's
> micro-op cache goes some way towards this when it splits
> x86_64 instructions into micro-ops.
> 
> So, the idea of using actual compression seems interesting.
> This has been tried in the past, but it didn't catch on.
> 
> There are a few basic problems to be solved.  One that comes to
> mind immediately is branch addresses.  If the instruction stream
> is compressed, any bit of the compressed stream can start an
> instruction, and calculating the target of a branch instruction
> is not straightforward.  To avoid having to decode the whole
> program, it would be necessary to create blocks of some sort,
> which could be decoded on loading into a suitable cache level.
> 
> For example, one could make the Icache into a micro-op-store
> and decode on fetching from L2.
> 
> Branch targets could then be in the form block,instruction in
> block.  There would have to be an upper limit on the number
> of instructions per block, leading to some waste for easily
> compressible instructions.  Also, instructions which no
> longer fit in a block would reduce the efficieny.
> 
> One would also have to look at PC-relative branches; these
> would probably become block-relative + instruction in block.
> 
> Writing binutils for this kind of architecture would be fun,
> in the sense of absoutely no fun at all.  Object code would
> probably be uncompressed, with the poor guy implementing the
> linker having to do all the dirty work.
> 
> The ISA to be compressed would not be limited by having to
> fit into a container determined by byte or word sizes.
> If one so desired, one could chose an ISA based on any
> bit size, although having instructions based on an n-bit
> package size (with multiples) would still make sense for
> further decoding of the micro-ops.
> 
> Other thoughts?

Micro-ops are the opposite of compressed instructions. They are 
typically wider than the instructions encoded.

Writing software for dumps of code and other such things is much more 
expensive (takes more time) when things are not byte aligned.

Even with compressed instructions the savings in memory space is 
typically < 40%. The savings in execution time is far less.

Instruction size is an engineering issue. With most instructions, 
including constants, fitting into 36 bits or less, a 32-bit instruction 
parcel covers a high percentage of instruction use.

Variable bit length instructions could be asking for a nasty instruction 
decoder.

No system is going to be perfect.

Compressing the instruction stream may be useful for transferring the 
code over wire and for storage. Once in the CPU’s memory I think it is 
less important for compression. For instance, micro-ops use much more 
memory than the instructions from the program code, but they are used in 
some designs.

[toc] | [prev] | [next] | [standalone]

#118216

Robert Finch <robfi680@gmail.com> schrieb:
> On 2026-09-24 4:04 p.m., Thomas Koenig wrote:
>> It seems that the different CISC and compressed instruction sets
>> are ad-hoc (and not very good) attempts at compression of the
>> actual instructions that machines execute.  Pure RISCS have very
>> little compression, RISC-V has some, CISC has some more.  AMD's
>> micro-op cache goes some way towards this when it splits
>> x86_64 instructions into micro-ops.
>> 
>> So, the idea of using actual compression seems interesting.
>> This has been tried in the past, but it didn't catch on.
>> 
>> There are a few basic problems to be solved.  One that comes to
>> mind immediately is branch addresses.  If the instruction stream
>> is compressed, any bit of the compressed stream can start an
>> instruction, and calculating the target of a branch instruction
>> is not straightforward.  To avoid having to decode the whole
>> program, it would be necessary to create blocks of some sort,
>> which could be decoded on loading into a suitable cache level.
>> 
>> For example, one could make the Icache into a micro-op-store
>> and decode on fetching from L2.
>> 
>> Branch targets could then be in the form block,instruction in
>> block.  There would have to be an upper limit on the number
>> of instructions per block, leading to some waste for easily
>> compressible instructions.  Also, instructions which no
>> longer fit in a block would reduce the efficieny.
>> 
>> One would also have to look at PC-relative branches; these
>> would probably become block-relative + instruction in block.
>> 
>> Writing binutils for this kind of architecture would be fun,
>> in the sense of absoutely no fun at all.  Object code would
>> probably be uncompressed, with the poor guy implementing the
>> linker having to do all the dirty work.
>> 
>> The ISA to be compressed would not be limited by having to
>> fit into a container determined by byte or word sizes.
>> If one so desired, one could chose an ISA based on any
>> bit size, although having instructions based on an n-bit
>> package size (with multiples) would still make sense for
>> further decoding of the micro-ops.
>> 
>> Other thoughts?
>
> Micro-ops are the opposite of compressed instructions. They are 
> typically wider than the instructions encoded.
>
> Writing software for dumps of code and other such things is much more 
> expensive (takes more time) when things are not byte aligned.
>
> Even with compressed instructions the savings in memory space is 
> typically < 40%. The savings in execution time is far less.

The work I have seen is motivated by saving energy
for embedded systems.  They didn't use Micro-Ops, but
standard ISAs.  Here is a relatively recent example:
https://link.springer.com/article/10.1007/s10617-024-09290-2

It doesn't look too bad, but I am not holding my breath that
this will be used widely.

-- 
This USENET posting was made without artificial intelligence,
artificial impertinence, artificial arrogance, artificial stupidity,
artificial flavorings or artificial colorants.

[toc] | [prev] | [next] | [standalone]

#118200

On Thu, 24 Sep 2026 20:04:24 -0000 (UTC)
Thomas Koenig <tkoenig@netcologne.de> wrote:

> It seems that the different CISC and compressed instruction sets
> are ad-hoc (and not very good) attempts at compression of the
> actual instructions that machines execute.  Pure RISCS have very
> little compression, RISC-V has some, CISC has some more.  AMD's
> micro-op cache goes some way towards this when it splits
> x86_64 instructions into micro-ops.
> 

Can I ask what you find special in AMD's micro-op cache relatively to
Intel's?
To me it looks like Zen1 mostly copied 6 years earlier Sandy Bridge
tech. Following generations of Zen, while doing new things in other
parts of the core, left principles of micro-op cache mostly intact.

[toc] | [prev] | [next] | [standalone]

#118210

Michael S <already5chosen@yahoo.com> schrieb:
> On Thu, 24 Sep 2026 20:04:24 -0000 (UTC)
> Thomas Koenig <tkoenig@netcologne.de> wrote:
>
>> It seems that the different CISC and compressed instruction sets
>> are ad-hoc (and not very good) attempts at compression of the
>> actual instructions that machines execute.  Pure RISCS have very
>> little compression, RISC-V has some, CISC has some more.  AMD's
>> micro-op cache goes some way towards this when it splits
>> x86_64 instructions into micro-ops.
>> 
>
> Can I ask what you find special in AMD's micro-op cache relatively to
> Intel's?

Nothing in particular, it was just something I mentioned as an
example. Plus, I looked the format of AMD microops some time ago.

-- 
This USENET posting was made without artificial intelligence,
artificial impertinence, artificial arrogance, artificial stupidity,
artificial flavorings or artificial colorants.

[toc] | [prev] | [next] | [standalone]

#118207

On Thu, 24 Sep 2026 20:04:24 -0000 (UTC)
Thomas Koenig <tkoenig@netcologne.de> wrote:

> It seems that the different CISC and compressed instruction sets
> are ad-hoc (and not very good) attempts at compression of the
> actual instructions that machines execute.  Pure RISCS have very
> little compression, RISC-V has some, CISC has some more.  AMD's
> micro-op cache goes some way towards this when it splits
> x86_64 instructions into micro-ops.
> 
> So, the idea of using actual compression seems interesting.
> This has been tried in the past, but it didn't catch on.
> 
> There are a few basic problems to be solved.  One that comes to
> mind immediately is branch addresses.  If the instruction stream
> is compressed, any bit of the compressed stream can start an
> instruction, and calculating the target of a branch instruction
> is not straightforward.  To avoid having to decode the whole
> program, it would be necessary to create blocks of some sort,
> which could be decoded on loading into a suitable cache level.
> 
> For example, one could make the Icache into a micro-op-store
> and decode on fetching from L2.
> 
> Branch targets could then be in the form block,instruction in
> block.  There would have to be an upper limit on the number
> of instructions per block, leading to some waste for easily
> compressible instructions.  Also, instructions which no
> longer fit in a block would reduce the efficieny.
> 
> One would also have to look at PC-relative branches; these
> would probably become block-relative + instruction in block.
> 
> Writing binutils for this kind of architecture would be fun,
> in the sense of absoutely no fun at all.  Object code would
> probably be uncompressed, with the poor guy implementing the
> linker having to do all the dirty work.
> 
> The ISA to be compressed would not be limited by having to
> fit into a container determined by byte or word sizes.
> If one so desired, one could chose an ISA based on any
> bit size, although having instructions based on an n-bit
> package size (with multiples) would still make sense for
> further decoding of the micro-ops.
> 
> Other thoughts?

Last time I gave it a serious thought was more than 5 but less
than 10 years ago. Then I came to conclusion that the only  practical
way for bit-compressed instruction set is "reversed VL-VLIW".
I.e. instruction stream consists of aligned fixed-width chunks, most
likely 256 bit, but 512 bit is also possible if it turns out that 256b
is not enough for good compression. Each chunk carries variable number
of individual instructions. Details of encoding may vary, but probably
based on format header that is placed in fixed position in the chunk
that governs the rest of parsing.

Jumps into the middle of chunk are allowed, jump target is expressed as
a tuple - address-of-chunk:index-of-instruction-in-chunk. For
conditional branches address part is relative and covers limited
distance, may be -256 to + 255 chuncks, similarly to conventional
designs.

I didn't rethink it since then, but I know that I didn't become any
smarter.

[toc] | [prev] | [next] | [standalone]

#118212

> So, the idea of using actual compression seems interesting.
> This has been tried in the past, but it didn't catch on.

There are different levels at (and ways in) which compression can be
applied, with very different tradeoffs.

E.g. I remember an article years ago (maybe from ETHZ?) doing
compression on bytecode where common sequences of bytecode were turned
into something akin to "functions", IOW a kind of "common sub-expression
elimination" that's also reminiscent of LempelZiv.  The result was
compressed bytecode executable "without decompression".

You can gain some savings by playing at the bit-level to take advantage
of Hufmann-style compression, but another way to attack the problem is
to design an ISA where you can easily share common sequences of
instructions (I guess you could call it "outlining"), for example by
providing a very concise way to call and write short functions.
And maybe the micro-architecture could be taught to inline those calls
(I guess it would naturally happen if you use a trace cache).


=== Stefan

[toc] | [prev] | [next] | [standalone]

#118219

On 9/25/2026 10:46 AM, Stefan Monnier wrote:
>> So, the idea of using actual compression seems interesting.
>> This has been tried in the past, but it didn't catch on.
> 
> There are different levels at (and ways in) which compression can be
> applied, with very different tradeoffs.
> 
> E.g. I remember an article years ago (maybe from ETHZ?) doing
> compression on bytecode where common sequences of bytecode were turned
> into something akin to "functions", IOW a kind of "common sub-expression
> elimination" that's also reminiscent of LempelZiv.  The result was
> compressed bytecode executable "without decompression".
> 

BGBCC often does something similar with prologs and epilogs:
If more than a certain number of registers are saved/restored, the 
sequences are folded off and then a call/branch is used to do the actual 
bulk save/restore.

Luckily, works regardless of ISA.
Don't want to go too small though for the limit, or else it may reduce 
performance and/or make code density worse (if very small).

So, a usual cutoff is around 6 or 8 loads/stores (or 12 or 16 registers 
if one has Load/Store Pair).


This isn't really done inside functions though, and something like 
semi-efficient basic-block folding/reuse would be a much harder problem 
(even if functions have similar basic blocks, they will not necessarily 
have similar stack frames or register allocation).


LZ77 can work, but no good way to do it live.

For RAM saving though, one could do something like page-level LZ with 
dynamic decompression. So, the program is initially read into RAM in a 
compressed form, but not actually fully mapped in. When one of these 
pages is hit, the corresponding page for the image is decompressed.

I guess, in theory, I could map something like this onto my existing 
PEL4 format, by building a block-offset table. Random access decoding 
would require explicit window breaks at regular intervals though (say, 
for example, once every 8K or so).

However, an 8K window break would likely shift the "optimality" balance 
from LZ4 to RP2 (the main merit LZ4 seemingly has here is that it works 
better for distant but short matches, *; but reducing the effective 
window size would lessen this advantage).


*: RP2's design essentially assumes a positive correlation between match 
length and distance. This is true for general data, but less true for 
executable code (where all matches tend to be shorter, but have a wider 
distribution). LZ4 does better for "hey, here is 12 bytes from 60K ago" 
(which it can encode in 3 bytes, vs needing 4 in RP2; however an 8K 
sliding window means RP2 matches could operate within the 3-byte regime; 
l=4..67, d=8K).

Ironically, I also found that RP2 was less ideal for matches entirely 
within fixed-size 256 byte blocks (with a window limited to a single 
block), as again, the length and distance became negatively correlated 
(such a negative correlation was also noted in raster image compression, 
typically in the form of long matches with short distances).

The most common RLE case was partly addressed in the more recent RP2B 
variant by adding a 2-byte Len=4..131, Dist=1 case.


Debatable:
Maybe could reuse the retired "Long Match" case for a new 2-byte cases, say:
   dddlllll-rrr01111  (len=4..35, dist=1..8, raw=0..7)
Which could hit on some cases that miss with the added RP2B case:
   lllllll0-01111111  (RP2B, len=4..131, dist=1, raw=0)

And, complements the existing 2-byte match:
   dddddddd-dlllrrr0  (len=3..10, dist=0..511, raw=0..7)

Though, maybe a case could be made for 3-byte, say:
   dddddddd-llllllll-rrr01111  (l=4..259, d=1..256)

Or, errm, both:
            ddlllll0-rrr01111  (len=4..35, dist=1..4, raw=0..7)
   dddddddl-lllllll1-rrr01111  (len=4..259, d=1..128, raw=0..7)

May need to do some testing to figure out which possibility would work 
better here.


Also kind of annoying that even RP2 has fragmented:
   RP2 (Original)
   RP2A (Limits sliding window to 128K, drops Long Match)
   RP2B (Re-adds support for a 4MB sliding window via new matches)
   RP2C(?) Maybe reuse "Long Match" case as above

The original VLN based Long-Match case was dropped mostly because using 
it was detrimental to speed as well as needless pain for both ASM 
implementations and post compressors.

For RP2B, made more sense to replace it with a fixed-length 6-byte 
format (with 16K matches and a 4MB window, but no VLNs).



> You can gain some savings by playing at the bit-level to take advantage
> of Hufmann-style compression, but another way to attack the problem is
> to design an ISA where you can easily share common sequences of
> instructions (I guess you could call it "outlining"), for example by
> providing a very concise way to call and write short functions.
> And maybe the micro-architecture could be taught to inline those calls
> (I guess it would naturally happen if you use a trace cache).
> 

In an ISA, one could leverage the support in RISC-V for multiple Link 
Registers for the latter.


Say:
X1 is the main link register for function calls;
X5 is a second link register for outlined blobs and threaded-code helpers.

At a minimum, one would need a JAL+JALR of overhead, so would mean the 
"minimum break even" point (space-wise) would be around 4 instructions.
Break-even point could be reduced to 2 instructions if one had a "Branch 
here, run N instructions, then auto-return" instruction.

Would need a higher limit though if performance is a concern.


One other wacky idea could be to do something like RV-C, but instead of 
a fixed compressed ISA, have an ISA that is essentially built at compile 
time as a sort of table of patterns. The CPU then looks into this table 
and dynamically unpacks into a virtual 32-bit instruction.

Couldn't really make sense to have RVC as a preset in such as scheme, as 
ideally one wants an encoding scheme that that is more regular / less 
dog chewed.

This sort of approach would make an evil mess for things like dynamic 
linking though.

Also, would unlikely gain much as RV-C is already mostly aligned with 
the (statistically speaking) most common instructions. Well, at least if 
one assumes that the code is being generated by GCC; it is a worse fit 
for BGBCC as BGBCC tends to mostly use callee save registers for local 
variables, which greatly reduces the effectiveness of the Reg3 
instructions (and, X8/X9/X10/X11, X24/X25/X26/X27, would be a harder 
sell). Does at least work OK for leaf functions, if one assumes that 
most code is leaf functions.


There are very few instructions common enough to justify a single byte 
encoding.

The biggest gain I saw in terms of maximizing code density was with a 
16/24/32 encoding scheme.

But, even then, the 24 bit instructions weren't worth the added hassle, 
and then one either needs there to exist a 1-byte NOP or other messes 
may result.

...



Meanwhile, a Huffman-compressed instruction stream is more in "I 
wouldn't want to poke this thing with a pole".

Rice coding the instructions would be bad enough, but at least Rice 
coding would allow for a more affordable hardware decoder. Still not ideal.

> 
> === Stefan

[toc] | [prev] | [next] | [standalone]

#118222

BGB <cr88192@gmail.com> posted:

> On 9/25/2026 10:46 AM, Stefan Monnier wrote:
> >> So, the idea of using actual compression seems interesting.
> >> This has been tried in the past, but it didn't catch on.
> > 
> > There are different levels at (and ways in) which compression can be
> > applied, with very different tradeoffs.
> > 
> > E.g. I remember an article years ago (maybe from ETHZ?) doing
> > compression on bytecode where common sequences of bytecode were turned
> > into something akin to "functions", IOW a kind of "common sub-expression
> > elimination" that's also reminiscent of LempelZiv.  The result was
> > compressed bytecode executable "without decompression".
> > 
> 
> BGBCC often does something similar with prologs and epilogs:
> If more than a certain number of registers are saved/restored, the 
> sequences are folded off and then a call/branch is used to do the actual 
> bulk save/restore.
> 
> Luckily, works regardless of ISA.
> Don't want to go too small though for the limit, or else it may reduce 
> performance and/or make code density worse (if very small).
> 
> So, a usual cutoff is around 6 or 8 loads/stores (or 12 or 16 registers 
> if one has Load/Store Pair).

How does the hardware recognize that this sequence of STs (prologue)
or LDs (epilogue) are using a dense set of addresses so that one only
needs to access the tag once (or twice) instead of (12-16) times?

How does the hardware recognize that this sequence stays all within
one page and thus one TLB hit suffices for 12-16 memory references ??

And if performed with Call/Return semantics, how do non-memory instructions
get through the Decoder and into Reservation Stations--while those strings
of memory references get performed ??

Instead, if one uses ENTER/EXIT, one address calculation satisfies many
accesses, one TLB lookup satisfies all those accesses, and the cache tag
is only accesses once (or twice). 

You also get the ability to scoreboard all the registers being written,
scoreboard all the registers being read, read the return address before
reading the preserved registers, and begin fetch before all the loads
have been performed.

And, ENTER is only 1 32-bit instruction without any flow control while
EXIT is 1 32-bit instruction with flow control faster than data access.
 

[toc] | [prev] | [next] | [standalone]

#118225

On 9/25/2026 5:59 PM, MitchAlsup wrote:
> 
> BGB <cr88192@gmail.com> posted:
> 
>> On 9/25/2026 10:46 AM, Stefan Monnier wrote:
>>>> So, the idea of using actual compression seems interesting.
>>>> This has been tried in the past, but it didn't catch on.
>>>
>>> There are different levels at (and ways in) which compression can be
>>> applied, with very different tradeoffs.
>>>
>>> E.g. I remember an article years ago (maybe from ETHZ?) doing
>>> compression on bytecode where common sequences of bytecode were turned
>>> into something akin to "functions", IOW a kind of "common sub-expression
>>> elimination" that's also reminiscent of LempelZiv.  The result was
>>> compressed bytecode executable "without decompression".
>>>
>>
>> BGBCC often does something similar with prologs and epilogs:
>> If more than a certain number of registers are saved/restored, the
>> sequences are folded off and then a call/branch is used to do the actual
>> bulk save/restore.
>>
>> Luckily, works regardless of ISA.
>> Don't want to go too small though for the limit, or else it may reduce
>> performance and/or make code density worse (if very small).
>>
>> So, a usual cutoff is around 6 or 8 loads/stores (or 12 or 16 registers
>> if one has Load/Store Pair).
> 
> How does the hardware recognize that this sequence of STs (prologue)
> or LDs (epilogue) are using a dense set of addresses so that one only
> needs to access the tag once (or twice) instead of (12-16) times?
> 

Load/Store Pair gets it down to 6/8 ...

I guess in theory a CPU could recognize that pairs of LDP/SDP 
instructions are, say, actually LDQ/SDQ operations. Though, this would 
mean a 256 bit memory port, and needing to move 4 registers at a time. 
This wouldn't really work with a 4R2W or 6R3W register file with 64-bit 
ports though.

Well, or add special instructions, assuming the CPU has the register 
ports to make it happen.


Could in theory work if one did a register file as 4R2W 128-bit (then 
with some trickery to support 64-bit operations). I once looked into 
this, but noted that a 4R2W regfile operating 2-wide with 128-bit ports 
(but faking 64-bit operations at the register-port level) would give 
worse performance on-average than a 6R3W regfile with 64-bit ports for 
64-bit operations (would mostly make sense if the goal was more 
specifically to try to build a SIMD monster with a 256 bits/cycle 
throughput or similar).

Ironically, wouldn't really need to change the ISA for this, though it 
would have effects on the compiler's instruction shuffling/scheduling 
heuristics.


> How does the hardware recognize that this sequence stays all within
> one page and thus one TLB hit suffices for 12-16 memory references ??
> 

Dunno. Likely the absence of TLB misses would imply a hits by extension.


> And if performed with Call/Return semantics, how do non-memory instructions
> get through the Decoder and into Reservation Stations--while those strings
> of memory references get performed ??
> 

FWIW, with an in-order pipeline, I explicitly don't allow anything to 
co-execute with branch style instructions. With OoO, dunno. Probably 
need some way to create a barrier to separate between the pre-branch and 
post-branch parts of the pipeline so that if a branch mispredict happens 
one isn't "up a creek".


> Instead, if one uses ENTER/EXIT, one address calculation satisfies many
> accesses, one TLB lookup satisfies all those accesses, and the cache tag
> is only accesses once (or twice).
> 

You do however, need a mechanism to orchestrate these sub-tasks, vs just 
using a naive instruction sequence.

Can also note that ARM32 had LDM/STM, but ARM64 explicitly dropped to 
Load/Store Pair.

Went and checked before, seemingly Load/Store Pair is safe, as the way 
it works in XG2 and XG3 is effectively covered by prior art established 
by SPARC.


Then again, can also note that seemingly most of the ARM64 cores are 2 
or 3 wide, so would likely face the same issue as above.

Seemingly, going 4-wide (or wider) mostly being a thing in PC/server 
class processors.


> You also get the ability to scoreboard all the registers being written,
> scoreboard all the registers being read, read the return address before
> reading the preserved registers, and begin fetch before all the loads
> have been performed.
> 
> And, ENTER is only 1 32-bit instruction without any flow control while
> EXIT is 1 32-bit instruction with flow control faster than data access.
>   

Using a call or branch for a reused Load/Store blob, while not free, 
does at leas not ask anything special from the CPU...

Like, the compiler then is the only one that needs to care (and the CPU 
can remain dumb).

...


Then again, thinking about it more, would maybe be interesting if there 
were some way to (somehow) cram an instruction-level LZ decompressor 
into the I$.

Hard thing would be trying to figure out some way to make it play well 
with interrupts (and would need to somehow deal with potentially 
multiple independent locations per-cycle).

...

[toc] | [prev] | [next] | [standalone]

#118294

BGB <cr88192@gmail.com> writes:
>On 9/25/2026 5:59 PM, MitchAlsup wrote:
>> 
>> BGB <cr88192@gmail.com> posted:

>> How does the hardware recognize that this sequence of STs (prologue)
>> or LDs (epilogue) are using a dense set of addresses so that one only
>> needs to access the tag once (or twice) instead of (12-16) times?
>> 
>
>Load/Store Pair gets it down to 6/8 ...
>
>I guess in theory a CPU could recognize that pairs of LDP/SDP 
>instructions are, say, actually LDQ/SDQ operations.

It's not theory.  Many of the ARM server-grade CPUs in the last decade have
supported converting LDP/SDP into a single twice as wide potentially
*atomic* memory operation.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.arch

csiph-web