[Libre-soc-dev] v3.1B prefix

[Alexandre Oliva]

On Dec 14, 2020, Luke Kenneth Casson Leighton <lkcl at lkcl.net> wrote:

> although i just realised that the 4 reg versions need to be on the
> best 4 *relevant* regs not the global top 4 regs.

Register mapping is something that generic algorithms could help us
with, actually.  We don't have to use the same mapping for all
instructions.  We have to use that which makes for most longest
compressed sequences.

Now, modeling the compressed ISA and the relevant transformations for
evolution and selection isn't something I immediately see how to do.
Considering the amount of time it took me to implement the encodings for
the compressor, and to understand some of the clever decisions that went
into it, I can't quite picture how to go beyond the most trivial 'how
many bits does it take to encode the operands for this one opcode', and
packing as many opcodes as possible so as to use up the available
representation bits.

Alas, that doesn't build any such cleverness as compressing 3 register
operands into 2 by requiring matching input and output, using fewer bits
for certain operands due to mapping or giving up flexibility, excluding
register 0 from one opcode and using it to encode an alternate opcode...  

OTOH, we could just go completely wild and have every single insn, all
operands considered, be regarded as eligible independently.  That would
make for quite an interesting evolution model, but it might take quite a
long time to evolve a useful compressed isa, and it might not make for
very efficient remapping, hardware-wise.

Another aspect that would have to be taken into account would be the
underlying mode-switching model.  E.g., the currently implemented models
carry assumptions about costs of mode switching, and circumstances in
which it may or may not occur: 10-bit insns to enter compressed mode or
not, and 2 bits out of 16-bit insns to leave it or not, temporarily or
not, or to encode insns that don't leave it.  Various other
possibilities are available, and exploring that design space might
require a lot of thought in designing generic cross-over operations to
enable combined solutions that make sense.


Now, I'm a little confused.  Not long after I joined, I got the notion
that the time for such wild exploration was long past, and that we had
pretty much settled on a design that we've now abandoned.  We have a
major deliverable this month.  And yet we seem to be starting a fresh
exploration of the design space.  This is not a complaint, I just feel
I'm confused about where this exploration fits in.

> what's the statistics on the number of consecutive Compressed opportunities?

I can't say I have any statistics or significant analysis, I only got as
far as writing the script and dumping the (test) data it gathered from a
single unrepresentative program.

> what if we said that there were 4 bits per reg (16 possibles), and
> that the transition to 16bit was a "countdown" of up to 8 ops?

> or, because there are 10 bits available, how about 3 3 3 so:

> * up to 8 16bit ops
> * up to 8 32bit ops
> * up to 8 16bit then finally drop out

> the 2 bits currently taken with N and M can be assumed to be allocated
> to increasing 3bit reg#s to 4 bit for now.

> yes it is not perfect, some ops are src1 src2 dest, they can't all be 4 bit

I assume you'd like me to prepare a modified version of the compression
estimator to implement this model?

The count-down logic will take a very different main loop state machine,
and this would do away with 16-imm altogether, which would significantly
reduce the possibilities of encoding compressed insns.

Furthermore, I don't think this 3+3+3 encoding will make for very
efficient compressed encoding.  If we were to get up to 50% compressed
insns (which this won't do), alternating between compressed and
traditional insns, that would be the least efficient use of those bits,
encoding 0b001 in each of the 3-bit fields.

A much denser representation would be achieved by using one bit per
upcoming insn, to tell whether or not it's compressed, as I suggested
elsewhere: https://bugs.libre-soc.org/show_bug.cgi?id=238#c113 starting
at "consider, for inspiration"

-- 
Alexandre Oliva, happy hacker  https://FSFLA.org/blogs/lxo/
   Free Software Activist         GNU Toolchain Engineer
        Vim, Vi, Voltei pro Emacs -- GNUlius Caesar