....is difficult to see.
But one goal that has been a constant is high code density.
Even though the IBM System/360 was not considered to have been a
system with particularly dense code, my goal of not having code
density that is any _worse_ than it had, while adding extra features,
has led to... exertions.

So, in my original Concertina design, I took the 32-bit memory-reference
format of System/360, which was

opcode: 8 bits
destination register: 4 bits
index register: 4 bits
base register: 4 bits
displacement: 12 bits

and, in order to increase the displacement to 16 bits, as found in many
microprocessors today, I went to

opcode: 7 bits
destination register: 3 bits
index register: 3 bits
base register: 3 bits
displacement: 16 bits

which was reasonable enough; a similar instruction format is used
in the Cray I.

To change to a RISC-like architecture - but retaining base-index
addressing - I wanted to increase the destination register field to 5 bits.

This can be done, as a 5 bit opcode is enough for load and store
instructions. However, that means the load and store instructions use
up almost 3/4 of the available opcode space. I wanted to carve out 1/4
of the opcode space to allow me to put pairs of 16-bit instructions in
the 32-bit instruction words.

At this point, what I have been doing is shrinking the load and store
instructions considerablty by restricting them to aligned operands - and
using what would be the unused displacement bits to indicate the
operand type.

But recently I was toying with a way to avoid this restriction... and here is
the monstrosity I came up with.

Unindexed instruction:

1 (to indicate memory-reference instruction)
opcode: 5 bits
destination register: 5 bits
00 (to indicate unindexed instruction)
base register: 3 bits
displacement: 16 bits

Indexed instruction:

1 (to indicate memory-reference instruction)
opcode: 5 bits
destination register: 4 bits
index register: 3 bits
base register: 3 bits
displacement: 16 bits

So the base register would be, perhaps, one of
registers 25 through 31.

The available index registers would be registers
1, 2, 3, 5, 6, and 7. Neither register 0 nor register 4
would be available for use as an index register.

And only even-numbered registers could be used with
indexed loads and stores!

There are historical computer designs with even weirder
and less orthogonal restrictions, but coming up with wild
ideas like this does seem to indicate I'm going in the wrong
direction...

John Savard

On Tuesday, July 5, 2022 at 6:25:46 PM UTC-5, Quadibloc wrote:
> ...is difficult to see.
> But one goal that has been a constant is high code density.
> Even though the IBM System/360 was not considered to have been a
> system with particularly dense code, my goal of not having code
> density that is any _worse_ than it had, while adding extra features,
> has led to... exertions.
>
> So, in my original Concertina design, I took the 32-bit memory-reference
> format of System/360, which was
>
> opcode: 8 bits
> destination register: 4 bits
> index register: 4 bits
> base register: 4 bits
> displacement: 12 bits
>
> and, in order to increase the displacement to 16 bits, as found in many
> microprocessors today, I went to
>
> opcode: 7 bits
> destination register: 3 bits
> index register: 3 bits
> base register: 3 bits
> displacement: 16 bits
>
> which was reasonable enough; a similar instruction format is used
> in the Cray I.
>
> To change to a RISC-like architecture - but retaining base-index
> addressing - I wanted to increase the destination register field to 5 bits.
<
S.E.L. used lower order bits in the displacement to indicate size (in
an otherwise 360-like ISA). So there were 2 instructions with Byte
(LD and ST) and 2 instructions with Sized (also LD and ST).
Displacement<1:0>::
00: right Halfword
01: left Halfword
10: Word
11: DoubleWord
This modification SHOULD take the OpCode space penalty out of
the 16-bit Displacement.
>
> This can be done, as a 5 bit opcode is enough for load and store
> instructions. However, that means the load and store instructions use
> up almost 3/4 of the available opcode space. I wanted to carve out 1/4
> of the opcode space to allow me to put pairs of 16-bit instructions in
> the 32-bit instruction words.
<
My 66000 has 6-bit Major OpCode, and 16-bit Displacements in the
Major OpCode without index register, and in XOP1 are memrefs with
indexing with no displacement, 32-bit displacements, and 64-bit
displacements. Thus taking only ¼ of the Major OpCode space, and
another ½ of the XOP1 OpCode area.
{Each XOxx subgroup takes 1 Major OpCode and provides an entire
space of sub instructions}.
>
> At this point, what I have been doing is shrinking the load and store
> instructions considerablty by restricting them to aligned operands - and
> using what would be the unused displacement bits to indicate the
> operand type.
<
as above.....
>
> But recently I was toying with a way to avoid this restriction... and here is
> the monstrosity I came up with.
>
> Unindexed instruction:
>
> 1 (to indicate memory-reference instruction)
> opcode: 5 bits
> destination register: 5 bits
> 00 (to indicate unindexed instruction)
> base register: 3 bits
> displacement: 16 bits
>
> Indexed instruction:
>
> 1 (to indicate memory-reference instruction)
> opcode: 5 bits
> destination register: 4 bits
> index register: 3 bits
> base register: 3 bits
> displacement: 16 bits
>
> So the base register would be, perhaps, one of
> registers 25 through 31.
<
Note: S.E.L. machines could only base with Registers[0,1,2,3]
>
> The available index registers would be registers
> 1, 2, 3, 5, 6, and 7. Neither register 0 nor register 4
> would be available for use as an index register.
>
> And only even-numbered registers could be used with
> indexed loads and stores!
>
> There are historical computer designs with even weirder
> and less orthogonal restrictions, but coming up with wild
> ideas like this does seem to indicate I'm going in the wrong
> direction...
<
Warning Will Robinson: you have take the wrong turn a few days
back.....
>
> John Savard

