On Wednesday, February 2, 2022 at 4:17:14 PM UTC-6, MitchAlsup wrote:
> On Wednesday, February 2, 2022 at 3:39:15 PM UTC-6, JimBrakefield wrote:
>
> > Some comments:
> > A) In the modern uP arch, instruction flow is separated from data flow. Thus there is negligible hardware cost in having instruction granularity different from data granularity.
> <
> Indeed--clever observation
> <
> > B) Why use the remaining bits to re-sync the instruction addresses? E.g.. why not have 21 bit instruction granularity instead of 20 bit? Re-sync to always occur at the start of 64 or 128 or 256-bit instruction block?
> <
> two (2) bits are not used 21×6 = 126
> <
> > C) Opens a new arena for uP architecture, eg instruction formats not tied to data granularity.
> <
> Indeed
> <
> > D) Need a name for for the concept. Maybe there is already an ISA of this nature (other than stack machines with very short instructions)?
> <
> Mill instruction formats and layout are similar, but not based on fixed sized containers and are also model specific.
> <
> > E) Need yet another name for the concept of using some of the remaining instruction block bits for (usually) decode purposes?
> <
> Instruction Containerization ! {And I give permission for you to steal this name)

Containerized ISAs !

On Wednesday, February 2, 2022 at 10:32:49 AM UTC-7, MitchAlsup wrote:
> On Wednesday, February 2, 2022 at 11:04:44 AM UTC-6, Quadibloc wrote:
> > On Wednesday, February 2, 2022 at 9:39:54 AM UTC-7, Stephen Fuld wrote:
> > > And one
> > > quibble; you may need the address of the next instruction in the bundle
> > > to handle the case of the current instruction is a CALL type instruction
> > > that puts the address of the next instruction in a register.
> <
> > That is true; if you can branch into the middle of a bundle, then presumably
> > branches out with returns in the middle will be allowed. Here, though, I
> > think the issue will be encoding rather than calculation. If a 128-bit bundle
> > is divided into 20-bit packets, presumably packet n will be given an
> > address aligned on 16-bit boundaries which will be...
> <
> I am surprised at you--you are making the mistake that control flow addressing
> is identical to memory addressing--it is not (in this case). Instructions are located
> on 20-bit boundaries, and whether or not an instruction starts in this container
> is controlled by the header to the bundle. HW has no problem decoding to 20-bit
> boundaries, so the only constraint is that the range in the LOBs of the IP is [0..5]
> (instead of 0..7]) !!

This is interesting, because my reply to Stephen Fuld was based on percieving
him as having made that mistake.

What I was assuming was that when the control flow escapes from the internal
circuitry of the processor, and you actually have a sequence of bits that serves
as an address - _then_ it's going to be a memory address.

If I'm going to return from a subroutine, I *need* the control flow address of
the return point to quickly and easily supply me with the memory address of
the code to which I'm returning.

And so a code address might have the form (128-bit aligned memory address)
followed by (instruction number from 0 to 5). But in order to grab the memory address
really fast, a 'divide by six' numerical operation will be avoided. Plus, explaining it as
a 16-bit aligned memory address, which happens to point to a fictional location
for the instruction... just makes it easier to understand and less confusing for
the programmer (who I am assuming to have a very conventional and old-fashioned
mindset).

John Savard

On Thursday, February 3, 2022 at 12:18:54 PM UTC-6, Quadibloc wrote:
> On Wednesday, February 2, 2022 at 10:32:49 AM UTC-7, MitchAlsup wrote:
> > On Wednesday, February 2, 2022 at 11:04:44 AM UTC-6, Quadibloc wrote:
> > > On Wednesday, February 2, 2022 at 9:39:54 AM UTC-7, Stephen Fuld wrote:
> > > > And one
> > > > quibble; you may need the address of the next instruction in the bundle
> > > > to handle the case of the current instruction is a CALL type instruction
> > > > that puts the address of the next instruction in a register.
> > <
> > > That is true; if you can branch into the middle of a bundle, then presumably
> > > branches out with returns in the middle will be allowed. Here, though, I
> > > think the issue will be encoding rather than calculation. If a 128-bit bundle
> > > is divided into 20-bit packets, presumably packet n will be given an
> > > address aligned on 16-bit boundaries which will be...
> > <
> > I am surprised at you--you are making the mistake that control flow addressing
> > is identical to memory addressing--it is not (in this case). Instructions are located
> > on 20-bit boundaries, and whether or not an instruction starts in this container
> > is controlled by the header to the bundle. HW has no problem decoding to 20-bit
> > boundaries, so the only constraint is that the range in the LOBs of the IP is [0..5]
> > (instead of 0..7]) !!
> This is interesting, because my reply to Stephen Fuld was based on percieving
> him as having made that mistake.
>
> What I was assuming was that when the control flow escapes from the internal
> circuitry of the processor, and you actually have a sequence of bits that serves
> as an address - _then_ it's going to be a memory address.
<
But the HIOBs of the address access the container (128-bits)
while the LOBs have a range from [0..5] and access the 20-bit instruction start.
>
> If I'm going to return from a subroutine, I *need* the control flow address of
> the return point to quickly and easily supply me with the memory address of
> the code to which I'm returning.
<
Sure, just use the above algorithm, and take some king of exception if the
LOBs are not in range [0..5].
>
> And so a code address might have the form (128-bit aligned memory address)
> followed by (instruction number from 0 to 5). But in order to grab the memory address
> really fast, a 'divide by six' numerical operation will be avoided.
<
> Plus, explaining it as
> a 16-bit aligned memory address, which happens to point to a fictional location
> for the instruction... just makes it easier to understand and less confusing for
> the programmer (who I am assuming to have a very conventional and old-fashioned
> mindset).
<
Why is the <ahem> programmer concerned with the size of individual instructions?
They are not from machines as diverse as B5500-to-x86-to-IBM z-series.
<
Certainly the assembler and linker need to be concerned, but the programmer ???
>
> John Savard

On Thursday, February 3, 2022 at 11:48:54 AM UTC-7, MitchAlsup wrote:

> Why is the <ahem> programmer concerned with the size of individual instructions?
> They are not from machines as diverse as B5500-to-x86-to-IBM z-series.
> <
> Certainly the assembler and linker need to be concerned, but the programmer ???

Um, it depends what you mean by "concerned". The programmer doesn't have to
calculate stuff by hand that the assembler does, but should still have a basic
general idea of how the machine being programmed works.

John Savard

MitchAlsup wrote:
> On Thursday, February 3, 2022 at 12:18:54 PM UTC-6, Quadibloc wrote:
>> On Wednesday, February 2, 2022 at 10:32:49 AM UTC-7, MitchAlsup wrote:
>>> On Wednesday, February 2, 2022 at 11:04:44 AM UTC-6, Quadibloc wrote:
>>>> On Wednesday, February 2, 2022 at 9:39:54 AM UTC-7, Stephen Fuld wrote:
>>>>> And one
>>>>> quibble; you may need the address of the next instruction in the bundle
>>>>> to handle the case of the current instruction is a CALL type instruction
>>>>> that puts the address of the next instruction in a register.
>>> <
>>>> That is true; if you can branch into the middle of a bundle, then presumably
>>>> branches out with returns in the middle will be allowed. Here, though, I
>>>> think the issue will be encoding rather than calculation. If a 128-bit bundle
>>>> is divided into 20-bit packets, presumably packet n will be given an
>>>> address aligned on 16-bit boundaries which will be...
>>> <
>>> I am surprised at you--you are making the mistake that control flow addressing
>>> is identical to memory addressing--it is not (in this case). Instructions are located
>>> on 20-bit boundaries, and whether or not an instruction starts in this container
>>> is controlled by the header to the bundle. HW has no problem decoding to 20-bit
>>> boundaries, so the only constraint is that the range in the LOBs of the IP is [0..5]
>>> (instead of 0..7]) !!
>> This is interesting, because my reply to Stephen Fuld was based on percieving
>> him as having made that mistake.
>>
>> What I was assuming was that when the control flow escapes from the internal
>> circuitry of the processor, and you actually have a sequence of bits that serves
>> as an address - _then_ it's going to be a memory address.
> <
> But the HIOBs of the address access the container (128-bits)
> while the LOBs have a range from [0..5] and access the 20-bit instruction start.
>>
>> If I'm going to return from a subroutine, I *need* the control flow address of
>> the return point to quickly and easily supply me with the memory address of
>> the code to which I'm returning.
> <
> Sure, just use the above algorithm, and take some king of exception if the
> LOBs are not in range [0..5].

I agree.

Extracting the bottom three bits, trapping if they are 11x, while at the
same time multiplying them by 20 and the top bits by 16 (trivial lookup
or shift/add for the former, just a routing issue for the top bits)
should only add one or two gate delays, right?

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On Friday, February 4, 2022 at 2:22:31 AM UTC-7, Terje Mathisen wrote:

