[Libre-soc-dev] efficient decoding algorithm for variable-length instructions

[Luke Kenneth Casson Leighton]

On Wed, Nov 25, 2020 at 8:17 PM Jacob Lifshay <programmerjake at gmail.com> wrote:
>
> On Wed, Nov 25, 2020, 04:53 Luke Kenneth Casson Leighton <lkcl at lkcl.net>
> wrote:
>
> > On Wed, Nov 25, 2020 at 6:06 AM Jacob Lifshay <programmerjake at gmail.com>
> > wrote:
> > >
> > > I wrote out the following decoding algorithm for variable-length
> > instructions:
> > > https://libre-soc.org/openpower/sv/16_bit_compressed/decoding/
> > >
> > > It uses the 16/32/48/64-bit encoding that I proposed in earlier
> > > emails. It has a circuit depth of O(log N) for a decoder that can
> > > decode N instructions per cycle.
> >
> > excellent.
> >
> > just to check: https://libre-soc.org/openpower/sv/16_bit_compressed/
> >
> >     "Demo of encoding that's backward-compatible with PowerISA v3.1 in
> > both LE and BE mode"
> >
> > i believe we determined yesterday that this is not true?  that 16/48
> > (as i intuited/suspected" prevents and prohibits inter-mingling of
> > v3.0B, v3.1B and 16/48-bit prefixed instructions without additional
> > state (such as a VLE-like 64k page marker bit)?
> >
>
> You misunderstood me, the additional state is tracked as-if it is an
> extension of PC, read and written by every instruction. That state does
> *not* come from the page tables. If the state is set to Standard Mode (the
> state required at ABI boundaries), then all 32/48/64-bit instructions leave
> it set in Standard Mode and it is completely backward-compatible with
> PowerISA v3.1.

yep, i got it, through a walk-through with bits of paper and large
coloured pens :)
https://youtu.be/LdAIOew63Bs  (still processing, will be ready in 20+
mins or so)

the only thing that's slightly weird is the SV-P48 encoding (and
SV-C48 which is the 27-bit SV prefix plus a 16-bit instruction).
these i noted in the video have to be encoded as:

* when PC mod 4 == 0
   - bytes 2-3 must contain the Major EXTNNN
   - bytes 0-1 can be whatever-we-choose-the-order-to-be
   - bytes 4-5 can be whatever-we-choose-them-to-to

* when PC mod 4 == 2
   - bytes 0-1 must contain the Major EXTNNN
   - bytes 2-5 can be whatever-we-choose-them-to-be

in other words if there was a 16-bit instruction in bytes 2-3 of
memory, then the SV-P48 instruction has to be encoded such that EXTNNN
shows up in byte column 1 (1st halfword)

but if we are on word-aligned boundaries, the EXTNNN has to show up in
bytes *2 to 3*.

this is... spectacularly weird.

l.