Quadibloc wrote:

> ...is difficult to see.
> But one goal that has been a constant is high code density.
> Even though the IBM System/360 was not considered to have been a
> system with particularly dense code, my goal of not having code
> density that is any worse than it had, while adding extra features,
> has led to... exertions.
>
> So, in my original Concertina design, I took the 32-bit
> memory-reference format of System/360, which was
>
> opcode: 8 bits
> destination register: 4 bits
> index register: 4 bits
> base register: 4 bits
> displacement: 12 bits
>
> and, in order to increase the displacement to 16 bits, as found in
> many microprocessors today, I went to
>
> opcode: 7 bits
> destination register: 3 bits
> index register: 3 bits
> base register: 3 bits
> displacement: 16 bits
>
> which was reasonable enough; a similar instruction format is used
> in the Cray I.
>
> To change to a RISC-like architecture - but retaining base-index
> addressing - I wanted to increase the destination register field to 5
> bits.

Why do you want to keep the base register. It was, IMO a bad idea from
the start. In order to keep it, you are reducing the number of
registers to 8, which will hurt a lot. Just dump it and use those four
instruction bits to get a 16 bit displacement from the start.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

On Tuesday, July 5, 2022 at 5:57:11 PM UTC-6, Stephen Fuld wrote:

> Why do you want to keep the base register. It was, IMO a bad idea from
> the start. In order to keep it, you are reducing the number of
> registers to 8, which will hurt a lot. Just dump it and use those four
> instruction bits to get a 16 bit displacement from the start.

What good is a 16-bit displacement without a base register? Unless
you have only 64K of memory.

First, you have to arrange a way to access locations everywhere in the
entire address space. Then you can add indexing. The S/360 had nice
simple orthogonal base registers - whereas x86 has a complicated
segment register scheme. Before the S/360, one had schemes that are
currently not considered good: a zero page/current page bit, and/or
indirect addressing.

Is there some other way of addressing more than 64K without a huge
displacement that other modern architectures are using that I've missed?

Also, instead of reducing the number of registers to 8, as I did in the
original Concertina, I'm going with 32 registers - but only the first 8
may be index registers and the last 8 may be base registers. So I don't
limit the architecture to 8 registers, although 32 are no longer enough
to do away with the need for out-of-order execution.

John Savard

On Tuesday, July 5, 2022 at 11:07:47 PM UTC-6, Quadibloc wrote:
> On Tuesday, July 5, 2022 at 5:57:11 PM UTC-6, Stephen Fuld wrote:
>
> > Why do you want to keep the base register. It was, IMO a bad idea from
> > the start. In order to keep it, you are reducing the number of
> > registers to 8, which will hurt a lot. Just dump it and use those four
> > instruction bits to get a 16 bit displacement from the start.

> What good is a 16-bit displacement without a base register? Unless
> you have only 64K of memory.

However, I shouldn't be _too_ hard on you. You are right that there's
a weakness in the base register model. But I have addressed that weakness
in a fancy feature of my memory addressing scheme that I didn't mention:
Array Mode.

When the base register is zero, then the 16 bit displacement field is divided
up. Either it's the bit 0 and a 15-bit displacement, or its the bit 1, a three-bit
base register indicating a base register from *another* set of 8 registers
(actually seven, from 17 to 23) and a 12-bit displacement. So, if seven base
registers with 16-bit displacements aren't enough, I have one more with a
15-bit displacement, and seven more with 12-bit displacements.

But if the _second_ base register field contains 000, then the 12-bit displacement
is chopped up.

In any event, Array Mode works like this:

There is a small area of memory which contains an array of pointers. One can
address that area of memory directly, to load the pointers. One can also address
that area of memory indirectly, with post-indexing.

This is how I address the fault of base-displacement addressing:

It's just fine if you have more than 64K named simple variables or short arrays in
your program. But what program is going to have that many variables in it?

However, every time you have an array bigger than 64K, you either
have to allocate a base register to *each such array*, or have extra instructions
in your program that keep reloading certain base registers for whichever array you
are currently accessing.

This way, by using indirect addressing, we have static pointers to all the
arrays a program might use, without the need to insert extra instructions into
the program.

John Savard

On Tuesday, July 5, 2022 at 11:26:20 PM UTC-6, Quadibloc wrote:

> However, I shouldn't be _too_ hard on you. You are right that there's
> a weakness in the base register model. But I have addressed that weakness
> in a fancy feature of my memory addressing scheme that I didn't mention:
> Array Mode.

This discussion has given me an idea.

Since I've designed the addressing scheme so that the case of base register
field = 0 leaves you with everything you "really" need, a 32K segment for
your main program, plus a bunch of 4K segments for handling shared variables
with other programs, and Array Mode, which is the "right" way to handle arrays...

why not replace the regular base register field with just a one-bit field?