> Extracting the bottom three bits, trapping if they are 11x, while at the
> same time multiplying them by 20 and the top bits by 16 (trivial lookup
> or shift/add for the former, just a routing issue for the top bits)
> should only add one or two gate delays, right?

Why would you _ever_ need to multiply anything by 20?

I mean, the instruction decode unit would be hardwired to find the instructions
in whatever part of the block they are put.

John Savard

On Friday, February 4, 2022 at 3:22:31 AM UTC-6, Terje Mathisen wrote:
> MitchAlsup wrote:
> > On Thursday, February 3, 2022 at 12:18:54 PM UTC-6, Quadibloc wrote:
> >> On Wednesday, February 2, 2022 at 10:32:49 AM UTC-7, MitchAlsup wrote:
> >>> On Wednesday, February 2, 2022 at 11:04:44 AM UTC-6, Quadibloc wrote:
> >>>> On Wednesday, February 2, 2022 at 9:39:54 AM UTC-7, Stephen Fuld wrote:
> >>>>> And one
> >>>>> quibble; you may need the address of the next instruction in the bundle
> >>>>> to handle the case of the current instruction is a CALL type instruction
> >>>>> that puts the address of the next instruction in a register.
> >>> <
> >>>> That is true; if you can branch into the middle of a bundle, then presumably
> >>>> branches out with returns in the middle will be allowed. Here, though, I
> >>>> think the issue will be encoding rather than calculation. If a 128-bit bundle
> >>>> is divided into 20-bit packets, presumably packet n will be given an
> >>>> address aligned on 16-bit boundaries which will be...
> >>> <
> >>> I am surprised at you--you are making the mistake that control flow addressing
> >>> is identical to memory addressing--it is not (in this case). Instructions are located
> >>> on 20-bit boundaries, and whether or not an instruction starts in this container
> >>> is controlled by the header to the bundle. HW has no problem decoding to 20-bit
> >>> boundaries, so the only constraint is that the range in the LOBs of the IP is [0..5]
> >>> (instead of 0..7]) !!
> >> This is interesting, because my reply to Stephen Fuld was based on percieving
> >> him as having made that mistake.
> >>
> >> What I was assuming was that when the control flow escapes from the internal
> >> circuitry of the processor, and you actually have a sequence of bits that serves
> >> as an address - _then_ it's going to be a memory address.
> > <
> > But the HIOBs of the address access the container (128-bits)
> > while the LOBs have a range from [0..5] and access the 20-bit instruction start.
> >>
> >> If I'm going to return from a subroutine, I *need* the control flow address of
> >> the return point to quickly and easily supply me with the memory address of
> >> the code to which I'm returning.
> > <
> > Sure, just use the above algorithm, and take some king of exception if the
> > LOBs are not in range [0..5].
> I agree.
>
> Extracting the bottom three bits, trapping if they are 11x, while at the
> same time multiplying them by 20 and the top bits by 16 (trivial lookup
> or shift/add for the former, just a routing issue for the top bits)
> should only add one or two gate delays, right?
<
There is no multiply, there is a multiplexer/shifter that selects 20-bit fields
instead of selecting 16-bit fields. The decoder can even be wired up to
assert the out-of-range exception.
<
>
> Terje
>
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

Quadibloc wrote:
> On Friday, February 4, 2022 at 2:22:31 AM UTC-7, Terje Mathisen wrote:
>
>> Extracting the bottom three bits, trapping if they are 11x, while at the
>> same time multiplying them by 20 and the top bits by 16 (trivial lookup
>> or shift/add for the former, just a routing issue for the top bits)
>> should only add one or two gate delays, right?
>
> Why would you _ever_ need to multiply anything by 20?
>
> I mean, the instruction decode unit would be hardwired to find the instructions
> in whatever part of the block they are put.

I wrote "trivial lookup", how is that different from "hardwired"? :-)

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On Wednesday, February 2, 2022 at 3:39:15 PM UTC-6, JimBrakefield wrote:
> On Wednesday, February 2, 2022 at 11:32:49 AM UTC-6, MitchAlsup wrote:
> > On Wednesday, February 2, 2022 at 11:04:44 AM UTC-6, Quadibloc wrote:
> > > On Wednesday, February 2, 2022 at 9:39:54 AM UTC-7, Stephen Fuld wrote:
> > > > And one
> > > > quibble; you may need the address of the next instruction in the bundle
> > > > to handle the case of the current instruction is a CALL type instruction
> > > > that puts the address of the next instruction in a register.
> > <
> > > That is true; if you can branch into the middle of a bundle, then presumably
> > > branches out with returns in the middle will be allowed. Here, though, I
> > > think the issue will be encoding rather than calculation. If a 128-bit bundle
> > > is divided into 20-bit packets, presumably packet n will be given an
> > > address aligned on 16-bit boundaries which will be...
> > <
> > I am surprised at you--you are making the mistake that control flow addressing
> > is identical to memory addressing--it is not (in this case). Instructions are located
> > on 20-bit boundaries, and whether or not an instruction starts in this container
> > is controlled by the header to the bundle. HW has no problem decoding to 20-bit
> > boundaries, so the only constraint is that the range in the LOBs of the IP is [0..5]
> > (instead of 0..7]) !!
> > <
> > > associated with one
> > > of the packets. The encoding scheme will presumably make those addresses
> > > consecutive, to simplify the calculation that needs to be done.
> > >
> > > John Savard
> Some comments:
> A) In the modern uP arch, instruction flow is separated from data flow. Thus there is negligible hardware cost in having instruction granularity different from data granularity.
> B) Why use the remaining bits to re-sync the instruction addresses? E.g. why not have 21 bit instruction granularity instead of 20 bit? Re-sync to always occur at the start of 64 or 128 or 256-bit instruction block?
> C) Opens a new arena for uP architecture, eg instruction formats not tied to data granularity.
> D) Need a name for for the concept. Maybe there is already an ISA of this nature (other than stack machines with very short instructions)?
> E) Need yet another name for the concept of using some of the remaining instruction block bits for (usually) decode purposes?

The next thing needing discussion is relative branches. In order to avoid division by small odd numbers, the branch displacement also needs to have the container plus packet location format. The branch address is then a modulo add with carry between the current instruction location and the relative displacement. Leading to the conclusion that instruction addresses and displacements need to be a distinct category or "type" from data addresses and offsets (which use whole binary numbers).

JimBrakefield wrote:
> On Wednesday, February 2, 2022 at 3:39:15 PM UTC-6, JimBrakefield wrote:
>> On Wednesday, February 2, 2022 at 11:32:49 AM UTC-6, MitchAlsup wrote:
>>> On Wednesday, February 2, 2022 at 11:04:44 AM UTC-6, Quadibloc wrote:
>>>> On Wednesday, February 2, 2022 at 9:39:54 AM UTC-7, Stephen Fuld wrote:
>>>>> And one
>>>>> quibble; you may need the address of the next instruction in the bundle
>>>>> to handle the case of the current instruction is a CALL type instruction
>>>>> that puts the address of the next instruction in a register.
>>> <
>>>> That is true; if you can branch into the middle of a bundle, then presumably
>>>> branches out with returns in the middle will be allowed. Here, though, I
>>>> think the issue will be encoding rather than calculation. If a 128-bit bundle
>>>> is divided into 20-bit packets, presumably packet n will be given an
>>>> address aligned on 16-bit boundaries which will be...
>>> <
>>> I am surprised at you--you are making the mistake that control flow addressing
>>> is identical to memory addressing--it is not (in this case). Instructions are located
>>> on 20-bit boundaries, and whether or not an instruction starts in this container
>>> is controlled by the header to the bundle. HW has no problem decoding to 20-bit
>>> boundaries, so the only constraint is that the range in the LOBs of the IP is [0..5]
>>> (instead of 0..7]) !!
>>> <
>>>> associated with one
>>>> of the packets. The encoding scheme will presumably make those addresses
>>>> consecutive, to simplify the calculation that needs to be done.
>>>>
>>>> John Savard
>> Some comments:
>> A) In the modern uP arch, instruction flow is separated from data flow. Thus there is negligible hardware cost in having instruction granularity different from data granularity.
>> B) Why use the remaining bits to re-sync the instruction addresses? E.g. why not have 21 bit instruction granularity instead of 20 bit? Re-sync to always occur at the start of 64 or 128 or 256-bit instruction block?
>> C) Opens a new arena for uP architecture, eg instruction formats not tied to data granularity.
>> D) Need a name for for the concept. Maybe there is already an ISA of this nature (other than stack machines with very short instructions)?
>> E) Need yet another name for the concept of using some of the remaining instruction block bits for (usually) decode purposes?
>
> The next thing needing discussion is relative branches. In order to avoid division by small odd numbers, the branch displacement also needs to have the container plus packet location format. The branch address is then a modulo add with carry between the current instruction location and the relative displacement. Leading to the conclusion that instruction addresses and displacements need to be a distinct category or "type" from data addresses and offsets (which use whole binary numbers).

