I keep changing the basic design of Concertina II, instead of going
forward and completing the task of fleshing it out.

The reason for that... has been obvious all along. None of my attempts
have satisfied me. I had goals for the architecture, some of which
weren't being met by each iteration. So I kept going back and forth
between compromising one set of goals, or compromising another set of
goals.

If I could make up my mind on what was most important to me, perhaps I
could stop somewhere.

Looking back at the various iterations, I did see that two goals were
very important to me.

I wanted to be able to have 16-bit instructions, at least in pairs
within a 32-bit instruction slot, available without the overhead of a
block header, in the basic instruction set. For this, I need to
reserve 1/4 of the opcode space.

Also, I wanted to have the basic load-store memory-reference
instructions be able to use 16-bit displacements, have a three-bit
index register field and a three-bit base register field, and be able
to use all 32 registers in a normal register bank as destinations.
This takes 3/4 of the opcode space.

As 3/4 plus 1/4 is _not_ greater than 1, having both of these things
in a design simultaneously is not impossible.

And I've found some tiny scraps of opcode space left (in the 3/4 part;
flexible auto-increment with an odd index register, since only even
index registers are allowed in that mode) which are barely enough...

for two-address register to register operate instructions, _and_ for a
block header.

The block header, while rudimentary, would be enough to allow...

indicating some instruction slots as containing instructions from a
secondary instruction set, so as to allow things like three-address
operate instructions, multiple-register load and store instructions,

and also allowing pseudo-immediates...

and instructions longer than 32 bits.

I have two unused opcodes in the load/store memory reference
instructions, so I can use one of them for jump to subroutine (offset
in the index register field, return address register in the
destination register field) - and one for conditional jump. Since the
condition code can go in the destinatin register field, and it only
needs four bits, not five... I can also have a Load Address
instruction, with the limitation that only registers 0-7 and 24-31 can
be used as destinations (the ones used as index registers and the
usual base registers).

However, requiring the block header mechanism even for load and store
multiple registers, basic to subroutine calls, means that the basic
instruction set is... only _barely_ a complete one.

So this is unlikely to satisfy me for very long either.

One other possibility: stick with the current design - 1/4 of the
opcode space for 16-bit instructions and 1/4 of the opcode space for
instructions longer than 32 bits, so as to reduce their overhead and
possibly allow the mechanism to also be used for prefixing
instructions (not needed, though, if I decide to return to having
block headers in a less vestigial form)...

I would have to squeeze the "rest" of the instruction set a bit more
if I switched from aligned-only load and store instructions to going
to using only four base registers for them (the least painful of the
restrictions I've considered so far), but it should be doable.

John Savard

John Savard wrote:

> I keep changing the basic design of Concertina II, instead of going
> forward and completing the task of fleshing it out.

> The reason for that... has been obvious all along. None of my attempts
> have satisfied me. I had goals for the architecture, some of which
> weren't being met by each iteration. So I kept going back and forth
> between compromising one set of goals, or compromising another set of
> goals.

> If I could make up my mind on what was most important to me, perhaps I
> could stop somewhere.

> Looking back at the various iterations, I did see that two goals were
> very important to me.

> I wanted to be able to have 16-bit instructions, at least in pairs
> within a 32-bit instruction slot, available without the overhead of a
> block header, in the basic instruction set. For this, I need to
> reserve 1/4 of the opcode space.

> Also, I wanted to have the basic load-store memory-reference
> instructions be able to use 16-bit displacements, have a three-bit
> index register field and a three-bit base register field, and be able
> to use all 32 registers in a normal register bank as destinations.
> This takes 3/4 of the opcode space.

> As 3/4 plus 1/4 is _not_ greater than 1, having both of these things
> in a design simultaneously is not impossible.

Not impossible, sure: but reserving so much for so little is gonna hurt.

> And I've found some tiny scraps of opcode space left (in the 3/4 part;
> flexible auto-increment with an odd index register, since only even
> index registers are allowed in that mode) which are barely enough...

In my opinion, your first cut at an ISA encoding should not consume more
than ½ of the available encodings. Concer-tina-tanic is already full to
the brim and you are still just fleshing it out.

> for two-address register to register operate instructions, _and_ for a
> block header.

> The block header, while rudimentary, would be enough to allow...

> indicating some instruction slots as containing instructions from a
> secondary instruction set, so as to allow things like three-address
> operate instructions, multiple-register load and store instructions,

> and also allowing pseudo-immediates...