That one-bit field could indicate either a 64K segment (presumably the
program's main data segment) or the base-register-zero scheme noted
previously, in which the 32K segment would now be usually the program's
main _code_ segment.

So you have one large data segment, one not quite as large code segment,
several small segments for shared variables, and a robust mechanism for
lots of large arrays if needed.

John Savard

Quadibloc wrote:

> On Tuesday, July 5, 2022 at 5:57:11 PM UTC-6, Stephen Fuld wrote:
>
> > Why do you want to keep the base register. It was, IMO a bad idea
> > from the start. In order to keep it, you are reducing the number of
> > registers to 8, which will hurt a lot. Just dump it and use those
> > four instruction bits to get a 16 bit displacement from the start.
>
> What good is a 16-bit displacement without a base register? Unless
> you have only 64K of memory.
>
> First, you have to arrange a way to access locations everywhere in the
> entire address space. Then you can add indexing. The S/360 had nice
> simple orthogonal base registers - whereas x86 has a complicated
> segment register scheme. Before the S/360, one had schemes that are
> currently not considered good: a zero page/current page bit, and/or
> indirect addressing.
>
> Is there some other way of addressing more than 64K without a huge
> displacement that other modern architectures are using that I've
> missed?

Sure. You only need to add one register to the displacement, not two.
Thus, with suitable arithmetic, the "index" register can serve as the
displacement register. I believe that is the way most architectures do
it. BTW, the idocy of the base register is even more apparent on
Register to Register instructions. What meaning does it have there?

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

On Wednesday, July 6, 2022 at 12:03:55 AM UTC-6, Stephen Fuld wrote:

> Sure. You only need to add one register to the displacement, not two.
> Thus, with suitable arithmetic, the "index" register can serve as the
> displacement register. I believe that is the way most architectures do
> it.

Yes, but that has a problem. You're doing an extra add instruction when
you access an array, instead of array access being automatic and built
in.

> BTW, the idocy of the base register is even more apparent on
> Register to Register instructions. What meaning does it have there?

Huh? Register to register instructions don't have a base register field.

Not on the System/360, and not on any of my architectures.

John Savard

On 06/07/2022 08:44, Quadibloc wrote:
> On Wednesday, July 6, 2022 at 12:03:55 AM UTC-6, Stephen Fuld wrote:
>
>> Sure. You only need to add one register to the displacement, not two.
>> Thus, with suitable arithmetic, the "index" register can serve as the
>> displacement register. I believe that is the way most architectures do
>> it.
>
> Yes, but that has a problem. You're doing an extra add instruction when
> you access an array, instead of array access being automatic and built
> in.

Having two registers that are added to form the effective address looks
like a win - after all, you are doing "x = *(a + i + offset)" in one
instruction. With no base (or, alternatively, no index) you need to do
"b = a + i; x = *(b + offset)" in two instructions.

However, your coding is highly restrictive about the registers it can
use. This means you are likely to need additional move instructions to
shuffle things around - negating the gains. And in the RISC-style
coding, any time you can re-use the pre-calculated "b = a + i" address,
you win again.

Another possibility to consider is that in addressing modes that have
two registers, you could have a much smaller displacement than 16-bits.
The displacement lets you access fields within structs that are in an
array. Maybe 6 bits is enough to cover almost all uses, leaving you 10
free bits to expand your register fields.

>
>> BTW, the idocy of the base register is even more apparent on
>> Register to Register instructions. What meaning does it have there?
>
> Huh? Register to register instructions don't have a base register field.
>
> Not on the System/360, and not on any of my architectures.
>
> John Savard

On Tuesday, July 5, 2022 at 5:48:16 PM UTC-6, MitchAlsup wrote:

> Warning Will Robinson: you have take the wrong turn a few days
> back.....

Maybe it was at Albuquerque...

This discussion, however, has given me an idea. No doubt, though, it is
just another wrong turn.

Instructions will continue to be fetched in blocks of eight 32-bit
instructions. However, there will be no block headers. Instead, the
instruction set will be... disguised... as a thoroughly conventional
32-bit RISC architecture.

Instruction formats:

A pair of 16-bit instructions:

0
15 bits of instruction
0 15 bits of instruction

Register-to-register instructions:

0
13 bits of opcode
00
1 destination register: 5 bits
operand register: 5 bits
source register: 5 bits

(The 00 bits are reserved for indicating that the operand register
and source register bits are instead pointers to pseudo-immediates
when a header is in effect due to an INBWH instruction, as explained
below.)

Memory-reference instructions:

1
Opcode: 5 bits
Destination register: 5 bits
Index register: 5 bits
Displacement: 16 bits

However:
- if the index register field contains 00000,
the instruction is not indexed.
- registers 1 through 23 may be used as
index registers.

If the index register field contents are of the
form 11nnn, then nnn indicates the index
register; 000 indicates no indexing, registers
1 through 7 may be used as index registers in
this case.

Then the 16-bit displacement field is divided
up to allow either a 15 bit displacement or
12 bit displacements with a 3-bit base register
field or Array Mode and so on.

When this _isn't_ done, the index register doesn't
have to serve as a base register. Instead,
the base register is either the "code segment"
register or the "data segment" register.

These pointer registers, though, aren't special registers.

Instead, there are two five-bit special registers, the
code segment pointer and the data segment pointer,
which each indicate which of the 32 general registers
serve as the pointers to the code segment and data segment.

Perhaps they'd better be five-bit fields in the PSW.
Having too many things to save and restore is
a bad idea. Or even just have general register 30
always point to the code segment, and general register
31 always point to the data segment. Sort of like having
two base registers.

Now, then.

I am fetching instructions in groups of eight, and
decoding them in parallel.

There are no block headers... not at the start of a
block, anyways.

But I still want to have "pseudo-immediates" - immediate values
that somehow in no way whatever disrupt parallel decoding.

So *instead* of a header at the start of a block, in the *previous*
block I execute an instruction...

Interpret Next Block With Header.

The bits of the header, of course, are part of the 32-bit instruction.

Incidentally, the header, and the bit in the PSW that says "use the
header" are *not* cleared when a branch instruction is
executed, so if you have the *same* INBWH instruction
in the block branching to a modified by header block as in the
block preceding and falling through to it, that could even
work.

I was thinking of also having two sets of two 8-element
push-down stacks in which "short prefixes" and "long prefixes" could
be placed - in the preceding block, for use by instructions in the
next block - to allow instructions longer than 32 bits.

However, that mechanism is, I think, too complicated, and
the INBWH mechanism is sufficient to handle long instructions as
well without adding extra complications.

John Savard

On Wednesday, July 6, 2022 at 1:06:13 AM UTC-6, David Brown wrote:

> Another possibility to consider is that in addressing modes that have
> two registers, you could have a much smaller displacement than 16-bits.
> The displacement lets you access fields within structs that are in an
> array. Maybe 6 bits is enough to cover almost all uses, leaving you 10
> free bits to expand your register fields.

I have Array Mode for that: a 9 bit displacement picks out a pointer
to a particular array, and then the index register points out the element
of the array. I don't have an additional displacement for elements of structures.

The displacement is used to pick out *which array I'm using*. The index register
picks out the element of the array... and the base register indicates, normally,
*which address space or segment is the array contained in*. A segment might
be 64K, it might be 4K, but it could hardly be 64 bytes long. To do things your
way, the base register would have to be *loaded* with the address of the *individual
array* instead of being the static address of a whole segment the program
uses.

I'm using the S/360 as a model, rather than using RISC architectures as the model.

John Savard

On Wednesday, July 6, 2022 at 1:07:20 AM UTC-6, Quadibloc wrote:

> I was thinking of also having two sets of two 8-element
> push-down stacks in which "short prefixes" and "long prefixes" could
> be placed - in the preceding block, for use by instructions in the
> next block - to allow instructions longer than 32 bits.

The idea, of course, is that there's a set of short and long prefix
stacks for the _next_ block that can only be PUSHed, and a set
of short and long prefix stacks for the _current_ block that can
only be POPped.

John Savard

On 7/5/2022 6:25 PM, Quadibloc wrote:
> ...is difficult to see.
> But one goal that has been a constant is high code density.
> Even though the IBM System/360 was not considered to have been a
> system with particularly dense code, my goal of not having code
> density that is any _worse_ than it had, while adding extra features,
> has led to... exertions.
>
> So, in my original Concertina design, I took the 32-bit memory-reference
> format of System/360, which was
>
> opcode: 8 bits
> destination register: 4 bits
> index register: 4 bits
> base register: 4 bits
> displacement: 12 bits
>
> and, in order to increase the displacement to 16 bits, as found in many
> microprocessors today, I went to
>
> opcode: 7 bits
> destination register: 3 bits
> index register: 3 bits
> base register: 3 bits
> displacement: 16 bits
>

Would not be worth it...

For typical struct and stack-frame offsets, a 16-bit displacement is
overkill;
For things like accessing global variables, it is still nowhere near
sufficient; for a "typical sized binary", somewhere around 22 to 26 bits
is needed here.

More so, one doesn't generally need both a displacement and an index at
the same time. For a 32-bit instruction format, it makes more sense to
have these cases as mutually exclusive.

The limited number of registers is going to hurt a lot more than a
smaller displacement.

As noted, in my case the vast majority of displacements still fit within
a 9-bit displacement field.

Though, this was still an upgrade from the 5-bit immediate and
displacement fields more commonly used in early forms of the ISA.

Adding some debug stats to my compiler
Doom numbers:
Disp-Hit(Scaled): 5u=86.60% 9u=98.62% 10s=99.08% 12s=99.68%
Disp-Hit(Byte): 5u=31.25% 9u=96.91% 10s=97.37% 12s=99.06%
Quake numbers:
Disp-Hit(Scaled): 5u=76.07% 9u=96.51% 10s=96.69% 12s=99.49%
Disp-Hit(Byte): 5u=29.70% 9u=93.81% 10s=93.99% 12s=96.15%

Scaled 9u and 10s are the cases which exist in BJX2 (10s being a special
pseudo-case that exists via gluing together the 9u and 5n cases, the
latter existing implicitly via the XGPR encodings, modeled as -32..511;
whereas 12s is -2048..2047).

Byte-Scaled Disp12s is the typical case for RISC-V.

In Doom, non-scaled 12s beats scaled 9u, but in Quake it is the reverse.

Also shows that scaling the displacement by the element size is
reasonably effective (1).

Increasing the number of bits further seems to be in "diminishing
returns" territory.

1: With typical alignment rules, it has negligible effect on miss rate.
A misaligned/packed load/store would need to be encoded like:
MOV Disp, R0
MOV.x (Rm, R1), Rn
Where R1 is interpreted as R0 (but non-scaled).
This case is rare enough that it can be mostly ignored for sake of
stats-gathering. Likewise, there are significantly more positive
displacements than negative ones (hence why I went with 9u rather than 9s).

It appears the hit-rate for RegImmReg ops is a little lower though.
Doom:
Imm-Hit: 9u=70.67% 5u=47.11% 9n=34.99%, 5n=23.23%
Quake:
Imm-Hit: 9u=68.01% 5u=44.63% 9n=34.86%, 5n=20.71%

I guess maybe one could justify spending a few extra bits on things like
"ADD Rm, Imm, Rn" and similar.

Hit rate would be a little better for ops with both 9u and 9n forms (eg:
ADD and ADDS.L), but this isn't modeled in this case.

In cases where these fail, this is where jumbo-encodings or explicit
constant loads come in (well, along with cases like "No RegImmReg case
actually exists, but it is more convenient for code-generation to
pretend that it does and insert a constant load at the last moment").

By contrast, 3-bit register fields means that the generated code is
likely going to be an almost non-stop stream of register spill and fill.

> which was reasonable enough; a similar instruction format is used
> in the Cray I.
>
> To change to a RISC-like architecture - but retaining base-index
> addressing - I wanted to increase the destination register field to 5 bits.
>
> This can be done, as a 5 bit opcode is enough for load and store
> instructions. However, that means the load and store instructions use
> up almost 3/4 of the available opcode space. I wanted to carve out 1/4
> of the opcode space to allow me to put pairs of 16-bit instructions in
> the 32-bit instruction words.
>
> At this point, what I have been doing is shrinking the load and store
> instructions considerablty by restricting them to aligned operands - and
> using what would be the unused displacement bits to indicate the
> operand type.
>
> But recently I was toying with a way to avoid this restriction... and here is
> the monstrosity I came up with.
>
> Unindexed instruction:
>
> 1 (to indicate memory-reference instruction)
> opcode: 5 bits
> destination register: 5 bits
> 00 (to indicate unindexed instruction)
> base register: 3 bits
> displacement: 16 bits
>
> Indexed instruction:
>
> 1 (to indicate memory-reference instruction)
> opcode: 5 bits
> destination register: 4 bits
> index register: 3 bits
> base register: 3 bits
> displacement: 16 bits
>
> So the base register would be, perhaps, one of
> registers 25 through 31.
>
> The available index registers would be registers
> 1, 2, 3, 5, 6, and 7. Neither register 0 nor register 4
> would be available for use as an index register.
>
> And only even-numbered registers could be used with
> indexed loads and stores!
>

Groan...

> There are historical computer designs with even weirder
> and less orthogonal restrictions, but coming up with wild
> ideas like this does seem to indicate I'm going in the wrong
> direction...
>

Short answer: Yes.

Sadly, chasing the local optimum constrains the design space some.

In terms of register-field size:
3: Not Enough (would result in a high spill rate)
4: Mostly Workable
5: Probably Optimal
6: Probably a Bit Over
7: We Itanium Now

I was mostly using 5-bit register fields, but had extended the ISA to 64
GPRs via hacks (R32..R63 only exist in 32-bit encodings for a subset of
the ISA).

Ironically, sorta works OK if one also extends "pretty much everything"
to 128 bits, since in my case 128-bit "Xn" registers are even-only, and
thus can still be encoded in the 5 bit register fields. Then only a
minority of instructions needing to resort to 64-bit encodings.

Though, at present, by default BGBCC is still mostly ignoring that
R32..R63 exist, and XGPR is at this point relatively unlikely to be
added to the baseline ISA.

Both XGPR and the Dual-ISA RISC-V mode are in this gray area between
"potentially useful" and "kind of an epic fail". Dust hasn't settled
enough on them to solidly make a determination yet.

On Wednesday, July 6, 2022 at 12:07:47 AM UTC-5, Quadibloc wrote:
> On Tuesday, July 5, 2022 at 5:57:11 PM UTC-6, Stephen Fuld wrote:
>
> > Why do you want to keep the base register. It was, IMO a bad idea from
> > the start. In order to keep it, you are reducing the number of
> > registers to 8, which will hurt a lot. Just dump it and use those four
> > instruction bits to get a 16 bit displacement from the start.
<
> What good is a 16-bit displacement without a base register? Unless
> you have only 64K of memory.
<
He is suggesting that you have 1 register and a 16-bit displacement as
the major format, I suggest that you also have a base+index register format.
I went further to base+scaled_index+displacement on demand.
>
> First, you have to arrange a way to access locations everywhere in the
> entire address space. Then you can add indexing. The S/360 had nice
> simple orthogonal base registers - whereas x86 has a complicated
> segment register scheme. Before the S/360, one had schemes that are
> currently not considered good: a zero page/current page bit, and/or
> indirect addressing.
<
All of that is a pointer-register; base-register has other entanglements.
>
> Is there some other way of addressing more than 64K without a huge
> displacement that other modern architectures are using that I've missed?
>
> Also, instead of reducing the number of registers to 8, as I did in the
> original Concertina, I'm going with 32 registers - but only the first 8
> may be index registers and the last 8 may be base registers. So I don't
> limit the architecture to 8 registers, although 32 are no longer enough
> to do away with the need for out-of-order execution.
>
> John Savard

On Wednesday, July 6, 2022 at 2:06:13 AM UTC-5, David Brown wrote:
> On 06/07/2022 08:44, Quadibloc wrote:
> > On Wednesday, July 6, 2022 at 12:03:55 AM UTC-6, Stephen Fuld wrote:
> >
> >> Sure. You only need to add one register to the displacement, not two.
> >> Thus, with suitable arithmetic, the "index" register can serve as the
> >> displacement register. I believe that is the way most architectures do
> >> it.
> >
> > Yes, but that has a problem. You're doing an extra add instruction when
> > you access an array, instead of array access being automatic and built
> > in.
> Having two registers that are added to form the effective address looks
> like a win - after all, you are doing "x = *(a + i + offset)" in one
> instruction. With no base (or, alternatively, no index) you need to do
> "b = a + i; x = *(b + offset)" in two instructions.
<
Note: Base+index+displacement represents only 2% of memory refs.
Base+disp and base+index represent the very vast majority. Compilers
have ways of turning Base+index+displacement into base+index inside
of loops.
>
> However, your coding is highly restrictive about the registers it can
> use. This means you are likely to need additional move instructions to
> shuffle things around - negating the gains. And in the RISC-style
> coding, any time you can re-use the pre-calculated "b = a + i" address,
> you win again.
>
> Another possibility to consider is that in addressing modes that have
> two registers, you could have a much smaller displacement than 16-bits.
> The displacement lets you access fields within structs that are in an
> array. Maybe 6 bits is enough to cover almost all uses, leaving you 10
> free bits to expand your register fields.
> >
> >> BTW, the idocy of the base register is even more apparent on
> >> Register to Register instructions. What meaning does it have there?
> >
> > Huh? Register to register instructions don't have a base register field.
> >
> > Not on the System/360, and not on any of my architectures.
> >
> > John Savard

On Wednesday, July 6, 2022 at 2:14:02 AM UTC-5, Quadibloc wrote:
> On Wednesday, July 6, 2022 at 1:06:13 AM UTC-6, David Brown wrote:
>
> > Another possibility to consider is that in addressing modes that have
> > two registers, you could have a much smaller displacement than 16-bits.
> > The displacement lets you access fields within structs that are in an
> > array. Maybe 6 bits is enough to cover almost all uses, leaving you 10
> > free bits to expand your register fields.
> I have Array Mode for that: a 9 bit displacement picks out a pointer
> to a particular array, and then the index register points out the element
> of the array. I don't have an additional displacement for elements of structures.
>
> The displacement is used to pick out *which array I'm using*. The index register
> picks out the element of the array... and the base register indicates, normally,
> *which address space or segment is the array contained in*. A segment might
> be 64K, it might be 4K, but it could hardly be 64 bytes long. To do things your
> way, the base register would have to be *loaded* with the address of the *individual
> array* instead of being the static address of a whole segment the program
> uses.
>
> I'm using the S/360 as a model, rather than using RISC architectures as the model.
<
Some of us are trying to nudge you into correcting that deficit.
>
> John Savard

On Wednesday, July 6, 2022 at 10:00:50 AM UTC-6, MitchAlsup wrote:

> Note: Base+index+displacement represents only 2% of memory refs.
> Base+disp and base+index represent the very vast majority. Compilers
> have ways of turning Base+index+displacement into base+index inside
> of loops.

My picture, of course, is:

Base+Displacement is used to refer to simple variables.
Base+Index+Displacement is used to refer to elements of short arrays
(Base+Displacement)+Index is used to refer to elements of long arrays

so that the compiler doesn't have to do _any work at all_ (except for the
arithmetic to scale the subscript and combine dimensions). Of course,
if the programmer uses exotic stuff like _structures_, *then* the
compiler will have to do additional arithmetic.

John Savard

On Wednesday, July 6, 2022 at 10:01:31 AM UTC-6, MitchAlsup wrote:
> On Wednesday, July 6, 2022 at 2:14:02 AM UTC-5, Quadibloc wrote:

> > I'm using the S/360 as a model, rather than using RISC architectures as the model.
> <
> Some of us are trying to nudge you into correcting that deficit.

Oh, I _have_ noticed. But basically I view the deficiencies of the 680x0, x86, and
modern RISC architectures... as the things they're omitting that the S/360 had.

Thus, the 68020 had base+index+displacement, but if the displacement was 16 bits,
the instruction was 48 bits long; only if the displacement was 8 bits would the instruction
be 32 bits long. That falls short of the 360, therefore it must be remedied!

And so fitting the capabilities of the System/360 into an ISA that makes a few
nods here and there to what today's machines do (like increasing the displacement
from 12 bits to 16 bits) is my *fundamental goal*.