The problems with relative branches can be avoided by changing the layout
of the bundle. Instead of 20 contiguous bits that start on bit boundaries,
have six 16-bit instruction words starting on byte boundaries,
followed by six 4-bit fields in 3 bytes which extend those words,
followed by 1 byte with the start bits.

This means the address of the start of each instruction is byte aligned,
and the offset from an instruction to another is always in integer bytes.
And this is the same as RIP relative offsets to data.

The byte increment from instruction to instruction inside a bundle is 2,
except for the last instruction in slot[5] which is 6.
But this is just like a variable length instruction set except it is
addresses that end in 0xA that appear to be a longer format.

JimBrakefield <jim.brakefield@ieee.org> schrieb:

> The next thing needing discussion is relative branches. In order
> to avoid division by small odd numbers, the branch displacement
> also needs to have the container plus packet location format.

In principle, yes.

> The branch address is then a modulo add with carry between the
> current instruction location and the relative displacement.

No need for that.

I would envisage a relative branch as the difference between
bundles, plus three bits for the slot.

> Leading
> to the conclusion that instruction addresses and displacements need
> to be a distinct category or "type" from data addresses and offsets
> (which use whole binary numbers).

For four-byte instructions, the offset of a relative branch should
also be multiplied by four before adding to the PC.

On Friday, February 4, 2022 at 4:25:03 PM UTC-6, EricP wrote:
> JimBrakefield wrote:
> > On Wednesday, February 2, 2022 at 3:39:15 PM UTC-6, JimBrakefield wrote:
> >> On Wednesday, February 2, 2022 at 11:32:49 AM UTC-6, MitchAlsup wrote:
> >>> On Wednesday, February 2, 2022 at 11:04:44 AM UTC-6, Quadibloc wrote:
> >>>> On Wednesday, February 2, 2022 at 9:39:54 AM UTC-7, Stephen Fuld wrote:
> >>>>> And one
> >>>>> quibble; you may need the address of the next instruction in the bundle
> >>>>> to handle the case of the current instruction is a CALL type instruction
> >>>>> that puts the address of the next instruction in a register.
> >>> <
> >>>> That is true; if you can branch into the middle of a bundle, then presumably
> >>>> branches out with returns in the middle will be allowed. Here, though, I
> >>>> think the issue will be encoding rather than calculation. If a 128-bit bundle
> >>>> is divided into 20-bit packets, presumably packet n will be given an
> >>>> address aligned on 16-bit boundaries which will be...
> >>> <
> >>> I am surprised at you--you are making the mistake that control flow addressing
> >>> is identical to memory addressing--it is not (in this case). Instructions are located
> >>> on 20-bit boundaries, and whether or not an instruction starts in this container
> >>> is controlled by the header to the bundle. HW has no problem decoding to 20-bit
> >>> boundaries, so the only constraint is that the range in the LOBs of the IP is [0..5]
> >>> (instead of 0..7]) !!
> >>> <
> >>>> associated with one
> >>>> of the packets. The encoding scheme will presumably make those addresses
> >>>> consecutive, to simplify the calculation that needs to be done.
> >>>>
> >>>> John Savard
> >> Some comments:
> >> A) In the modern uP arch, instruction flow is separated from data flow.. Thus there is negligible hardware cost in having instruction granularity different from data granularity.
> >> B) Why use the remaining bits to re-sync the instruction addresses? E.g. why not have 21 bit instruction granularity instead of 20 bit? Re-sync to always occur at the start of 64 or 128 or 256-bit instruction block?
> >> C) Opens a new arena for uP architecture, eg instruction formats not tied to data granularity.
> >> D) Need a name for for the concept. Maybe there is already an ISA of this nature (other than stack machines with very short instructions)?
> >> E) Need yet another name for the concept of using some of the remaining instruction block bits for (usually) decode purposes?
> >
> > The next thing needing discussion is relative branches. In order to avoid division by small odd numbers, the branch displacement also needs to have the container plus packet location format. The branch address is then a modulo add with carry between the current instruction location and the relative displacement. Leading to the conclusion that instruction addresses and displacements need to be a distinct category or "type" from data addresses and offsets (which use whole binary numbers).
> The problems with relative branches can be avoided by changing the layout
> of the bundle. Instead of 20 contiguous bits that start on bit boundaries,
> have six 16-bit instruction words starting on byte boundaries,
> followed by six 4-bit fields in 3 bytes which extend those words,
> followed by 1 byte with the start bits.
>
> This means the address of the start of each instruction is byte aligned,
> and the offset from an instruction to another is always in integer bytes.
> And this is the same as RIP relative offsets to data.
>
> The byte increment from instruction to instruction inside a bundle is 2,
> except for the last instruction in slot[5] which is 6.
> But this is just like a variable length instruction set except it is
> addresses that end in 0xA that appear to be a longer format.

Slick, and not slick at the same time:
Avoids the distinction between instruction and data addresses ! (mostly)
Complicates (in a minor way) extraction of instructions.
Instruction address adder/incrementer still needs to skip over part of the instruction block or deal with variable instruction lengths?

Relative are dealt with by making the relative branch relative to the start of
the container the relative branch reside in.

So you do not branch based on the IP of the branch instruction, but the
address of the container. The 3-LoB of the relative are non-relative offset
into the targeted container.

Presto, simple in HW, only a bit complicated for SW.

JimBrakefield wrote:
> On Friday, February 4, 2022 at 4:25:03 PM UTC-6, EricP wrote:
>> JimBrakefield wrote:
>>> On Wednesday, February 2, 2022 at 3:39:15 PM UTC-6, JimBrakefield wrote:
>>>> On Wednesday, February 2, 2022 at 11:32:49 AM UTC-6, MitchAlsup wrote:
>>>>> On Wednesday, February 2, 2022 at 11:04:44 AM UTC-6, Quadibloc wrote:
>>>>>> On Wednesday, February 2, 2022 at 9:39:54 AM UTC-7, Stephen Fuld wrote:
>>>>>>> And one
>>>>>>> quibble; you may need the address of the next instruction in the bundle
>>>>>>> to handle the case of the current instruction is a CALL type instruction
>>>>>>> that puts the address of the next instruction in a register.
>>>>> <
>>>>>> That is true; if you can branch into the middle of a bundle, then presumably
>>>>>> branches out with returns in the middle will be allowed. Here, though, I
>>>>>> think the issue will be encoding rather than calculation. If a 128-bit bundle
>>>>>> is divided into 20-bit packets, presumably packet n will be given an
>>>>>> address aligned on 16-bit boundaries which will be...
>>>>> <
>>>>> I am surprised at you--you are making the mistake that control flow addressing
>>>>> is identical to memory addressing--it is not (in this case). Instructions are located
>>>>> on 20-bit boundaries, and whether or not an instruction starts in this container
>>>>> is controlled by the header to the bundle. HW has no problem decoding to 20-bit
>>>>> boundaries, so the only constraint is that the range in the LOBs of the IP is [0..5]
>>>>> (instead of 0..7]) !!
>>>>> <
>>>>>> associated with one
>>>>>> of the packets. The encoding scheme will presumably make those addresses
>>>>>> consecutive, to simplify the calculation that needs to be done.
>>>>>>
>>>>>> John Savard
>>>> Some comments:
>>>> A) In the modern uP arch, instruction flow is separated from data flow.. Thus there is negligible hardware cost in having instruction granularity different from data granularity.
>>>> B) Why use the remaining bits to re-sync the instruction addresses? E.g. why not have 21 bit instruction granularity instead of 20 bit? Re-sync to always occur at the start of 64 or 128 or 256-bit instruction block?
>>>> C) Opens a new arena for uP architecture, eg instruction formats not tied to data granularity.
>>>> D) Need a name for for the concept. Maybe there is already an ISA of this nature (other than stack machines with very short instructions)?
>>>> E) Need yet another name for the concept of using some of the remaining instruction block bits for (usually) decode purposes?
>>> The next thing needing discussion is relative branches. In order to avoid division by small odd numbers, the branch displacement also needs to have the container plus packet location format. The branch address is then a modulo add with carry between the current instruction location and the relative displacement. Leading to the conclusion that instruction addresses and displacements need to be a distinct category or "type" from data addresses and offsets (which use whole binary numbers).
>> The problems with relative branches can be avoided by changing the layout
>> of the bundle. Instead of 20 contiguous bits that start on bit boundaries,
>> have six 16-bit instruction words starting on byte boundaries,
>> followed by six 4-bit fields in 3 bytes which extend those words,
>> followed by 1 byte with the start bits.
>>
>> This means the address of the start of each instruction is byte aligned,
>> and the offset from an instruction to another is always in integer bytes.
>> And this is the same as RIP relative offsets to data.
>>
>> The byte increment from instruction to instruction inside a bundle is 2,
>> except for the last instruction in slot[5] which is 6.
>> But this is just like a variable length instruction set except it is
>> addresses that end in 0xA that appear to be a longer format.
>
> Slick, and not slick at the same time:

:-) It's a floor wax AND a dessert topping!

> Avoids the distinction between instruction and data addresses ! (mostly)
> Complicates (in a minor way) extraction of instructions.
> Instruction address adder/incrementer still needs to skip over part of the instruction block or deal with variable instruction lengths?

Instead of the decoder looking at an opcode to decide how much to
add to the RIP, it looks at the RIP address last hex digit.

The only place I can think of that might care how the RIP increment works
would be the linker since offsets are usually relative to the incremented
address so that offset=0 means the next sequential instruction.
Also for dynamic patching DLL linkages.

One could also make the offset relative to the branch instruction address.

MitchAlsup wrote:
> Relative are dealt with by making the relative branch relative to the start of
> the container the relative branch reside in.
>
> So you do not branch based on the IP of the branch instruction, but the
> address of the container. The 3-LoB of the relative are non-relative offset
> into the targeted container.
>
> Presto, simple in HW, only a bit complicated for SW.

I thought of that but is makes offsets for instructions different
from offsets for data.

inst_offset = ((dest_addr & (~7)) - (branch_addr & (~7))) | (dest_addr & 7)

which makes the instruction offset calculation non-commutative arithmetic
so that ((a + b) - b) != a
and I was concerned that might cause other problems.

EricP wrote:
> JimBrakefield wrote:
>> On Wednesday, February 2, 2022 at 3:39:15 PM UTC-6, JimBrakefield wrote:
>>> On Wednesday, February 2, 2022 at 11:32:49 AM UTC-6, MitchAlsup wrote:
>>>> On Wednesday, February 2, 2022 at 11:04:44 AM UTC-6, Quadibloc wrote:
>>>>> On Wednesday, February 2, 2022 at 9:39:54 AM UTC-7, Stephen Fuld
>>>>> wrote:
>>>>>> And one quibble; you may need the address of the next instruction
>>>>>> in the bundle to handle the case of the current instruction is a
>>>>>> CALL type instruction that puts the address of the next
>>>>>> instruction in a register.
>>>> <
>>>>> That is true; if you can branch into the middle of a bundle, then
>>>>> presumably branches out with returns in the middle will be allowed.
>>>>> Here, though, I think the issue will be encoding rather than
>>>>> calculation. If a 128-bit bundle is divided into 20-bit packets,
>>>>> presumably packet n will be given an address aligned on 16-bit
>>>>> boundaries which will be...
>>>> < I am surprised at you--you are making the mistake that control
>>>> flow addressing is identical to memory addressing--it is not (in
>>>> this case). Instructions are located on 20-bit boundaries, and
>>>> whether or not an instruction starts in this container is controlled
>>>> by the header to the bundle. HW has no problem decoding to 20-bit
>>>> boundaries, so the only constraint is that the range in the LOBs of
>>>> the IP is [0..5] (instead of 0..7]) !! <
>>>>> associated with one of the packets. The encoding scheme will
>>>>> presumably make those addresses consecutive, to simplify the
>>>>> calculation that needs to be done.
>>>>> John Savard
>>> Some comments: A) In the modern uP arch, instruction flow is
>>> separated from data flow. Thus there is negligible hardware cost in
>>> having instruction granularity different from data granularity. B)
>>> Why use the remaining bits to re-sync the instruction addresses? E.g.
>>> why not have 21 bit instruction granularity instead of 20 bit?
>>> Re-sync to always occur at the start of 64 or 128 or 256-bit
>>> instruction block? C) Opens a new arena for uP architecture, eg
>>> instruction formats not tied to data granularity. D) Need a name for
>>> for the concept. Maybe there is already an ISA of this nature (other
>>> than stack machines with very short instructions)? E) Need yet
>>> another name for the concept of using some of the remaining
>>> instruction block bits for (usually) decode purposes?
>>
>> The next thing needing discussion is relative branches. In order to
>> avoid division by small odd numbers, the branch displacement also
>> needs to have the container plus packet location format. The branch
>> address is then a modulo add with carry between the current
>> instruction location and the relative displacement. Leading to the
>> conclusion that instruction addresses and displacements need to be a
>> distinct category or "type" from data addresses and offsets (which use
>> whole binary numbers).
>
> The problems with relative branches can be avoided by changing the layout
> of the bundle. Instead of 20 contiguous bits that start on bit boundaries,
> have six 16-bit instruction words starting on byte boundaries,
> followed by six 4-bit fields in 3 bytes which extend those words,
> followed by 1 byte with the start bits.
>
> This means the address of the start of each instruction is byte aligned,
> and the offset from an instruction to another is always in integer bytes.
> And this is the same as RIP relative offsets to data.
>
> The byte increment from instruction to instruction inside a bundle is 2,
> except for the last instruction in slot[5] which is 6.
> But this is just like a variable length instruction set except it is
> addresses that end in 0xA that appear to be a longer format.

Or how about this...

The bundle is an aligned 16 byte packet so the high 60 bits are the
bundle number and low 4 bits are the internal byte offset.

When reading or writing bundle bytes we use the normal 64 bit address.

When executing instructions the RIP address has the same high 60 bit
bundle address and the low 4 bits denotes the instruction.
However we pretend that the 6 instructions start at bytes 0..5
and values in the range 6..15 are an illegal instruction trap.
We completely ignore the internal structure of the bundle
and leave that up to the decoder to sort out.
Its as though a bundle consists of five 1-byte and one 11-byte instructions.

That leaves RIP addresses and branch offset as normal 64-bit integers,
all the arithmetic is normal and there is no field masking or shifting.

This probably should have some test scenarios... I can see that having
the instruction size appear to change based on its address might have
some unexpected consequences.
Things to test like how compiler generates conditional branches, linker,
maybe see how one would generate a trampoline on the stack,
calculate the address into a register, and branch to that register address.

EricP <ThatWouldBeTelling@thevillage.com> schrieb:
> Or how about this...
>
> The bundle is an aligned 16 byte packet so the high 60 bits are the
> bundle number and low 4 bits are the internal byte offset.
>
> When reading or writing bundle bytes we use the normal 64 bit address.
>
> When executing instructions the RIP address has the same high 60 bit
> bundle address and the low 4 bits denotes the instruction.
> However we pretend that the 6 instructions start at bytes 0..5
> and values in the range 6..15 are an illegal instruction trap.
> We completely ignore the internal structure of the bundle
> and leave that up to the decoder to sort out.
> Its as though a bundle consists of five 1-byte and one 11-byte instructions.

> That leaves RIP addresses and branch offset as normal 64-bit integers,
> all the arithmetic is normal and there is no field masking or shifting.

The question is what to do on a branch without wasting entropy.
I think that scheme would waste one bit of entropy if you also wanted
to calculate reltive branches.

If you want to use "normal" address arithmetic, it would probably
be better to pretend that the instructions start at a two-byte
boundary and shift relative offsets by one (same as you would
in an instruction set with a minimum 16-bit instruction size).

> This probably should have some test scenarios... I can see that having
> the instruction size appear to change based on its address might have
> some unexpected consequences.
> Things to test like how compiler generates conditional branches, linker,
> maybe see how one would generate a trampoline on the stack,
> calculate the address into a register, and branch to that register address.

If you want to have a trampoline, you can prescribe that it is
always aligned to a 128-bit boundary. Set the bits so that
jumping to the start would be allowed, but not jumping into
the middle.