> and instructions longer than 32 bits.

> I have two unused opcodes in the load/store memory reference
> instructions, so I can use one of them for jump to subroutine (offset
> in the index register field, return address register in the
> destination register field) - and one for conditional jump. Since the
> condition code can go in the destinatin register field, and it only
> needs four bits, not five... I can also have a Load Address
> instruction, with the limitation that only registers 0-7 and 24-31 can
> be used as destinations (the ones used as index registers and the
> usual base registers).

> However, requiring the block header mechanism even for load and store
> multiple registers, basic to subroutine calls, means that the basic
> instruction set is... only _barely_ a complete one.

> So this is unlikely to satisfy me for very long either.

Sigh....

> One other possibility: stick with the current design - 1/4 of the
> opcode space for 16-bit instructions and 1/4 of the opcode space for
> instructions longer than 32 bits, so as to reduce their overhead and
> possibly allow the mechanism to also be used for prefixing
> instructions (not needed, though, if I decide to return to having
> block headers in a less vestigial form)...

> I would have to squeeze the "rest" of the instruction set a bit more
> if I switched from aligned-only load and store instructions to going
> to using only four base registers for them (the least painful of the
> restrictions I've considered so far), but it should be doable.

> John Savard

On Thu, 25 Apr 2024 16:00:14 +0000, mitchalsup@aol.com (MitchAlsup1)
wrote:

>In my opinion, your first cut at an ISA encoding should not consume more
>than ½ of the available encodings. Concer-tina-tanic is already full to
>the brim and you are still just fleshing it out.

Basically, I think that the reasonable length that a computer
instruction should occupy is that which a similar instruction occupied
on the IBM System/360 - which, in its day, was not regarded highly for
its code density.

However, I have banks of 32 registers instead of 16, and 16-bit
displacements instead of 12 bits. Having only load and store
memory-reference instructions, of course, helps to make up for this.

That's why I can only use 8 of the 32 registers as base registers and
as index registers, too.

For wanting the impossible, of course I basically deserve what I get.
If I _could_ manaage to pull it off, of course, the result would be of
some practical use; an instruction set that's plain, clear, and simple
(at least when compared to monstrosities like Itanium and x86) and
which is parsimonious in its use of memory is of some value.

While I'm rearranging the deck chairs, maybe I'll come up with an
original idea.

John Savard

On 4/25/2024 11:00 AM, MitchAlsup1 wrote:
> John Savard wrote:
>
>> I keep changing the basic design of Concertina II, instead of going
>> forward and completing the task of fleshing it out.
>
>> The reason for that... has been obvious all along. None of my attempts
>> have satisfied me. I had goals for the architecture, some of which
>> weren't being met by each iteration. So I kept going back and forth
>> between compromising one set of goals, or compromising another set of
>> goals.
>
>> If I could make up my mind on what was most important to me, perhaps I
>> could stop somewhere.
>
>> Looking back at the various iterations, I did see that two goals were
>> very important to me.
>
>> I wanted to be able to have 16-bit instructions, at least in pairs
>> within a 32-bit instruction slot, available without the overhead of a
>> block header, in the basic instruction set. For this, I need to
>> reserve 1/4 of the opcode space.
>
>> Also, I wanted to have the basic load-store memory-reference
>> instructions be able to use 16-bit displacements, have a three-bit
>> index register field and a three-bit base register field, and be able
>> to use all 32 registers in a normal register bank as destinations.
>> This takes 3/4 of the opcode space.
>
>> As 3/4 plus 1/4 is _not_ greater than 1, having both of these things
>> in a design simultaneously is not impossible.
>
> Not impossible, sure: but reserving so much for so little is gonna hurt.
>
>> And I've found some tiny scraps of opcode space left (in the 3/4 part;
>> flexible auto-increment with an odd index register, since only even
>> index registers are allowed in that mode) which are barely enough...
>
> In my opinion, your first cut at an ISA encoding should not consume more
> than ½ of the available encodings. Concer-tina-tanic is already full to
> the brim and you are still just fleshing it out.
>

Yeah, this has also been a problem with most of my attempts to design a
fully orthogonal encoding with 16 ans 32 bit instructions, predication +
bundling, and 64 GPRs.

Encoding space quickly runs out (often well before I get to the
feature-set of my current ISA design), so at least one of these needs to
be cut.

But, even then, hard to come up with much "obviously better" than what I
have already. Like, maybe I could have less dog chew in the register and
immediate fields, but ...