So I'm trying to achieve...

An architecture that does _almost_ everything the S/360 did,
consuming no more bits per instruction, for any instruction type than the S/360,
and adding modern capabilities like... 16 bit displacements instead of 12 bit
displacements; the ability to decode instructions in parallel instead of serially
determining their lengths

and this does mean that I'm trying to squeeze an awful lot into each 32-bit
instruction.

That my goal may be wildly misguided is... something I have considered.

John Savard

On Wednesday, July 6, 2022 at 1:07:20 AM UTC-6, Quadibloc wrote:

> So *instead* of a header at the start of a block, in the *previous*
> block I execute an instruction...
>
> Interpret Next Block With Header.

This of course is a mistake. Besides needing *two* of them if I
also branch into a modified block, it means there are two ways to
read the instructions in a block.

So I should stick with headers at the start of block.

However, using extra bits in some instructions to have a flag that
says "next block has a header", a sort of vestige of this, has its
uses... that way, _absent_ such a flag, decoding each instruction
in parallel can go faster, as there's no delay, then, before later
instructions can be decoded while it is determined if the first
instruction slot contains a header! (But of course going to such
a length to save a few gate delays is a mistake.)

John Savard

Quadibloc wrote:

> On Wednesday, July 6, 2022 at 12:03:55 AM UTC-6, Stephen Fuld wrote:
>
> > Sure. You only need to add one register to the displacement, not
> > two. Thus, with suitable arithmetic, the "index" register can
> > serve as the displacement register. I believe that is the way most
> > architectures do it.
>
> Yes, but that has a problem. You're doing an extra add instruction
> when you access an array, instead of array access being automatic and
> built in.