On Sunday, February 6, 2022 at 3:23:11 AM UTC-6, Thomas Koenig wrote:
> EricP <ThatWould...@thevillage.com> schrieb:
> > Or how about this...
> >
> > The bundle is an aligned 16 byte packet so the high 60 bits are the
> > bundle number and low 4 bits are the internal byte offset.
> >
> > When reading or writing bundle bytes we use the normal 64 bit address.
> >
> > When executing instructions the RIP address has the same high 60 bit
> > bundle address and the low 4 bits denotes the instruction.
> > However we pretend that the 6 instructions start at bytes 0..5
> > and values in the range 6..15 are an illegal instruction trap.
> > We completely ignore the internal structure of the bundle
> > and leave that up to the decoder to sort out.
> > Its as though a bundle consists of five 1-byte and one 11-byte instructions.
>
> > That leaves RIP addresses and branch offset as normal 64-bit integers,
> > all the arithmetic is normal and there is no field masking or shifting.
> The question is what to do on a branch without wasting entropy.
> I think that scheme would waste one bit of entropy if you also wanted
> to calculate reltive branches.
<
Most RISC machines are already wasting 2-bits of entropy--the bits addressing
Bytes and HalfWords. Nobody seems to care.
>
> If you want to use "normal" address arithmetic, it would probably
> be better to pretend that the instructions start at a two-byte
> boundary and shift relative offsets by one (same as you would
> in an instruction set with a minimum 16-bit instruction size).
<
Since this is HW, you could always define the 20-bit containers comprising
2 fields: a 16-bit container having the more important 16-bits of the inst
and starting at Halfword boundary, and a 4-bit extension starting at the
last Word, and indexed by the same index the 16-bit part of the container
just at 4-bit size. This would be horrible for SW, and trivial for HW. But
here, all instructions start on 16-bit boundaries!
<
I hate it (and so would assemblers and linkers and JITs), but it can be made
to work. It is, however, unnecessary.
<
> > This probably should have some test scenarios... I can see that having
> > the instruction size appear to change based on its address might have
> > some unexpected consequences.
> > Things to test like how compiler generates conditional branches, linker,
> > maybe see how one would generate a trampoline on the stack,
> > calculate the address into a register, and branch to that register address.
> If you want to have a trampoline, you can prescribe that it is
> always aligned to a 128-bit boundary. Set the bits so that
> jumping to the start would be allowed, but not jumping into
> the middle.
<
All entry points should be container aligned.

I looked a bit at what to include in the 20-bit instruction subset.

Looking at the biggest piece of bloat^H^H^H^H^Hsoftware I can find
on POWER, chromium plus supporting shared libraries, a bit more
than 58 million instructions, I found the following instruction
frequency. The first column is the instruction, the second the
number of instructions, the third one percentage, and the fourth
one culminative percentage. The frequency will probably surprise
no one here:

ld 5837117 11.55 11.55 (load 64-bit with offset)
mr 5590458 11.06 22.61 (move register)
addi 4750662 9.40 32.00 (add with 16-bit constant)
std 3739464 7.40 39.40 (store 64-bit with offset)
bl 3390274 6.71 46.11 (branch and link)
li 2486296 4.92 51.03 (load immediate)
addis 1668924 3.30 54.33 (add immediate and shift)
b 1534024 3.03 57.36 (branch)
beq 1507796 2.98 60.34 (branch if equal)
add 1266393 2.51 62.85 (add)
cmpdi 1009923 2.00 64.85 (compare immediate)
ori 822801 1.63 66.48 (or immedaite)
lwz 810375 1.60 68.08 (load word and zero)
bne 799486 1.58 69.66 (branch if not equal)
stdu 691161 1.37 71.03 (store double with update)
stw 690701 1.37 72.39 (store word)
cmpwi 642714 1.27 73.66 (compare word immediate)
mflr 587134 1.16 74.83 (move from link register)
lbz 472965 0.94 75.76 (load byte zero)
extsw 465193 0.92 76.68 (extend sign)
subf 435575 0.86 77.54 (subtract)
sldi 370387 0.73 78.28 (shift left)
blr 358973 0.71 78.99 (branch and link)
mtctr 350664 0.69 79.68 (move to counter register)
rlwinm 327689 0.65 80.33 (word shifting)
stb 326003 0.64 80.97 (store byte with offset)

Not all offsets would fit into a 20-bit container, of course.
Looking at an instruction format consisting of

- one four-bit opcode
- two five-bit registers
- one six-bit constant

it would be possible to fit (original data too long to post
here)

ld 9.72
addi 2.26
std 6.50
li 3.87
cmpdi 1.30
lwz 1.02
sldi 0.62

into that format, close to 25,3% of instructions.

For a two or three-register format,

mr 11.06
add 2.51
extw 0.92
subf 0.86

would give 15,3% on top.

For branches, I would say that 5 bit of POWER offset would correspond
to 6 bits of the combined address, which would give a percent or two.
So 40% of half-length instructions sounds reasonable.

In other words: Recoding POWER into 20 and 40 bit chunks without
using any of the additional freedom gained by 40-bit instructions
would actually be a gain in code density, without any restrictions
in what registers to choose (such as having special instructions
for the stack pointer).

Trying to compress this into 16 bits would be much more difficult.

On 2/8/2022 3:54 PM, Thomas Koenig wrote:
> I looked a bit at what to include in the 20-bit instruction subset.
>
> Looking at the biggest piece of bloat^H^H^H^H^Hsoftware I can find
> on POWER, chromium plus supporting shared libraries, a bit more
> than 58 million instructions, I found the following instruction
> frequency. The first column is the instruction, the second the
> number of instructions, the third one percentage, and the fourth
> one culminative percentage. The frequency will probably surprise
> no one here:
>
> ld 5837117 11.55 11.55 (load 64-bit with offset)
> mr 5590458 11.06 22.61 (move register)
> addi 4750662 9.40 32.00 (add with 16-bit constant)
> std 3739464 7.40 39.40 (store 64-bit with offset)
> bl 3390274 6.71 46.11 (branch and link)
> li 2486296 4.92 51.03 (load immediate)
> addis 1668924 3.30 54.33 (add immediate and shift)
> b 1534024 3.03 57.36 (branch)
> beq 1507796 2.98 60.34 (branch if equal)
> add 1266393 2.51 62.85 (add)
> cmpdi 1009923 2.00 64.85 (compare immediate)
> ori 822801 1.63 66.48 (or immedaite)
> lwz 810375 1.60 68.08 (load word and zero)
> bne 799486 1.58 69.66 (branch if not equal)
> stdu 691161 1.37 71.03 (store double with update)
> stw 690701 1.37 72.39 (store word)
> cmpwi 642714 1.27 73.66 (compare word immediate)
> mflr 587134 1.16 74.83 (move from link register)
> lbz 472965 0.94 75.76 (load byte zero)
> extsw 465193 0.92 76.68 (extend sign)
> subf 435575 0.86 77.54 (subtract)
> sldi 370387 0.73 78.28 (shift left)
> blr 358973 0.71 78.99 (branch and link)
> mtctr 350664 0.69 79.68 (move to counter register)
> rlwinm 327689 0.65 80.33 (word shifting)
> stb 326003 0.64 80.97 (store byte with offset)
>
> Not all offsets would fit into a 20-bit container, of course.
> Looking at an instruction format consisting of
>
> - one four-bit opcode
> - two five-bit registers
> - one six-bit constant
>
> it would be possible to fit (original data too long to post
> here)
>
> ld 9.72
> addi 2.26
> std 6.50
> li 3.87
> cmpdi 1.30
> lwz 1.02
> sldi 0.62
>
> into that format, close to 25,3% of instructions.
>
> For a two or three-register format,
>
> mr 11.06
> add 2.51
> extw 0.92
> subf 0.86
>
> would give 15,3% on top.
>
> For branches, I would say that 5 bit of POWER offset would correspond
> to 6 bits of the combined address, which would give a percent or two.
> So 40% of half-length instructions sounds reasonable.
>
> In other words: Recoding POWER into 20 and 40 bit chunks without
> using any of the additional freedom gained by 40-bit instructions
> would actually be a gain in code density, without any restrictions
> in what registers to choose (such as having special instructions
> for the stack pointer).
>
> Trying to compress this into 16 bits would be much more difficult.

A decent chunk of the common instructions can be crammed into 16-bit
encodings on BJX2, sorta...

But, yeah, the overall rankings in my case seem to be vaguely similar.

Top ranking instructions from Doom (aggregated by mnemonic):
MOV.Q (Load/Store QWord)
MOV.L (Load/Store DWord)
BF (Branch if False)
MOVU.L (Load, Unsigned DWord)
BT (Branch if True)
MOVU.B (Load, Unsigned Byte)
MOV (Move Reg, Reg)
MOVU.W (Load, Unsigned Word)
MOV.W (Load/Store, Word)
ADD (Add, 64-bit)
TST (Bit Test, ((A&B)==0))
BRA (Unconditional Branch)
ADDS.L (Add, 32-bit, Sign-Extending)
MOV.X (Load/Store, 128-bit)
SHLD (Logical Shift, 32-bit)
OR (Bitwise OR)
CMPQGT (Compare Greater, 64-bit)
LDIZ (Load Immediate, Zero-Extended)
...

Or, aggregating by category:
Load/Store ops
Branch Ops
Common ALU ops

Within 16-bit encodings, the bulk of the most commonly encoded:
MOV (Reg, Reg)
Branch ops (Disp8)
ADD (Imm8, Reg)
LDI (Imm12, R0)
LDI (Imm8, Reg)
Load/Store with (SP, Disp4), Various
CMPEQ (Imm4, Rn)