And, there is seemingly no way to fit all the features of both Baseline
and XG2 into a 32-bit instruction word. And, in this case, it is a
tradeoff between better code density (Baseline) and higher performance
(XG2).

But, was at least able to twiddle the compiler enough that at least XG2
is "mostly not losing" in terms of code-density if compared with RV64G.

Have also seemingly made some gains in terms of Software Quake
performance, as it is now (mostly) able to run in the upper single
digits at 50MHz (~ 6-8 fps), except for the cases where it is still
stuck at 3 or 4.

TBD what might happen if I tried reverting to the original 8bpp SW
renderer, rather than the modified 16-bpp hi-color version I am using.

>> for two-address register to register operate instructions, _and_ for a
>> block header.
>
>> The block header, while rudimentary, would be enough to allow...
>
>> indicating some instruction slots as containing instructions from a
>> secondary instruction set, so as to allow things like three-address
>> operate instructions, multiple-register load and store instructions,
>
>> and also allowing pseudo-immediates...
>
>> and instructions longer than 32 bits.
>
>> I have two unused opcodes in the load/store memory reference
>> instructions, so I can use one of them for jump to subroutine (offset
>> in the index register field, return address register in the
>> destination register field) - and one for conditional jump. Since the
>> condition code can go in the destinatin register field, and it only
>> needs four bits, not five... I can also have a Load Address
>> instruction, with the limitation that only registers 0-7 and 24-31 can
>> be used as destinations (the ones used as index registers and the
>> usual base registers).
>
>> However, requiring the block header mechanism even for load and store
>> multiple registers, basic to subroutine calls, means that the basic
>> instruction set is... only _barely_ a complete one.
>
>> So this is unlikely to satisfy me for very long either.
>
> Sigh....
>
>> One other possibility: stick with the current design - 1/4 of the
>> opcode space for 16-bit instructions and 1/4 of the opcode space for
>> instructions longer than 32 bits, so as to reduce their overhead and
>> possibly allow the mechanism to also be used for prefixing
>> instructions (not needed, though, if I decide to return to having
>> block headers in a less vestigial form)...
>
>> I would have to squeeze the "rest" of the instruction set a bit more
>> if I switched from aligned-only load and store instructions to going
>> to using only four base registers for them (the least painful of the
>> restrictions I've considered so far), but it should be doable.
>
>> John Savard

On Thu, 25 Apr 2024 12:41:23 -0600, John Savard
<quadibloc@servername.invalid> wrote:

>While I'm rearranging the deck chairs, maybe I'll come up with an
>original idea.

This latest proposal, which does differ from my previous attempts,
does have _one_ advantage.

In this case, as in the previous attempts, I will need to use the
block header to indicate that some 32-bit instruction slots contain
32-bit instructions in an "alternate" format.

When the memory-reference instructions in the main format were
compromised, that alternate format included uncompromised
memory-reference instructions. So the extended instruction set,
normal plus alternate, included the normal instructions twice.

Here, I avoid that. Of course, though, the main format includes a
severely compromised version of the register-to-register operate
instructions. The alternate format would include the full version of
those.

Same thing, right?

Well, not really - because the compromised version of
register-to-register operate instructions contains only *one*
instruction format. So there _is_ less duplication and waste, the
instruction decode unit isn't set up to decode both the full version
of the operate instructions and a second compromised format which is
equally complex, but just has one bit trimmed off everywhere.

John Savard

On Wed, 24 Apr 2024 23:49:25 -0600, John Savard
<quadibloc@servername.invalid> wrote:

>So this is unlikely to satisfy me for very long either.

And, given that, I've thought long and hard about what really is
needed.

The main opcode space for 32-bit instructions is now divided as
follows:

3/4 for uncompromised memory-reference instructions.

3/16 for uncompromised register-to-register operate instructions.

1/16 for the header required for variable-length instructions.

The variable-length instructions will allow, with 32 bits of overhead
per block, arbitrary mixing of 17-bit short instructions (the extra
bit goes into the two-bit prefix field in the header) and 32-bit
instructions - and longer instructions.

00 and 01 indicate 17-bit instructions starting with 0 and 1
respectively.

10 indicates a 16-bit extent that contains the start of an instruction
32 bits long or longer.

11 indicates a 16-bit extent that is not the start of an instruction.
In addition to the remaining parts of an instruction, space reserved
for pseudo-immediates can be indicated by this.

There will be three forms of header.

One just has a three-bit field indicating the number of 32-bit
instruction slots reserved for pseudo-immediates, in a restricted
register-to-register operate instruction squeezed into an odd bit of
leftover opcode space.

The other will provide VLIW functionality for code consisting only of
32-bit instructions: predication, and explicit indication of
parallelism.

The final one is 1111 that allows 17-bit instructions, 48, 64, 80, and
96 bit instructions, and their arbitrary mixing.

This has the advantage of providing all the functionality I'm looking
for - a large, extensible instruction set, compactness of code through
16-bit instructions that don't restict which registers can be used,
and memory-reference instructions that make full use of a 32-bit
length being the only version of those instructions, instead of having
to include both a cut-down form and a full-form, the latter only
accessible with a header.

Finally, this seems to be something that I will be forced to admit
that further restructurings won't be able to improve upon - this will
be the best way to squeeze everything I want into the 8-bit byte and
the 32-bit word.

John Savard

On Sun, 05 May 2024 00:57:44 -0600, John Savard
<quadibloc@servername.invalid> wrote:

>The final one is 1111 that allows 17-bit instructions, 48, 64, 80, and
>96 bit instructions, and their arbitrary mixing.

However, one thing I wanted to do was have the 48-bit and longer
instructions also available outside of the variable-length format.

Previously, I had done this by having a second format of long
instructions. I wanted to avoid that, this time.

I came up with an idea. Just as 1111 _after_ the header in
variable-length mode was used to indicate long instructions, for other
modes, let 1111 after the header indicate each of two instruction
slots in which three 18-bit units from variable-length are
encapsulated. So a 48-bit instruction, taking up 64 bits, could be
placed in any of the other modes.

But because that code conflicts with the header, these things aren't
first-class citizens! I tried freeing up 1110 as well, but that was
clearly not going to work acceptably. So I took other measures that
only partly addressed that issue but consumed far less opcode space.

John Savard

On Sun, 05 May 2024 00:57:44 -0600, John Savard
<quadibloc@servername.invalid> wrote:

>The main opcode space for 32-bit instructions is now divided as
>follows:
>
>3/4 for uncompromised memory-reference instructions.
>
>3/16 for uncompromised register-to-register operate instructions.
>
>1/16 for the header required for variable-length instructions.

This is not quite right.

3/4 for uncompromised basic memory-reference instructions.

1/8 for other memory-reference instructions.

1/16 for uncompromised register-to-register operate instructions.

1/16 for the header required for variable-length instructions.

John Savard

John Savard wrote:

> On Sun, 05 May 2024 00:57:44 -0600, John Savard
> <quadibloc@servername.invalid> wrote:

>>The main opcode space for 32-bit instructions is now divided as
>>follows:
>>
>>3/4 for uncompromised memory-reference instructions.
>>
>>3/16 for uncompromised register-to-register operate instructions.
>>
>>1/16 for the header required for variable-length instructions.

> This is not quite right.

> 3/4 for uncompromised basic memory-reference instructions.

> 1/8 for other memory-reference instructions.

> 1/16 for uncompromised register-to-register operate instructions.

> 1/16 for the header required for variable-length instructions.

In comparison::

1/8 for [Rbase+@disp16]
1/8 for Rd = Rs1 OP imm16
1/64 for [Rbase,Ri<<scale,#disp]
1/64 for Rd = Rs1 OP Rs2
1/64 for Rd = 3OP( Rs1,Rs2,Rs3)
1/64 for Rd = 1OP( Rs1 )
1/64 for PRED
1/64 for <w:o>
1/8 for branching

> John Savard

On Mon, 06 May 2024 11:06:44 -0600, John Savard
<quadibloc@servername.invalid> wrote:

>But because that code conflicts with the header, these things aren't
>first-class citizens! I tried freeing up 1110 as well, but that was
>clearly not going to work acceptably. So I took other measures that
>only partly addressed that issue but consumed far less opcode space.

Although I had limited long vector and short vector operate
instructions in the basic 32 bit instruction set, I didn't have long
vector and short vector load and store instructions of any kind. Do I
needed to add them in some form in order for the basic 32 bit
instruction set to be complete.

However, if I were to include a 6-bit length field in the long vector
load and store instructions, once again I would have had to free up
1/16 of the opcode space. Instead of completely doing without the
ability to load and store any but full-length vectors, I eventually
was able to include a two-bit length register field to the long vector
load and store instructions.

So this new instruction set has survived another challenge.

John Savard