No, At the beginning, you load a register with the address of the
start of the array. Then, after each access, you add the length of the
array element to the register. The register now points to the next
element.

One register and one add per access.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

On 7/6/2022 10:58 AM, MitchAlsup wrote:
> On Wednesday, July 6, 2022 at 12:07:47 AM UTC-5, Quadibloc wrote:
>> On Tuesday, July 5, 2022 at 5:57:11 PM UTC-6, Stephen Fuld wrote:
>>
>>> Why do you want to keep the base register. It was, IMO a bad idea from
>>> the start. In order to keep it, you are reducing the number of
>>> registers to 8, which will hurt a lot. Just dump it and use those four
>>> instruction bits to get a 16 bit displacement from the start.
> <
>> What good is a 16-bit displacement without a base register? Unless
>> you have only 64K of memory.
> <
> He is suggesting that you have 1 register and a 16-bit displacement as
> the major format, I suggest that you also have a base+index register format.
> I went further to base+scaled_index+displacement on demand.

I agree that these cases should be exclusive (with both displacement and
index forms being present), but still feel that a 16-bit displacement
here is overkill for a 32-bit instruction format.

Like, say, if one spends 4 more bits (vs 12 bits), but only reduces the
number of overflowed cases by 0.5% or so, this isn't really a win IMO.