Within 32-bit encodings:
Branch Ops (Disp20)
Load/Store Ops (Disp9)
ALU Ops (Rm, Imm9, Rn)
LDI/ADD (Imm16, Rn)
...

There is much less of a showing for Load/Store with a non-SP base
register in 16-bit land, but the likely reason here is there is a very
limited selection of displacement encodings (these encodings are very
common in terms of 32-bit encodings).

Say, for example, one wants:
4b Base Register
4b Dest Register
3b Disp
3b Format

Then, one is already looking at 14 bits of encoding space.

Could in theory cram it down to 12 bits of encoding space by using 3-bit
register fields, but this would be somewhat limiting.

This can fit a little better into a 24-bit encoding, but in a past
experiment, the savings from 24-bit Load/Store encodings and similar
were overall fairly modest vs plain 16/32.

In the current form of the ISA, the encoding space that was originally
assigned for 24-bit encodings was reused for the XGPR encodings (Namely,
32-bit instruction encodings with 6-bit register fields, covering a
"common" ISA subset; with cases which don't fit into the 32-bit encoding
falling back to a 64-bit instruction format, which while not necessarily
the most efficient possibility, this is rare enough that it doesn't
really matter).

But, in general, a 20 or 24 bit encoding could potentially be able to
fit a better range of Load/Store encodings, which could potentially be
worthwhile (though, in this case, I would probably go for a byte-aligned
16/24/32 encoding, rather than a bundle-based 20/40 encoding).

....

BGB <cr88192@gmail.com> wrote:
> On 2/8/2022 3:54 PM, Thomas Koenig wrote:
>> I looked a bit at what to include in the 20-bit instruction subset.
>>
>> Looking at the biggest piece of bloat^H^H^H^H^Hsoftware I can find
>> on POWER, chromium plus supporting shared libraries, a bit more
>> than 58 million instructions, I found the following instruction
>> frequency. The first column is the instruction, the second the
>> number of instructions, the third one percentage, and the fourth
>> one culminative percentage. The frequency will probably surprise
>> no one here:
>>
>> ld 5837117 11.55 11.55 (load 64-bit with offset)
>> mr 5590458 11.06 22.61 (move register)
>> addi 4750662 9.40 32.00 (add with 16-bit constant)
>> std 3739464 7.40 39.40 (store 64-bit with offset)
>> bl 3390274 6.71 46.11 (branch and link)
>> li 2486296 4.92 51.03 (load immediate)
>> addis 1668924 3.30 54.33 (add immediate and shift)
>> b 1534024 3.03 57.36 (branch)
>> beq 1507796 2.98 60.34 (branch if equal)
>> add 1266393 2.51 62.85 (add)
>> cmpdi 1009923 2.00 64.85 (compare immediate)
>> ori 822801 1.63 66.48 (or immedaite)
>> lwz 810375 1.60 68.08 (load word and zero)
>> bne 799486 1.58 69.66 (branch if not equal)
>> stdu 691161 1.37 71.03 (store double with update)
>> stw 690701 1.37 72.39 (store word)
>> cmpwi 642714 1.27 73.66 (compare word immediate)
>> mflr 587134 1.16 74.83 (move from link register)
>> lbz 472965 0.94 75.76 (load byte zero)
>> extsw 465193 0.92 76.68 (extend sign)
>> subf 435575 0.86 77.54 (subtract)
>> sldi 370387 0.73 78.28 (shift left)
>> blr 358973 0.71 78.99 (branch and link)
>> mtctr 350664 0.69 79.68 (move to counter register)
>> rlwinm 327689 0.65 80.33 (word shifting)
>> stb 326003 0.64 80.97 (store byte with offset)
>>
>> Not all offsets would fit into a 20-bit container, of course.
>> Looking at an instruction format consisting of
>>
>> - one four-bit opcode
>> - two five-bit registers
>> - one six-bit constant
>>
>> it would be possible to fit (original data too long to post
>> here)
>>
>> ld 9.72
>> addi 2.26
>> std 6.50
>> li 3.87
>> cmpdi 1.30
>> lwz 1.02
>> sldi 0.62
>>
>> into that format, close to 25,3% of instructions.
>>
>> For a two or three-register format,
>>
>> mr 11.06
>> add 2.51
>> extw 0.92
>> subf 0.86
>>
>> would give 15,3% on top.
>>
>> For branches, I would say that 5 bit of POWER offset would correspond
>> to 6 bits of the combined address, which would give a percent or two.
>> So 40% of half-length instructions sounds reasonable.
>>
>> In other words: Recoding POWER into 20 and 40 bit chunks without
>> using any of the additional freedom gained by 40-bit instructions
>> would actually be a gain in code density, without any restrictions
>> in what registers to choose (such as having special instructions
>> for the stack pointer).
>>
>> Trying to compress this into 16 bits would be much more difficult.
>
> A decent chunk of the common instructions can be crammed into 16-bit
> encodings on BJX2, sorta...
>
> But, yeah, the overall rankings in my case seem to be vaguely similar.
>
>
> Top ranking instructions from Doom (aggregated by mnemonic):
> MOV.Q (Load/Store QWord)
> MOV.L (Load/Store DWord)
> BF (Branch if False)
> MOVU.L (Load, Unsigned DWord)
> BT (Branch if True)
> MOVU.B (Load, Unsigned Byte)
> MOV (Move Reg, Reg)
> MOVU.W (Load, Unsigned Word)
> MOV.W (Load/Store, Word)
> ADD (Add, 64-bit)
> TST (Bit Test, ((A&B)==0))
> BRA (Unconditional Branch)
> ADDS.L (Add, 32-bit, Sign-Extending)
> MOV.X (Load/Store, 128-bit)
> SHLD (Logical Shift, 32-bit)
> OR (Bitwise OR)
> CMPQGT (Compare Greater, 64-bit)
> LDIZ (Load Immediate, Zero-Extended)
> ...
>
> Or, aggregating by category:
> Load/Store ops
> Branch Ops
> Common ALU ops
>
>
> Within 16-bit encodings, the bulk of the most commonly encoded:
> MOV (Reg, Reg)
> Branch ops (Disp8)
> ADD (Imm8, Reg)
> LDI (Imm12, R0)
> LDI (Imm8, Reg)
> Load/Store with (SP, Disp4), Various
> CMPEQ (Imm4, Rn)
>
> Within 32-bit encodings:
> Branch Ops (Disp20)
> Load/Store Ops (Disp9)
> ALU Ops (Rm, Imm9, Rn)
> LDI/ADD (Imm16, Rn)
> ...
>
>
> There is much less of a showing for Load/Store with a non-SP base
> register in 16-bit land, but the likely reason here is there is a very
> limited selection of displacement encodings (these encodings are very
> common in terms of 32-bit encodings).
>
> Say, for example, one wants:
> 4b Base Register
> 4b Dest Register
> 3b Disp
> 3b Format
>
> Then, one is already looking at 14 bits of encoding space.
>
> Could in theory cram it down to 12 bits of encoding space by using 3-bit
> register fields, but this would be somewhat limiting.

If you do preferred split non-overlapping address-data registers like short
form 8086 then 16 bits is plenty. Only long form needs access to all
registers.

This is before you add a short belt, which cuts instruction sizes more.

> This can fit a little better into a 24-bit encoding, but in a past
> experiment, the savings from 24-bit Load/Store encodings and similar
> were overall fairly modest vs plain 16/32.
>
> In the current form of the ISA, the encoding space that was originally
> assigned for 24-bit encodings was reused for the XGPR encodings (Namely,
> 32-bit instruction encodings with 6-bit register fields, covering a
> "common" ISA subset; with cases which don't fit into the 32-bit encoding
> falling back to a 64-bit instruction format, which while not necessarily
> the most efficient possibility, this is rare enough that it doesn't
> really matter).
>
> But, in general, a 20 or 24 bit encoding could potentially be able to
> fit a better range of Load/Store encodings, which could potentially be
> worthwhile (though, in this case, I would probably go for a byte-aligned
> 16/24/32 encoding, rather than a bundle-based 20/40 encoding).

On 2/8/2022 1:54 PM, Thomas Koenig wrote:
> I looked a bit at what to include in the 20-bit instruction subset.
>
> Looking at the biggest piece of bloat^H^H^H^H^Hsoftware I can find
> on POWER, chromium plus supporting shared libraries, a bit more
> than 58 million instructions, I found the following instruction
> frequency. The first column is the instruction, the second the
> number of instructions, the third one percentage, and the fourth
> one culminative percentage. The frequency will probably surprise
> no one here:
>
> ld 5837117 11.55 11.55 (load 64-bit with offset)
> mr 5590458 11.06 22.61 (move register)
> addi 4750662 9.40 32.00 (add with 16-bit constant)
> std 3739464 7.40 39.40 (store 64-bit with offset)
> bl 3390274 6.71 46.11 (branch and link)
> li 2486296 4.92 51.03 (load immediate)
> addis 1668924 3.30 54.33 (add immediate and shift)
> b 1534024 3.03 57.36 (branch)
> beq 1507796 2.98 60.34 (branch if equal)
> add 1266393 2.51 62.85 (add)
> cmpdi 1009923 2.00 64.85 (compare immediate)
> ori 822801 1.63 66.48 (or immedaite)
> lwz 810375 1.60 68.08 (load word and zero)
> bne 799486 1.58 69.66 (branch if not equal)
> stdu 691161 1.37 71.03 (store double with update)
> stw 690701 1.37 72.39 (store word)
> cmpwi 642714 1.27 73.66 (compare word immediate)
> mflr 587134 1.16 74.83 (move from link register)
> lbz 472965 0.94 75.76 (load byte zero)
> extsw 465193 0.92 76.68 (extend sign)
> subf 435575 0.86 77.54 (subtract)
> sldi 370387 0.73 78.28 (shift left)
> blr 358973 0.71 78.99 (branch and link)
> mtctr 350664 0.69 79.68 (move to counter register)
> rlwinm 327689 0.65 80.33 (word shifting)
> stb 326003 0.64 80.97 (store byte with offset)
>
> Not all offsets would fit into a 20-bit container, of course.
> Looking at an instruction format consisting of
>
> - one four-bit opcode
> - two five-bit registers
> - one six-bit constant
>
> it would be possible to fit (original data too long to post
> here)
>
> ld 9.72
> addi 2.26
> std 6.50
> li 3.87
> cmpdi 1.30
> lwz 1.02
> sldi 0.62
>
> into that format, close to 25,3% of instructions.
>
> For a two or three-register format,
>
> mr 11.06
> add 2.51
> extw 0.92
> subf 0.86
>
> would give 15,3% on top.
>
> For branches, I would say that 5 bit of POWER offset would correspond
> to 6 bits of the combined address, which would give a percent or two.
> So 40% of half-length instructions sounds reasonable.
>
> In other words: Recoding POWER into 20 and 40 bit chunks without
> using any of the additional freedom gained by 40-bit instructions
> would actually be a gain in code density, without any restrictions
> in what registers to choose (such as having special instructions
> for the stack pointer).

I am probably missing something, but using your 40% figure

(.4 * 20) + (.6 * 40) = 8 + 24 = 32

Then you have to add say on average one bit per instruction for the 8
bit overhead.

So ISTM that at best, you break even on code density, and probably lose
a small amount.

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

Stephen Fuld <sfuld@alumni.cmu.edu.invalid> schrieb:
> On 2/8/2022 1:54 PM, Thomas Koenig wrote:
>> I looked a bit at what to include in the 20-bit instruction subset.
>>
>> Looking at the biggest piece of bloat^H^H^H^H^Hsoftware I can find
>> on POWER, chromium plus supporting shared libraries, a bit more
>> than 58 million instructions, I found the following instruction
>> frequency. The first column is the instruction, the second the
>> number of instructions, the third one percentage, and the fourth
>> one culminative percentage. The frequency will probably surprise
>> no one here:
>>
>> ld 5837117 11.55 11.55 (load 64-bit with offset)
>> mr 5590458 11.06 22.61 (move register)
>> addi 4750662 9.40 32.00 (add with 16-bit constant)
>> std 3739464 7.40 39.40 (store 64-bit with offset)
>> bl 3390274 6.71 46.11 (branch and link)
>> li 2486296 4.92 51.03 (load immediate)
>> addis 1668924 3.30 54.33 (add immediate and shift)
>> b 1534024 3.03 57.36 (branch)
>> beq 1507796 2.98 60.34 (branch if equal)
>> add 1266393 2.51 62.85 (add)
>> cmpdi 1009923 2.00 64.85 (compare immediate)
>> ori 822801 1.63 66.48 (or immedaite)
>> lwz 810375 1.60 68.08 (load word and zero)
>> bne 799486 1.58 69.66 (branch if not equal)
>> stdu 691161 1.37 71.03 (store double with update)
>> stw 690701 1.37 72.39 (store word)
>> cmpwi 642714 1.27 73.66 (compare word immediate)
>> mflr 587134 1.16 74.83 (move from link register)
>> lbz 472965 0.94 75.76 (load byte zero)
>> extsw 465193 0.92 76.68 (extend sign)
>> subf 435575 0.86 77.54 (subtract)
>> sldi 370387 0.73 78.28 (shift left)
>> blr 358973 0.71 78.99 (branch and link)
>> mtctr 350664 0.69 79.68 (move to counter register)
>> rlwinm 327689 0.65 80.33 (word shifting)
>> stb 326003 0.64 80.97 (store byte with offset)
>>
>> Not all offsets would fit into a 20-bit container, of course.
>> Looking at an instruction format consisting of
>>
>> - one four-bit opcode
>> - two five-bit registers
>> - one six-bit constant
>>
>> it would be possible to fit (original data too long to post
>> here)
>>
>> ld 9.72
>> addi 2.26
>> std 6.50
>> li 3.87
>> cmpdi 1.30
>> lwz 1.02
>> sldi 0.62
>>
>> into that format, close to 25,3% of instructions.
>>
>> For a two or three-register format,
>>
>> mr 11.06
>> add 2.51
>> extw 0.92
>> subf 0.86
>>
>> would give 15,3% on top.
>>
>> For branches, I would say that 5 bit of POWER offset would correspond
>> to 6 bits of the combined address, which would give a percent or two.
>> So 40% of half-length instructions sounds reasonable.
>>
>> In other words: Recoding POWER into 20 and 40 bit chunks without
>> using any of the additional freedom gained by 40-bit instructions
>> would actually be a gain in code density, without any restrictions
>> in what registers to choose (such as having special instructions
>> for the stack pointer).
>
> I am probably missing something, but using your 40% figure
>
> (.4 * 20) + (.6 * 40) = 8 + 24 = 32

Density is the number of instructions per unit, you have to
add the inverse of the number of bits.

1/(0.4 / 20 + 0.6 / 40) = 1/ (0.02 + 0.015) = 28.57...

(Same as when calculating an avarage density of a mixture).

On 2/8/2022 11:09 PM, Stephen Fuld wrote:
> On 2/8/2022 1:54 PM, Thomas Koenig wrote:
>> I looked a bit at what to include in the 20-bit instruction subset.
>>
>> Looking at the biggest piece of bloat^H^H^H^H^Hsoftware I can find
>> on POWER, chromium plus supporting shared libraries, a bit more
>> than 58 million instructions, I found the following instruction
>> frequency.  The first column is the instruction, the second the
>> number of instructions, the third one percentage, and the fourth
>> one culminative percentage.  The frequency will probably surprise
>> no one here:
>>
>> ld      5837117  11.55   11.55  (load 64-bit with offset)
>> mr      5590458  11.06   22.61  (move register)
>> addi    4750662   9.40   32.00  (add with 16-bit constant)
>> std     3739464   7.40   39.40  (store 64-bit with offset)
>> bl      3390274   6.71   46.11  (branch and link)
>> li      2486296   4.92   51.03  (load immediate)
>> addis   1668924   3.30   54.33  (add immediate and shift)
>> b       1534024   3.03   57.36  (branch)
>> beq     1507796   2.98   60.34  (branch if equal)
>> add     1266393   2.51   62.85  (add)
>> cmpdi   1009923   2.00   64.85  (compare immediate)
>> ori     822801    1.63   66.48  (or immedaite)
>> lwz     810375    1.60   68.08  (load word and zero)
>> bne     799486    1.58   69.66  (branch if not equal)
>> stdu    691161    1.37   71.03  (store double with update)
>> stw     690701    1.37   72.39  (store word)
>> cmpwi   642714    1.27   73.66  (compare word immediate)
>> mflr    587134    1.16   74.83  (move from link register)
>> lbz     472965    0.94   75.76  (load byte zero)
>> extsw   465193    0.92   76.68  (extend sign)
>> subf    435575    0.86   77.54  (subtract)
>> sldi    370387    0.73   78.28  (shift left)
>> blr     358973    0.71   78.99  (branch and link)
>> mtctr   350664    0.69   79.68  (move to counter register)
>> rlwinm  327689    0.65   80.33  (word shifting)
>> stb     326003    0.64   80.97  (store byte with offset)
>>
>> Not all offsets would fit into a 20-bit container, of course.
>> Looking at an instruction format consisting of
>>
>> - one four-bit opcode
>> - two five-bit registers
>> - one six-bit constant
>>
>> it would be possible to fit (original data too long to post
>> here)
>>
>> ld    9.72
>> addi  2.26
>> std   6.50
>> li    3.87
>> cmpdi 1.30
>> lwz   1.02
>> sldi  0.62
>>
>> into that format, close to 25,3% of instructions.
>>
>> For a two or three-register format,
>>
>> mr   11.06
>> add   2.51
>> extw  0.92
>> subf  0.86
>>
>> would give 15,3% on top.
>>
>> For branches, I would say that 5 bit of POWER offset would correspond
>> to 6 bits of the combined address, which would give a percent or two.
>> So 40% of half-length instructions sounds reasonable.
>>
>> In other words: Recoding POWER into 20 and 40 bit chunks without
>> using any of the additional freedom gained by 40-bit instructions
>> would actually be a gain in code density, without any restrictions
>> in what registers to choose (such as having special instructions
>> for the stack pointer).
>
> I am probably missing something, but using your 40% figure
>
>     (.4 * 20) + (.6 * 40) = 8 + 24 = 32
>
> Then you have to add say on average one bit per instruction for the 8
> bit overhead.
>
> So ISTM that at best, you break even on code density, and probably lose
> a small amount.
>