As noted from my other stats, scaling the displacement by the accessed
element size gains around 2 or 3 bits of range "basically for free"
(whereas signed displacement basically loses a bit given the rarity of
negative displacements).

Well, unless one does an x86 style frame-pointer, in which case there is
going to be a lot of negative displacements (assuming a traditional
"grows downwards" stack design).

Though, I guess it is a mystery how much code would break with a "grows
upwards" stack and evaluating function arguments left-to-right rather
than right-to-left, ...

I suspect though that full [Base+Index<<Scale+Disp] is likely not common
enough to justify its inclusion, at least for 32 bit encodings, and
still has a non-zero cost in other areas (needing to encode this case as
a 2-instruction sequence does not seem unreasonable IMO; But, does
basically require having "LEA" style instructions though).

>>
>> First, you have to arrange a way to access locations everywhere in the
>> entire address space. Then you can add indexing. The S/360 had nice
>> simple orthogonal base registers - whereas x86 has a complicated
>> segment register scheme. Before the S/360, one had schemes that are
>> currently not considered good: a zero page/current page bit, and/or
>> indirect addressing.
> <
> All of that is a pointer-register; base-register has other entanglements.
>>
>> Is there some other way of addressing more than 64K without a huge
>> displacement that other modern architectures are using that I've missed?
>>
>> Also, instead of reducing the number of registers to 8, as I did in the
>> original Concertina, I'm going with 32 registers - but only the first 8
>> may be index registers and the last 8 may be base registers. So I don't
>> limit the architecture to 8 registers, although 32 are no longer enough
>> to do away with the need for out-of-order execution.
>>
>> John Savard