I suspect that in the average case, an ISA with 16/24/32 instructions
could probably beat one with a 20/40 encoding in terms of code-density.

So, trying to come up with something that loosely organizes instruction
encodings by probability...

Say, for example, we had an ISA like:
32x GPRs;
16/24/32 bit instructions;
Smaller encodings may use 4-bit registers in some forms.

So, length encoded in bits 2:0 of the first byte, transposed here:
0..7: 16-bit
8..B: 24-bit
C..F: 32-bit

Or:
ZZZZ-mmmm-nnnn-ZZZ0 (2R, 16b, typical)
Znmt-ZZZZ-tttt-ssss-nnnn-ZZ01 (3R, 24b, typical)
ZZZZ-ZZZZ-Znmt-ZZZZ-tttt-ssss-nnnn-ZZ11 (3R, 32b, typical)

ZZZZ-mmmm-nnnn-ZZZ0 (2R, 16b, typical)

Within 16b space:
0SSS-mmmm-nnnn-0000 Store (Rm, 0)
1SSS-mmmm-nnnn-0000 Load (Rm, 0)
0SSS-dddd-nnnn-0010 Store (SP, Disp4)
1SSS-dddd-nnnn-0010 Load (SP, Disp4)

SSS: 000=SB, 001=SW, 010=SL, 011=Q, 100=UB, 101=UW, 110=UL, 111=X

ZZZZ-mmmm-nnnn-0100 ALU Ops (Rm, Rn)
ZZZZ-mmmm-nnnn-0110 ALU Ops (Imm4u, Rn)
0000=ADD, 0001=SUB, 0010=ADDL, 0011=SUBL
0100=TST, 0101=AND, 0110=OR , 0111=XOR
1000=MOV, 1001=MOV, 1010=MOV, 1011=MOV (5-bit Reg)
1100=CMPEQ, 1101=CMPGT
1110=SHAD, 1111=SHLD

ADDL/SUBL=ADD/SUB with 32-bit sign extension.
SHAD/SHLD=Shift

ZZZn-ZZZZ-nnnn-1000 1R Ops (5-bit register)
ZZZZ-ZZZZ-ZZZZ-1010 0R Ops
dddd-dddd-dd00-1100 BRA Disp10s (+/- 512B)
dddd-dddd-dd01-1100 BSR Disp10s
dddd-dddd-dd10-1100 BT Disp10s
dddd-dddd-dd11-1100 BF Disp10s
dddd-dddd-dd00-1110 ADD Disp10u, SP
dddd-dddd-dd01-1110 ADD Disp10n, SP

Within 24b space:
0nmd-0SSS-dddd-mmmm-nnnn-0001 Store (Disp5)
1nmi-0SSS-iiii-mmmm-nnnn-0001 Store (Index)
0nmd-1SSS-dddd-mmmm-nnnn-0001 Load (Disp5)
1nmi-1SSS-iiii-mmmm-nnnn-0001 Load (Index)
0nmt-ZZZZ-tttt-ssss-nnnn-0101 ALU (3R)
1nmi-ZZZZ-iiii-ssss-nnnn-0101 ALU (3RI, Imm5)
...

0nmZ-ZZZZ-ZZZZ-mmmm-nnnn-1001 2R Space
1nmZ-ZZdd-dddd-mmmm-nnnn-1001 -

0ndd-0000-dddd-dddd-nnnn-1101 ADD Imm10u, Rn
0ndd-0001-dddd-dddd-nnnn-1101 ADD Imm10n, Rn
0ndd-0010-dddd-dddd-nnnn-1101 LDI Imm10u, Rn
0ndd-0011-dddd-dddd-nnnn-1101 LDI Imm10n, Rn
0ndd-0100-dddd-dddd-nnnn-1101 TST Imm10u, Rn
0ndd-0101-dddd-dddd-nnnn-1101 TST Imm10n, Rn

0ndd-1000-dddd-dddd-nnnn-1101 CMPEQ Imm10u, Rn
0ndd-1001-dddd-dddd-nnnn-1101 CMPEQ Imm10n, Rn
0ndd-1010-dddd-dddd-nnnn-1101 CMPGT Imm10u, Rn
0ndd-1011-dddd-dddd-nnnn-1101 CMPGT Imm10n, Rn
0ndd-1100-dddd-dddd-nnnn-1101 CMPGE Imm10u, Rn
0ndd-1101-dddd-dddd-nnnn-1101 CMPGE Imm10n, Rn
0ndd-1110-dddd-dddd-nnnn-1101 CMPHI Imm10u, Rn
0ndd-1111-dddd-dddd-nnnn-1101 CMPHS Imm10u, Rn

10dd-0000-dddd-dddd-dddd-1101 BRA Disp14s (+/- 8K)
10dd-0001-dddd-dddd-dddd-1101 BSR Disp14s
10dd-0010-dddd-dddd-dddd-1101 BT Disp14s
10dd-0011-dddd-dddd-dddd-1101 BF Disp14s
10dd-0100-dddd-dddd-dddd-1101 ADD Disp14u, SP (16K)
10dd-0101-dddd-dddd-dddd-1101 ADD Disp14n, SP (16K)

...

Within 32b space:
PP00-0000-0nmi-0SSS-iiii-mmmm-nnnn-0011 Store (Index)
PP00-dddd-1nmd-0SSS-dddd-mmmm-nnnn-0011 Store (Disp9u)
PP00-0000-0nmi-1SSS-iiii-mmmm-nnnn-0011 Load (Index)
PP00-dddd-1nmd-1SSS-dddd-mmmm-nnnn-0011 Load (Disp9u)
PP00-ZZZZ-0nmt-ZZZZ-tttt-ssss-nnnn-0111 ALU (3R Space)
PP00-dddd-1nmd-ZZZZ-dddd-ssss-nnnn-0111 ALU (3RI, Imm9u)
...
PPdd-dddd-0ndd-0000-dddd-dddd-nnnn-1101 ADD Imm16u, Rn
PPdd-dddd-0ndd-0001-dddd-dddd-nnnn-1101 ADD Imm16n, Rn
PPdd-dddd-0ndd-0010-dddd-dddd-nnnn-1101 LDIZ Imm16u, Rn
PPdd-dddd-0ndd-0011-dddd-dddd-nnnn-1101 LDIN Imm16n, Rn
PPdd-dddd-0ndd-0100-dddd-dddd-nnnn-1101 TST Imm16u, Rn
PPdd-dddd-0ndd-0101-dddd-dddd-nnnn-1101 LDISH Imm16u, Rn
...
PPdd-dddd-10dd-0000-dddd-dddd-dddd-1111 BRA Disp20s (+/- 512K)
PPdd-dddd-10dd-0001-dddd-dddd-dddd-1111 BSR Disp20s

ZZdd-dddd-11dd-dddd-dddd-dddd-dddd-1111 Jumbo Group

...

PP: 00=Always, 01=Wide-Execute Hint, 10=If-True, 11=If-False

....

Tweaks are possible, this is just what I have come up with at the moment
(kind of a bit-confetti design, but alas...).

Thomas Koenig <tkoenig@netcologne.de> schrieb:
> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> schrieb:

>> I am probably missing something, but using your 40% figure
>>
>> (.4 * 20) + (.6 * 40) = 8 + 24 = 32
>
> Density is the number of instructions per unit, you have to
> add the inverse of the number of bits.
>
> 1/(0.4 / 20 + 0.6 / 40) = 1/ (0.02 + 0.015) = 28.57...
>
> (Same as when calculating an avarage density of a mixture).

Ah, never mind. You are right, 40% is not quite enough.
Have to stick in some compare immediate and branch instructions
as well.