On 7/6/2022 11:22 AM, Quadibloc wrote:
> On Wednesday, July 6, 2022 at 10:01:31 AM UTC-6, MitchAlsup wrote:
>> On Wednesday, July 6, 2022 at 2:14:02 AM UTC-5, Quadibloc wrote:
>
>>> I'm using the S/360 as a model, rather than using RISC architectures as the model.
>> <
>> Some of us are trying to nudge you into correcting that deficit.
>
> Oh, I _have_ noticed. But basically I view the deficiencies of the 680x0, x86, and
> modern RISC architectures... as the things they're omitting that the S/360 had.
>
> Thus, the 68020 had base+index+displacement, but if the displacement was 16 bits,
> the instruction was 48 bits long; only if the displacement was 8 bits would the instruction
> be 32 bits long. That falls short of the 360, therefore it must be remedied!
>
> And so fitting the capabilities of the System/360 into an ISA that makes a few
> nods here and there to what today's machines do (like increasing the displacement
> from 12 bits to 16 bits) is my *fundamental goal*.
>
> So I'm trying to achieve...
>
> An architecture that does _almost_ everything the S/360 did,
> consuming no more bits per instruction, for any instruction type than the S/360,
> and adding modern capabilities like... 16 bit displacements instead of 12 bit
> displacements; the ability to decode instructions in parallel instead of serially
> determining their lengths
>
> and this does mean that I'm trying to squeeze an awful lot into each 32-bit
> instruction.
>
> That my goal may be wildly misguided is... something I have considered.
>

How about(?):
ISA makes 64-bit instructions the canonical format;
Can then treat 32-bit encodings as the "compressed" variant;
...

Of course, 64-bit instructions still can't encode a 64-bit immediate.

But, making 96 or 128 bit instructions the canonical format would be
kinda absurd.

Well, probably don't want to add too much fuel to the fire...

How it works in my case is a little ambiguous, as effectively the
"32-bit" instruction decoder is actually around 60 bits, with the 32-bit
instruction word as input, and bits from a paired Jumbo prefix as the
other input (the 96-bit instruction formats are partially handled as a
special case that is decoded across two lanes).

Say:
Lane 1: Handles Immed(31: 0), Decodes Instruction + Jumbo Bits
Lane 2: Handles Immed(63:32), Decodes Jumbo Prefix + More Jumbo Bits

So, say, the instruction decoder sees that it has been given a pair of
Jumbo prefixes and proceeds to spit out an immediate-field representing
the high 32 bits of the immediate (but otherwise still a NOP).

> John Savard

On Wednesday, July 6, 2022 at 11:22:42 AM UTC-5, Quadibloc wrote:
> On Wednesday, July 6, 2022 at 10:01:31 AM UTC-6, MitchAlsup wrote:
> > On Wednesday, July 6, 2022 at 2:14:02 AM UTC-5, Quadibloc wrote:
>
> > > I'm using the S/360 as a model, rather than using RISC architectures as the model.
> > <
> > Some of us are trying to nudge you into correcting that deficit.
> Oh, I _have_ noticed. But basically I view the deficiencies of the 680x0, x86, and
> modern RISC architectures... as the things they're omitting that the S/360 had.
<
So did I when architecting My 66000 ISA. But I also took into account the utility of
the feature with respect to modern compiler technology, and ended up with the
same 360 ISA model but with 32 registers. I augmented it with IP relative addressing,
and large displacements. And it still ends up smelling like RISC--it is RISC with a few
features added.
>
> Thus, the 68020 had base+index+displacement, but if the displacement was 16 bits,
> the instruction was 48 bits long; only if the displacement was 8 bits would the instruction
> be 32 bits long. That falls short of the 360, therefore it must be remedied!
<
B+I+D is only used 2% of the time. So while one can encode it in My 66000, one
still has access to B+D and B+I without exceeding 32-bits.
>
> And so fitting the capabilities of the System/360 into an ISA that makes a few
> nods here and there to what today's machines do (like increasing the displacement
> from 12 bits to 16 bits) is my *fundamental goal*.
<
I assert My 66000 reached those goals and vastly surpassed them.
>
> So I'm trying to achieve...
<
One cannot achieve with blinders what one can achieve without !!
>
> An architecture that does _almost_ everything the S/360 did,
> consuming no more bits per instruction, for any instruction type than the S/360,
> and adding modern capabilities like... 16 bit displacements instead of 12 bit
> displacements; the ability to decode instructions in parallel instead of serially
> determining their lengths
>
> and this does mean that I'm trying to squeeze an awful lot into each 32-bit
> instruction.
>
> That my goal may be wildly misguided is... something I have considered.
>
> John Savard

On Wednesday, July 6, 2022 at 6:07:47 AM UTC+1, Quadibloc wrote:

> Is there some other way of addressing more than 64K without a huge
> displacement that other modern architectures are using that I've missed?

Power ISA v3.1 64-bit prefixes. adds (i think) an extra 18-bits to immediates.
gets up to 34-bit immediates in some cases.

l.

Quadibloc wrote:

> On Wednesday, July 6, 2022 at 10:01:31 AM UTC-6, MitchAlsup wrote:
> > On Wednesday, July 6, 2022 at 2:14:02 AM UTC-5, Quadibloc wrote:
>
> > > I'm using the S/360 as a model, rather than using RISC
> > > architectures as the model.
> > <
> > Some of us are trying to nudge you into correcting that deficit.
>
> Oh, I have noticed. But basically I view the deficiencies of the
> 680x0, x86, and modern RISC architectures... as the things they're
> omitting that the S/360 had.

OK, so what features specifically did S/360 have that none of the
others you mentioned had that were so beneficial? Surely it was more
than just the limit to the displacement field of the 68020.

Remember, the original reason for base registers was to allow multiple
programs to be run in different locations in memory without the
programmer having to code for specific real addresses. Of course S/360
was a "real memory" machine - no paging, etc. So a program had to
execute a BALR instruction right at the beginning to "capture" the read
address of where the program was atually loaded, then use that "base"
for all subsequent references. Other vendors used different solutions
for this problem, e.g. base register that was not visible to the
program but saved in say its register save area and was loaded by the
OS along with the user registerswhenever it gave control to a use
program. IMHO, this was a better solution, as it freed a user register
for other use. And, of course, the need for all of this went away when
virtual memory with separate address spaces per user became available.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)