Would it be possible or just a bad idea to allow some form of
variable/fp encoding of branch offsets?

I.e. all small (byte) offsets would be encoded directly, but for longer
ones you could require the target to be word/dword/qword aligned, and
therefore allow a much greater range.

It would probably only be useful for inter-module calls/branches...

The main problem is probably that the target address adder is already in
the critical path, so you can't just add a little shifter there as well.

(Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of this,
right?)

Terje

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

On Wednesday, March 1, 2023 at 1:14:22 AM UTC-7, Terje Mathisen wrote:
> Would it be possible or just a bad idea to allow some form of
> variable/fp encoding of branch offsets?
>
> I.e. all small (byte) offsets would be encoded directly, but for longer
> ones you could require the target to be word/dword/qword aligned, and
> therefore allow a much greater range.

Some instruction sets _do_ include two types of branch instructions.

One has a single-byte relative offset, and the other uses the normal
form of memory addressing; usually, the instructions are 16 bits and
32 bits in length respectively.

The alignment restriction is the same in both cases, that of an
instruction. So the one-byte relative offset would be a multiple of
16 bits, for example, while the full-length offset would be in bytes,
but an odd value would be invalid (wasting a bit).

John Savard

Terje Mathisen wrote:
> Would it be possible or just a bad idea to allow some form of
> variable/fp encoding of branch offsets?
>
> I.e. all small (byte) offsets would be encoded directly, but for longer
> ones you could require the target to be word/dword/qword aligned, and
> therefore allow a much greater range.
>
> It would probably only be useful for inter-module calls/branches...
>
> The main problem is probably that the target address adder is already in
> the critical path, so you can't just add a little shifter there as well.
>
> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of this,
> right?)
>
> Terje

As with any variable length instruction, extracting its size
in the parse or decode stage is critical for concurrent decode.
So ideally this offset *won't* be an "fp-like" data item with an
"exponent" field appended to the opcode, but the instruction size
in words is in the first byte and the internal instruction format
is sorted out by decode.

RIP-relative offsets are often relative to the incremented RIP
and include the variable instruction's length. The alignment
is for both the 'from' and 'to' addresses and aligning just the
destination to 32 or 64 bits won't allow encoding a larger range.

The issue I had is when instructions are not byte aligned,
in my case 16-bit words. For branches the immediate field is a
relative _word_ count to get one extra bit of offset range.
But what to do when the immediate field is a 64-bit value:
should that still be a word offset count,
or should it switch to being a byte offset count?

For LD and ST the immediate offset is always a byte offset,
even if it is RIP-relative addressing.

In my naming convention, Branch is to relative offset,
Jump is to an absolute address.

I have a "BR reg" with the offset in a register,
intended for use in position-independent SWITCH statements.
A scaled-indexed LD of the offset onto a register, then BR reg.
But should that register offset be a byte count or a word count?
Or should I have two "BR reg" instructions, one for each?

On 3/1/2023 8:06 AM, EricP wrote:
> Terje Mathisen wrote:
>> Would it be possible or just a bad idea to allow some form of
>> variable/fp encoding of branch offsets?
>>
>> I.e. all small (byte) offsets would be encoded directly, but for
>> longer ones you could require the target to be word/dword/qword
>> aligned, and therefore allow a much greater range.
>>
>> It would probably only be useful for inter-module calls/branches...
>>
>> The main problem is probably that the target address adder is already
>> in the critical path, so you can't just add a little shifter there as
>> well.
>>
>> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of
>> this, right?)
>>
>> Terje
>
> As with any variable length instruction, extracting its size
> in the parse or decode stage is critical for concurrent decode.
> So ideally this offset *won't* be an "fp-like" data item with an
> "exponent" field appended to the opcode, but the instruction size
> in words is in the first byte and the internal instruction format
> is sorted out by decode.
>
> RIP-relative offsets are often relative to the incremented RIP
> and include the variable instruction's length. The alignment
> is for both the 'from' and 'to' addresses and aligning just the
> destination to 32 or 64 bits won't allow encoding a larger range.
>
> The issue I had is when instructions are not byte aligned,
> in my case 16-bit words. For branches the immediate field is a
> relative _word_ count to get one extra bit of offset range.
> But what to do when the immediate field is a 64-bit value:
> should that still be a word offset count,
> or should it switch to being a byte offset count?
>
> For LD and ST the immediate offset is always a byte offset,
> even if it is RIP-relative addressing.
>
> In my naming convention, Branch is to relative offset,
> Jump is to an absolute address.
>
> I have a "BR reg" with the offset in a register,
> intended for use in position-independent SWITCH statements.
> A scaled-indexed LD of the offset onto a register, then BR reg.
> But should that register offset be a byte count or a word count?
> Or should I have two "BR reg" instructions, one for each?

I, perhaps mistakenly, interpreted Terje's suggestion differently. I
don't think he was suggesting variable length instructions, but an
orthogonal idea. Let's take an example. Suppose you have 10 bits
available for a branch offset. If the high order bit is zero, the low
order nine bits give a byte address. But if the high order bit is one,
you get the address by appending say 3 zero bits to the low order 9
bits, giving a possible displacement of 12 bits, but restricted to an 8
byte aligned address.

Of course, this idea isn't applicable to just byte aligned instructions,
though its benefit diminishes as you increase the instruction alignment
requirements.

Whether this is a good idea or not, I don't know.

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

Stephen Fuld wrote:
> On 3/1/2023 8:06 AM, EricP wrote:
>> Terje Mathisen wrote:
>>> Would it be possible or just a bad idea to allow some form of
>>> variable/fp encoding of branch offsets?
>>>
>>> I.e. all small (byte) offsets would be encoded directly, but for
>>> longer ones you could require the target to be word/dword/qword
>>> aligned, and therefore allow a much greater range.
>>>
>>> It would probably only be useful for inter-module calls/branches...
>>>
>>> The main problem is probably that the target address adder is already
>>> in the critical path, so you can't just add a little shifter there as
>>> well.
>>>
>>> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of
>>> this, right?)
>>>
>>> Terje
>>
>> As with any variable length instruction, extracting its size
>> in the parse or decode stage is critical for concurrent decode.
>> So ideally this offset *won't* be an "fp-like" data item with an
>> "exponent" field appended to the opcode, but the instruction size
>> in words is in the first byte and the internal instruction format
>> is sorted out by decode.
>>
>> RIP-relative offsets are often relative to the incremented RIP
>> and include the variable instruction's length. The alignment
>> is for both the 'from' and 'to' addresses and aligning just the
>> destination to 32 or 64 bits won't allow encoding a larger range.
>>
>> The issue I had is when instructions are not byte aligned,
>> in my case 16-bit words. For branches the immediate field is a
>> relative _word_ count to get one extra bit of offset range.
>> But what to do when the immediate field is a 64-bit value:
>> should that still be a word offset count,
>> or should it switch to being a byte offset count?
>>
>> For LD and ST the immediate offset is always a byte offset,
>> even if it is RIP-relative addressing.
>>
>> In my naming convention, Branch is to relative offset,
>> Jump is to an absolute address.
>>
>> I have a "BR reg" with the offset in a register,
>> intended for use in position-independent SWITCH statements.
>> A scaled-indexed LD of the offset onto a register, then BR reg.
>> But should that register offset be a byte count or a word count?
>> Or should I have two "BR reg" instructions, one for each?
>
> I, perhaps mistakenly, interpreted Terje's suggestion differently. I
> don't think he was suggesting variable length instructions, but an
> orthogonal idea. Let's take an example. Suppose you have 10 bits
> available for a branch offset. If the high order bit is zero, the low
> order nine bits give a byte address. But if the high order bit is one,
> you get the address by appending say 3 zero bits to the low order 9
> bits, giving a possible displacement of 12 bits, but restricted to an 8
> byte aligned address.
>
> Of course, this idea isn't applicable to just byte aligned instructions,
> though its benefit diminishes as you increase the instruction alignment
> requirements.
>
> Whether this is a good idea or not, I don't know.

Ok, I understand. So the immediate field is fixed size and has
scale data type bits indicating it is a count of int8,int16,int32,
and a signed offset count of those sized words.

The scale would be that of the smallest alignment of the 'from' and 'to'
instructions, which is scaled up by inserting alignment NOPs before both.

I suppose it depends on the size of the immediate field as to how
often it would have to insert NOPs so that it can use a larger scale
to bring a destination back into range.

On Wednesday, March 1, 2023 at 2:14:22 AM UTC-6, Terje Mathisen wrote:
> Would it be possible or just a bad idea to allow some form of
> variable/fp encoding of branch offsets?
>
> I.e. all small (byte) offsets would be encoded directly, but for longer
> ones you could require the target to be word/dword/qword aligned, and
> therefore allow a much greater range.
>
> It would probably only be useful for inter-module calls/branches...
<
It is generally OK to place entry-points on cache line boundaries (about 64Byte
alignments) so you get 8 low order bits (which word instruction machines
already use the lowest 2-bits.) A gain of 6-bits.
<
It is generally not OK to require cache line alignment on labels within a
subroutine.
<
It is generally a good idea that BR and CALL use the same multiplexer
and address generator. So, mainly my first paragraph above is in conflict
with the leading sentence of this paragraph.
>
> The main problem is probably that the target address adder is already in
> the critical path, so you can't just add a little shifter there as well.
>
> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of this,
> right?)
<
In a pipeline microarchitecture, the added calculating branch targets is
seldom the adder performing memory address generation.
>
> Terje
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

On Wednesday, March 1, 2023 at 10:06:45 AM UTC-6, EricP wrote:
> Terje Mathisen wrote:
> > Would it be possible or just a bad idea to allow some form of
> > variable/fp encoding of branch offsets?
> >
> > I.e. all small (byte) offsets would be encoded directly, but for longer
> > ones you could require the target to be word/dword/qword aligned, and
> > therefore allow a much greater range.
> >
> > It would probably only be useful for inter-module calls/branches...
> >
> > The main problem is probably that the target address adder is already in
> > the critical path, so you can't just add a little shifter there as well..
> >
> > (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of this,
> > right?)
> >
> > Terje
> As with any variable length instruction, extracting its size
> in the parse or decode stage is critical for concurrent decode.
> So ideally this offset *won't* be an "fp-like" data item with an
> "exponent" field appended to the opcode, but the instruction size
> in words is in the first byte and the internal instruction format
> is sorted out by decode.
>
> RIP-relative offsets are often relative to the incremented RIP
> and include the variable instruction's length. The alignment
> is for both the 'from' and 'to' addresses and aligning just the
> destination to 32 or 64 bits won't allow encoding a larger range.
>
> The issue I had is when instructions are not byte aligned,
> in my case 16-bit words. For branches the immediate field is a
> relative _word_ count to get one extra bit of offset range.
> But what to do when the immediate field is a 64-bit value:
> should that still be a word offset count,
> or should it switch to being a byte offset count?
>
> For LD and ST the immediate offset is always a byte offset,
> even if it is RIP-relative addressing.
>
> In my naming convention, Branch is to relative offset,
> Jump is to an absolute address.
>
> I have a "BR reg" with the offset in a register,
> intended for use in position-independent SWITCH statements.
> A scaled-indexed LD of the offset onto a register, then BR reg.
> But should that register offset be a byte count or a word count?
> Or should I have two "BR reg" instructions, one for each?

On Wednesday, March 1, 2023 at 10:06:45 AM UTC-6, EricP wrote:
> Terje Mathisen wrote:
> > Would it be possible or just a bad idea to allow some form of
> > variable/fp encoding of branch offsets?
> >
> > I.e. all small (byte) offsets would be encoded directly, but for longer
> > ones you could require the target to be word/dword/qword aligned, and
> > therefore allow a much greater range.
> >
> > It would probably only be useful for inter-module calls/branches...
> >
> > The main problem is probably that the target address adder is already in
> > the critical path, so you can't just add a little shifter there as well..
> >
> > (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of this,
> > right?)
> >
> > Terje
> As with any variable length instruction, extracting its size
> in the parse or decode stage is critical for concurrent decode.
> So ideally this offset *won't* be an "fp-like" data item with an
> "exponent" field appended to the opcode, but the instruction size
> in words is in the first byte and the internal instruction format
> is sorted out by decode.
>
> RIP-relative offsets are often relative to the incremented RIP
> and include the variable instruction's length. The alignment
> is for both the 'from' and 'to' addresses and aligning just the
> destination to 32 or 64 bits won't allow encoding a larger range.
>
> The issue I had is when instructions are not byte aligned,
> in my case 16-bit words. For branches the immediate field is a
> relative _word_ count to get one extra bit of offset range.
> But what to do when the immediate field is a 64-bit value:
> should that still be a word offset count,
> or should it switch to being a byte offset count?
<
Item 1
>
> For LD and ST the immediate offset is always a byte offset,
> even if it is RIP-relative addressing.
>
> In my naming convention, Branch is to relative offset,
> Jump is to an absolute address.
>
> I have a "BR reg" with the offset in a register,
> intended for use in position-independent SWITCH statements.
> A scaled-indexed LD of the offset onto a register, then BR reg.
> But should that register offset be a byte count or a word count?
> Or should I have two "BR reg" instructions, one for each?
<
I agree that Branches should be to displacements (IP = IP+DISP)
I agree that JUMPs should be to absolute locations (IP = value)
<
The timing in the pipeline where reg becomes available is in conflict
with the time when the next fetch address is needed. Reading and
forwarding take significantly longer than IP+DISP calculation. So,
this typically adds 1 cycle of delay to BR reg forms.
<
Item 1::
<
My BR and CALL instructions have a 2^28-bit range from 26-bit
displacement.
But when I switch to the forms with constants, I switch to
absolute addressing.

On 3/1/2023 10:28 AM, EricP wrote:
> Stephen Fuld wrote:
>> On 3/1/2023 8:06 AM, EricP wrote:
>>> Terje Mathisen wrote:
>>>> Would it be possible or just a bad idea to allow some form of
>>>> variable/fp encoding of branch offsets?
>>>>
>>>> I.e. all small (byte) offsets would be encoded directly, but for
>>>> longer ones you could require the target to be word/dword/qword
>>>> aligned, and therefore allow a much greater range.
>>>>
>>>> It would probably only be useful for inter-module calls/branches...
>>>>
>>>> The main problem is probably that the target address adder is
>>>> already in the critical path, so you can't just add a little shifter
>>>> there as well.
>>>>
>>>> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of
>>>> this, right?)
>>>>
>>>> Terje
>>>
>>> As with any variable length instruction, extracting its size
>>> in the parse or decode stage is critical for concurrent decode.
>>> So ideally this offset *won't* be an "fp-like" data item with an
>>> "exponent" field appended to the opcode, but the instruction size
>>> in words is in the first byte and the internal instruction format
>>> is sorted out by decode.
>>>
>>> RIP-relative offsets are often relative to the incremented RIP
>>> and include the variable instruction's length. The alignment
>>> is for both the 'from' and 'to' addresses and aligning just the
>>> destination to 32 or 64 bits won't allow encoding a larger range.
>>>
>>> The issue I had is when instructions are not byte aligned,
>>> in my case 16-bit words. For branches the immediate field is a
>>> relative _word_ count to get one extra bit of offset range.
>>> But what to do when the immediate field is a 64-bit value:
>>> should that still be a word offset count,
>>> or should it switch to being a byte offset count?
>>>
>>> For LD and ST the immediate offset is always a byte offset,
>>> even if it is RIP-relative addressing.
>>>
>>> In my naming convention, Branch is to relative offset,
>>> Jump is to an absolute address.
>>>
>>> I have a "BR reg" with the offset in a register,
>>> intended for use in position-independent SWITCH statements.
>>> A scaled-indexed LD of the offset onto a register, then BR reg.
>>> But should that register offset be a byte count or a word count?
>>> Or should I have two "BR reg" instructions, one for each?
>>
>> I, perhaps mistakenly, interpreted Terje's suggestion differently.  I
>> don't think he was suggesting variable length instructions, but an
>> orthogonal idea.  Let's take an example.   Suppose you have 10 bits
>> available for a branch offset. If the high order bit is zero, the low
>> order nine bits give a byte address.  But if the high order bit is
>> one, you get the address by appending say 3 zero bits to the low order
>> 9 bits, giving a possible displacement of 12 bits, but restricted to
>> an 8 byte aligned address.
>>
>> Of course, this idea isn't applicable to just byte aligned
>> instructions, though its benefit diminishes as you increase the
>> instruction alignment requirements.
>>
>> Whether this is a good idea or not, I don't know.
>
> Ok, I understand. So the immediate field is fixed size and has
> scale data type bits indicating it is a count of int8,int16,int32,
> and a signed offset count of those sized words.

Yes, although I doubt you need to support all three sizes.

> The scale would be that of the smallest alignment of the 'from' and 'to'
> instructions, which is scaled up by inserting alignment NOPs before both.

No need to align the "from" instruction.

> I suppose it depends on the size of the immediate field as to how
> often it would have to insert NOPs so that it can use a larger scale
> to bring a destination back into range.

Yes. And also the mimimum size of an instruction. E.g. for CPUs with
32 bit instructions, you "automatically" get a factor of four in the
range of the branch instructions.

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

Stephen Fuld wrote:
> On 3/1/2023 10:28 AM, EricP wrote:
>> Stephen Fuld wrote:
>>> On 3/1/2023 8:06 AM, EricP wrote:
>>>> Terje Mathisen wrote:
>>>>> Would it be possible or just a bad idea to allow some form of
>>>>> variable/fp encoding of branch offsets?
>>>>>
>>>>> I.e. all small (byte) offsets would be encoded directly, but for
>>>>> longer ones you could require the target to be word/dword/qword
>>>>> aligned, and therefore allow a much greater range.
>>>>>
>>>>> It would probably only be useful for inter-module calls/branches...
>>>>>
>>>>> The main problem is probably that the target address adder is
>>>>> already in the critical path, so you can't just add a little
>>>>> shifter there as well.
>>>>>
>>>>> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of
>>>>> this, right?)
>>>>>
>>>>> Terje
>>>>
>>>> As with any variable length instruction, extracting its size
>>>> in the parse or decode stage is critical for concurrent decode.
>>>> So ideally this offset *won't* be an "fp-like" data item with an
>>>> "exponent" field appended to the opcode, but the instruction size
>>>> in words is in the first byte and the internal instruction format
>>>> is sorted out by decode.
>>>>
>>>> RIP-relative offsets are often relative to the incremented RIP
>>>> and include the variable instruction's length. The alignment
>>>> is for both the 'from' and 'to' addresses and aligning just the
>>>> destination to 32 or 64 bits won't allow encoding a larger range.
>>>>
>>>> The issue I had is when instructions are not byte aligned,
>>>> in my case 16-bit words. For branches the immediate field is a
>>>> relative _word_ count to get one extra bit of offset range.
>>>> But what to do when the immediate field is a 64-bit value:
>>>> should that still be a word offset count,
>>>> or should it switch to being a byte offset count?
>>>>
>>>> For LD and ST the immediate offset is always a byte offset,
>>>> even if it is RIP-relative addressing.
>>>>
>>>> In my naming convention, Branch is to relative offset,
>>>> Jump is to an absolute address.
>>>>
>>>> I have a "BR reg" with the offset in a register,
>>>> intended for use in position-independent SWITCH statements.
>>>> A scaled-indexed LD of the offset onto a register, then BR reg.
>>>> But should that register offset be a byte count or a word count?
>>>> Or should I have two "BR reg" instructions, one for each?
>>>
>>> I, perhaps mistakenly, interpreted Terje's suggestion differently. I
>>> don't think he was suggesting variable length instructions, but an
>>> orthogonal idea. Let's take an example. Suppose you have 10 bits
>>> available for a branch offset. If the high order bit is zero, the low
>>> order nine bits give a byte address. But if the high order bit is
>>> one, you get the address by appending say 3 zero bits to the low
>>> order 9 bits, giving a possible displacement of 12 bits, but
>>> restricted to an 8 byte aligned address.
>>>
>>> Of course, this idea isn't applicable to just byte aligned
>>> instructions, though its benefit diminishes as you increase the
>>> instruction alignment requirements.
>>>
>>> Whether this is a good idea or not, I don't know.
>>
>> Ok, I understand. So the immediate field is fixed size and has
>> scale data type bits indicating it is a count of int8,int16,int32,
>> and a signed offset count of those sized words.
>
> Yes, although I doubt you need to support all three sizes.

If we have a 16-bit immediate field,
and bit[15]==0 means bits [14:0] are a signed int8 offset count,
and bits [15:14]==10 means int16 offset count

then the 15-bit int8 count is redundant with the 14-bit int16 count.

So that prefix should select a different word size, maybe int24?
Or just have two scale sizes, int8 and int32.

>> The scale would be that of the smallest alignment of the 'from' and 'to'
>> instructions, which is scaled up by inserting alignment NOPs before both.
>
> No need to align the "from" instruction.

If you want the offset to be a count of int32's
then both 'from' and 'to' need the same mod-4 alignment.

That is, in order to use an int32 count as the offset then
both BR and target instruction addresses bits [1:0] must be the same.

>> I suppose it depends on the size of the immediate field as to how
>> often it would have to insert NOPs so that it can use a larger scale
>> to bring a destination back into range.
>
> Yes. And also the mimimum size of an instruction. E.g. for CPUs with
> 32 bit instructions, you "automatically" get a factor of four in the
> range of the branch instructions.

On Wednesday, March 1, 2023 at 1:35:40 PM UTC-6, EricP wrote:
> Stephen Fuld wrote:
> > On 3/1/2023 10:28 AM, EricP wrote:
> >> Stephen Fuld wrote:
> >>> On 3/1/2023 8:06 AM, EricP wrote:
> >>>> Terje Mathisen wrote:
> >>>>> Would it be possible or just a bad idea to allow some form of
> >>>>> variable/fp encoding of branch offsets?
> >>>>>
> >>>>> I.e. all small (byte) offsets would be encoded directly, but for
> >>>>> longer ones you could require the target to be word/dword/qword
> >>>>> aligned, and therefore allow a much greater range.
> >>>>>
> >>>>> It would probably only be useful for inter-module calls/branches...
> >>>>>
> >>>>> The main problem is probably that the target address adder is
> >>>>> already in the critical path, so you can't just add a little
> >>>>> shifter there as well.
> >>>>>
> >>>>> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of
> >>>>> this, right?)
> >>>>>
> >>>>> Terje
> >>>>
> >>>> As with any variable length instruction, extracting its size
> >>>> in the parse or decode stage is critical for concurrent decode.
> >>>> So ideally this offset *won't* be an "fp-like" data item with an
> >>>> "exponent" field appended to the opcode, but the instruction size
> >>>> in words is in the first byte and the internal instruction format
> >>>> is sorted out by decode.
> >>>>
> >>>> RIP-relative offsets are often relative to the incremented RIP
> >>>> and include the variable instruction's length. The alignment
> >>>> is for both the 'from' and 'to' addresses and aligning just the
> >>>> destination to 32 or 64 bits won't allow encoding a larger range.
> >>>>
> >>>> The issue I had is when instructions are not byte aligned,
> >>>> in my case 16-bit words. For branches the immediate field is a
> >>>> relative _word_ count to get one extra bit of offset range.
> >>>> But what to do when the immediate field is a 64-bit value:
> >>>> should that still be a word offset count,
> >>>> or should it switch to being a byte offset count?
> >>>>
> >>>> For LD and ST the immediate offset is always a byte offset,
> >>>> even if it is RIP-relative addressing.
> >>>>
> >>>> In my naming convention, Branch is to relative offset,
> >>>> Jump is to an absolute address.
> >>>>
> >>>> I have a "BR reg" with the offset in a register,
> >>>> intended for use in position-independent SWITCH statements.
> >>>> A scaled-indexed LD of the offset onto a register, then BR reg.
> >>>> But should that register offset be a byte count or a word count?
> >>>> Or should I have two "BR reg" instructions, one for each?
> >>>
> >>> I, perhaps mistakenly, interpreted Terje's suggestion differently. I
> >>> don't think he was suggesting variable length instructions, but an
> >>> orthogonal idea. Let's take an example. Suppose you have 10 bits
> >>> available for a branch offset. If the high order bit is zero, the low
> >>> order nine bits give a byte address. But if the high order bit is
> >>> one, you get the address by appending say 3 zero bits to the low
> >>> order 9 bits, giving a possible displacement of 12 bits, but
> >>> restricted to an 8 byte aligned address.
> >>>
> >>> Of course, this idea isn't applicable to just byte aligned
> >>> instructions, though its benefit diminishes as you increase the
> >>> instruction alignment requirements.
> >>>
> >>> Whether this is a good idea or not, I don't know.
> >>
> >> Ok, I understand. So the immediate field is fixed size and has
> >> scale data type bits indicating it is a count of int8,int16,int32,
> >> and a signed offset count of those sized words.
> >
> > Yes, although I doubt you need to support all three sizes.
> If we have a 16-bit immediate field,
> and bit[15]==0 means bits [14:0] are a signed int8 offset count,
> and bits [15:14]==10 means int16 offset count
>
> then the 15-bit int8 count is redundant with the 14-bit int16 count.
>
> So that prefix should select a different word size, maybe int24?
> Or just have two scale sizes, int8 and int32.
> >> The scale would be that of the smallest alignment of the 'from' and 'to'
> >> instructions, which is scaled up by inserting alignment NOPs before both.
> >
> > No need to align the "from" instruction.
> If you want the offset to be a count of int32's
> then both 'from' and 'to' need the same mod-4 alignment.
<
M88K, MIPS, SPARC, Alpha all had the IP<1..0> == 2b'00 as an alignment
condition.
>
> That is, in order to use an int32 count as the offset then
> both BR and target instruction addresses bits [1:0] must be the same.
<
At the time control transfer address is generated, IP<1..0> == 0 and
target_address<1..0> == 0. Thus, one can always shift a constant field
up by 2 bits and gain displacement range at no real cost.
<
> >> I suppose it depends on the size of the immediate field as to how
> >> often it would have to insert NOPs so that it can use a larger scale
> >> to bring a destination back into range.
> >
> > Yes. And also the mimimum size of an instruction. E.g. for CPUs with
> > 32 bit instructions, you "automatically" get a factor of four in the
> > range of the branch instructions.

On 3/1/2023 11:35 AM, EricP wrote:
> Stephen Fuld wrote:
>> On 3/1/2023 10:28 AM, EricP wrote:
>>> Stephen Fuld wrote:
>>>> On 3/1/2023 8:06 AM, EricP wrote:
>>>>> Terje Mathisen wrote:
>>>>>> Would it be possible or just a bad idea to allow some form of
>>>>>> variable/fp encoding of branch offsets?
>>>>>>
>>>>>> I.e. all small (byte) offsets would be encoded directly, but for
>>>>>> longer ones you could require the target to be word/dword/qword
>>>>>> aligned, and therefore allow a much greater range.
>>>>>>
>>>>>> It would probably only be useful for inter-module calls/branches...
>>>>>>
>>>>>> The main problem is probably that the target address adder is
>>>>>> already in the critical path, so you can't just add a little
>>>>>> shifter there as well.
>>>>>>
>>>>>> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of
>>>>>> this, right?)
>>>>>>
>>>>>> Terje
>>>>>
>>>>> As with any variable length instruction, extracting its size
>>>>> in the parse or decode stage is critical for concurrent decode.
>>>>> So ideally this offset *won't* be an "fp-like" data item with an
>>>>> "exponent" field appended to the opcode, but the instruction size
>>>>> in words is in the first byte and the internal instruction format
>>>>> is sorted out by decode.
>>>>>
>>>>> RIP-relative offsets are often relative to the incremented RIP
>>>>> and include the variable instruction's length. The alignment
>>>>> is for both the 'from' and 'to' addresses and aligning just the
>>>>> destination to 32 or 64 bits won't allow encoding a larger range.
>>>>>
>>>>> The issue I had is when instructions are not byte aligned,
>>>>> in my case 16-bit words. For branches the immediate field is a
>>>>> relative _word_ count to get one extra bit of offset range.
>>>>> But what to do when the immediate field is a 64-bit value:
>>>>> should that still be a word offset count,
>>>>> or should it switch to being a byte offset count?
>>>>>
>>>>> For LD and ST the immediate offset is always a byte offset,
>>>>> even if it is RIP-relative addressing.
>>>>>
>>>>> In my naming convention, Branch is to relative offset,
>>>>> Jump is to an absolute address.
>>>>>
>>>>> I have a "BR reg" with the offset in a register,
>>>>> intended for use in position-independent SWITCH statements.
>>>>> A scaled-indexed LD of the offset onto a register, then BR reg.
>>>>> But should that register offset be a byte count or a word count?
>>>>> Or should I have two "BR reg" instructions, one for each?
>>>>
>>>> I, perhaps mistakenly, interpreted Terje's suggestion differently.
>>>> I don't think he was suggesting variable length instructions, but an
>>>> orthogonal idea.  Let's take an example.   Suppose you have 10 bits
>>>> available for a branch offset. If the high order bit is zero, the
>>>> low order nine bits give a byte address.  But if the high order bit
>>>> is one, you get the address by appending say 3 zero bits to the low
>>>> order 9 bits, giving a possible displacement of 12 bits, but
>>>> restricted to an 8 byte aligned address.
>>>>
>>>> Of course, this idea isn't applicable to just byte aligned
>>>> instructions, though its benefit diminishes as you increase the
>>>> instruction alignment requirements.
>>>>
>>>> Whether this is a good idea or not, I don't know.
>>>
>>> Ok, I understand. So the immediate field is fixed size and has
>>> scale data type bits indicating it is a count of int8,int16,int32,
>>> and a signed offset count of those sized words.
>>
>> Yes, although I doubt you need to support all three sizes.
>
> If we have a 16-bit immediate field,
> and bit[15]==0 means bits [14:0] are a signed int8 offset count,
> and bits [15:14]==10 means int16 offset count
>
> then the 15-bit int8 count is redundant with the 14-bit int16 count.
>
> So that prefix should select a different word size, maybe int24?
> Or just have two scale sizes, int8 and int32.

That is what I would suggest.

>>> The scale would be that of the smallest alignment of the 'from' and 'to'
>>> instructions, which is scaled up by inserting alignment NOPs before
>>> both.
>>
>> No need to align the "from" instruction.
>
> If you want the offset to be a count of int32's
> then both 'from' and 'to' need the same mod-4 alignment.

Or, you have the rule that the address of the "from" instruction is
rounded up to the nearest size used for the displacement field. i.e. if
the address of the from instruction is say xxx03, and the displacement
is scaled to 4 byte values, the the xxx03 is "rounded up" to xxx04.

> That is, in order to use an int32 count as the offset then
> both BR and target instruction addresses bits [1:0] must be the same.

Not necessarily. See above.

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

On Wednesday, March 1, 2023 at 3:11:12 PM UTC-6, Stephen Fuld wrote:
> On 3/1/2023 11:35 AM, EricP wrote:
> > Stephen Fuld wrote:
> >> On 3/1/2023 10:28 AM, EricP wrote:
> >>> Stephen Fuld wrote:
> >>>> On 3/1/2023 8:06 AM, EricP wrote:
> >>>>> Terje Mathisen wrote:
> >>>>>> Would it be possible or just a bad idea to allow some form of
> >>>>>> variable/fp encoding of branch offsets?
> >>>>>>
> >>>>>> I.e. all small (byte) offsets would be encoded directly, but for
> >>>>>> longer ones you could require the target to be word/dword/qword
> >>>>>> aligned, and therefore allow a much greater range.
> >>>>>>
> >>>>>> It would probably only be useful for inter-module calls/branches....
> >>>>>>
> >>>>>> The main problem is probably that the target address adder is
> >>>>>> already in the critical path, so you can't just add a little
> >>>>>> shifter there as well.
> >>>>>>
> >>>>>> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of
> >>>>>> this, right?)
> >>>>>>
> >>>>>> Terje
> >>>>>
> >>>>> As with any variable length instruction, extracting its size
> >>>>> in the parse or decode stage is critical for concurrent decode.
> >>>>> So ideally this offset *won't* be an "fp-like" data item with an
> >>>>> "exponent" field appended to the opcode, but the instruction size
> >>>>> in words is in the first byte and the internal instruction format
> >>>>> is sorted out by decode.
> >>>>>
> >>>>> RIP-relative offsets are often relative to the incremented RIP
> >>>>> and include the variable instruction's length. The alignment
> >>>>> is for both the 'from' and 'to' addresses and aligning just the
> >>>>> destination to 32 or 64 bits won't allow encoding a larger range.
> >>>>>
> >>>>> The issue I had is when instructions are not byte aligned,
> >>>>> in my case 16-bit words. For branches the immediate field is a
> >>>>> relative _word_ count to get one extra bit of offset range.
> >>>>> But what to do when the immediate field is a 64-bit value:
> >>>>> should that still be a word offset count,
> >>>>> or should it switch to being a byte offset count?
> >>>>>
> >>>>> For LD and ST the immediate offset is always a byte offset,
> >>>>> even if it is RIP-relative addressing.
> >>>>>
> >>>>> In my naming convention, Branch is to relative offset,
> >>>>> Jump is to an absolute address.
> >>>>>
> >>>>> I have a "BR reg" with the offset in a register,
> >>>>> intended for use in position-independent SWITCH statements.
> >>>>> A scaled-indexed LD of the offset onto a register, then BR reg.
> >>>>> But should that register offset be a byte count or a word count?
> >>>>> Or should I have two "BR reg" instructions, one for each?
> >>>>
> >>>> I, perhaps mistakenly, interpreted Terje's suggestion differently.
> >>>> I don't think he was suggesting variable length instructions, but an
> >>>> orthogonal idea. Let's take an example. Suppose you have 10 bits
> >>>> available for a branch offset. If the high order bit is zero, the
> >>>> low order nine bits give a byte address. But if the high order bit
> >>>> is one, you get the address by appending say 3 zero bits to the low
> >>>> order 9 bits, giving a possible displacement of 12 bits, but
> >>>> restricted to an 8 byte aligned address.
> >>>>
> >>>> Of course, this idea isn't applicable to just byte aligned
> >>>> instructions, though its benefit diminishes as you increase the
> >>>> instruction alignment requirements.
> >>>>
> >>>> Whether this is a good idea or not, I don't know.
> >>>
> >>> Ok, I understand. So the immediate field is fixed size and has
> >>> scale data type bits indicating it is a count of int8,int16,int32,
> >>> and a signed offset count of those sized words.
> >>
> >> Yes, although I doubt you need to support all three sizes.
> >
> > If we have a 16-bit immediate field,
> > and bit[15]==0 means bits [14:0] are a signed int8 offset count,
> > and bits [15:14]==10 means int16 offset count
> >
> > then the 15-bit int8 count is redundant with the 14-bit int16 count.
> >
> > So that prefix should select a different word size, maybe int24?
> > Or just have two scale sizes, int8 and int32.
> That is what I would suggest.
> >>> The scale would be that of the smallest alignment of the 'from' and 'to'
> >>> instructions, which is scaled up by inserting alignment NOPs before
> >>> both.
> >>
> >> No need to align the "from" instruction.
> >
> > If you want the offset to be a count of int32's
> > then both 'from' and 'to' need the same mod-4 alignment.
<
> Or, you have the rule that the address of the "from" instruction is
> rounded up to the nearest size used for the displacement field. i.e. if
> the address of the from instruction is say xxx03, and the displacement
> is scaled to 4 byte values, the the xxx03 is "rounded up" to xxx04.
<
Rounding is significantly (several gates of delay) more expensive than
truncation (free).
<
The majority of architectures past and present require that "what comes
out of the branch adder" is what can be used to access instructions.
<
> > That is, in order to use an int32 count as the offset then
> > both BR and target instruction addresses bits [1:0] must be the same.
> Not necessarily. See above.
> --
> - Stephen Fuld
> (e-mail address disguised to prevent spam)

On 3/1/2023 2:42 PM, MitchAlsup wrote:
> On Wednesday, March 1, 2023 at 3:11:12 PM UTC-6, Stephen Fuld wrote:
>> On 3/1/2023 11:35 AM, EricP wrote:
>>> Stephen Fuld wrote:
>>>> On 3/1/2023 10:28 AM, EricP wrote:
>>>>> Stephen Fuld wrote:
>>>>>> On 3/1/2023 8:06 AM, EricP wrote:
>>>>>>> Terje Mathisen wrote:
>>>>>>>> Would it be possible or just a bad idea to allow some form of
>>>>>>>> variable/fp encoding of branch offsets?
>>>>>>>>
>>>>>>>> I.e. all small (byte) offsets would be encoded directly, but for
>>>>>>>> longer ones you could require the target to be word/dword/qword
>>>>>>>> aligned, and therefore allow a much greater range.
>>>>>>>>
>>>>>>>> It would probably only be useful for inter-module calls/branches...
>>>>>>>>
>>>>>>>> The main problem is probably that the target address adder is
>>>>>>>> already in the critical path, so you can't just add a little
>>>>>>>> shifter there as well.
>>>>>>>>
>>>>>>>> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of
>>>>>>>> this, right?)
>>>>>>>>
>>>>>>>> Terje
>>>>>>>
>>>>>>> As with any variable length instruction, extracting its size
>>>>>>> in the parse or decode stage is critical for concurrent decode.
>>>>>>> So ideally this offset *won't* be an "fp-like" data item with an
>>>>>>> "exponent" field appended to the opcode, but the instruction size
>>>>>>> in words is in the first byte and the internal instruction format
>>>>>>> is sorted out by decode.
>>>>>>>
>>>>>>> RIP-relative offsets are often relative to the incremented RIP
>>>>>>> and include the variable instruction's length. The alignment
>>>>>>> is for both the 'from' and 'to' addresses and aligning just the
>>>>>>> destination to 32 or 64 bits won't allow encoding a larger range.
>>>>>>>
>>>>>>> The issue I had is when instructions are not byte aligned,
>>>>>>> in my case 16-bit words. For branches the immediate field is a
>>>>>>> relative _word_ count to get one extra bit of offset range.
>>>>>>> But what to do when the immediate field is a 64-bit value:
>>>>>>> should that still be a word offset count,
>>>>>>> or should it switch to being a byte offset count?
>>>>>>>
>>>>>>> For LD and ST the immediate offset is always a byte offset,
>>>>>>> even if it is RIP-relative addressing.
>>>>>>>
>>>>>>> In my naming convention, Branch is to relative offset,
>>>>>>> Jump is to an absolute address.
>>>>>>>
>>>>>>> I have a "BR reg" with the offset in a register,
>>>>>>> intended for use in position-independent SWITCH statements.
>>>>>>> A scaled-indexed LD of the offset onto a register, then BR reg.
>>>>>>> But should that register offset be a byte count or a word count?
>>>>>>> Or should I have two "BR reg" instructions, one for each?
>>>>>>
>>>>>> I, perhaps mistakenly, interpreted Terje's suggestion differently.
>>>>>> I don't think he was suggesting variable length instructions, but an
>>>>>> orthogonal idea. Let's take an example. Suppose you have 10 bits
>>>>>> available for a branch offset. If the high order bit is zero, the
>>>>>> low order nine bits give a byte address. But if the high order bit
>>>>>> is one, you get the address by appending say 3 zero bits to the low
>>>>>> order 9 bits, giving a possible displacement of 12 bits, but
>>>>>> restricted to an 8 byte aligned address.
>>>>>>
>>>>>> Of course, this idea isn't applicable to just byte aligned
>>>>>> instructions, though its benefit diminishes as you increase the
>>>>>> instruction alignment requirements.
>>>>>>
>>>>>> Whether this is a good idea or not, I don't know.
>>>>>
>>>>> Ok, I understand. So the immediate field is fixed size and has
>>>>> scale data type bits indicating it is a count of int8,int16,int32,
>>>>> and a signed offset count of those sized words.
>>>>
>>>> Yes, although I doubt you need to support all three sizes.
>>>
>>> If we have a 16-bit immediate field,
>>> and bit[15]==0 means bits [14:0] are a signed int8 offset count,
>>> and bits [15:14]==10 means int16 offset count
>>>
>>> then the 15-bit int8 count is redundant with the 14-bit int16 count.
>>>
>>> So that prefix should select a different word size, maybe int24?
>>> Or just have two scale sizes, int8 and int32.
>> That is what I would suggest.
>>>>> The scale would be that of the smallest alignment of the 'from' and 'to'
>>>>> instructions, which is scaled up by inserting alignment NOPs before
>>>>> both.
>>>>
>>>> No need to align the "from" instruction.
>>>
>>> If you want the offset to be a count of int32's
>>> then both 'from' and 'to' need the same mod-4 alignment.
> <
>> Or, you have the rule that the address of the "from" instruction is
>> rounded up to the nearest size used for the displacement field. i.e. if
>> the address of the from instruction is say xxx03, and the displacement
>> is scaled to 4 byte values, the the xxx03 is "rounded up" to xxx04.
> <
> Rounding is significantly (several gates of delay) more expensive than
> truncation (free).

Fair enough. I think this whole thing is a little overblown, as it
really applies only to systems with byte aligned (or perhaps half word
aligned without a pairing requirement) systems, which, other than X86 I
think are pretty rare. If you stick with 32 bit instructions, then I
think Terje's original idea is just not worth it.

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

On Wednesday, March 1, 2023 at 6:11:25 PM UTC-5, Stephen Fuld wrote:
> On 3/1/2023 2:42 PM, MitchAlsup wrote:
> > On Wednesday, March 1, 2023 at 3:11:12 PM UTC-6, Stephen Fuld wrote:
> >> On 3/1/2023 11:35 AM, EricP wrote:
> >>> Stephen Fuld wrote:
> >>>> On 3/1/2023 10:28 AM, EricP wrote:
> >>>>> Stephen Fuld wrote:
> >>>>>> On 3/1/2023 8:06 AM, EricP wrote:
> >>>>>>> Terje Mathisen wrote:
> >>>>>>>> Would it be possible or just a bad idea to allow some form of
> >>>>>>>> variable/fp encoding of branch offsets?
> >>>>>>>>
> >>>>>>>> I.e. all small (byte) offsets would be encoded directly, but for
> >>>>>>>> longer ones you could require the target to be word/dword/qword
> >>>>>>>> aligned, and therefore allow a much greater range.
> >>>>>>>>
> >>>>>>>> It would probably only be useful for inter-module calls/branches....
> >>>>>>>>
> >>>>>>>> The main problem is probably that the target address adder is
> >>>>>>>> already in the critical path, so you can't just add a little
> >>>>>>>> shifter there as well.
> >>>>>>>>
> >>>>>>>> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of
> >>>>>>>> this, right?)
> >>>>>>>>
> >>>>>>>> Terje
> >>>>>>>
> >>>>>>> As with any variable length instruction, extracting its size
> >>>>>>> in the parse or decode stage is critical for concurrent decode.
> >>>>>>> So ideally this offset *won't* be an "fp-like" data item with an
> >>>>>>> "exponent" field appended to the opcode, but the instruction size
> >>>>>>> in words is in the first byte and the internal instruction format
> >>>>>>> is sorted out by decode.
> >>>>>>>
> >>>>>>> RIP-relative offsets are often relative to the incremented RIP
> >>>>>>> and include the variable instruction's length. The alignment
> >>>>>>> is for both the 'from' and 'to' addresses and aligning just the
> >>>>>>> destination to 32 or 64 bits won't allow encoding a larger range.
> >>>>>>>
> >>>>>>> The issue I had is when instructions are not byte aligned,
> >>>>>>> in my case 16-bit words. For branches the immediate field is a
> >>>>>>> relative _word_ count to get one extra bit of offset range.
> >>>>>>> But what to do when the immediate field is a 64-bit value:
> >>>>>>> should that still be a word offset count,
> >>>>>>> or should it switch to being a byte offset count?
> >>>>>>>
> >>>>>>> For LD and ST the immediate offset is always a byte offset,
> >>>>>>> even if it is RIP-relative addressing.
> >>>>>>>
> >>>>>>> In my naming convention, Branch is to relative offset,
> >>>>>>> Jump is to an absolute address.
> >>>>>>>
> >>>>>>> I have a "BR reg" with the offset in a register,
> >>>>>>> intended for use in position-independent SWITCH statements.
> >>>>>>> A scaled-indexed LD of the offset onto a register, then BR reg.
> >>>>>>> But should that register offset be a byte count or a word count?
> >>>>>>> Or should I have two "BR reg" instructions, one for each?
> >>>>>>
> >>>>>> I, perhaps mistakenly, interpreted Terje's suggestion differently.
> >>>>>> I don't think he was suggesting variable length instructions, but an
> >>>>>> orthogonal idea. Let's take an example. Suppose you have 10 bits
> >>>>>> available for a branch offset. If the high order bit is zero, the
> >>>>>> low order nine bits give a byte address. But if the high order bit
> >>>>>> is one, you get the address by appending say 3 zero bits to the low
> >>>>>> order 9 bits, giving a possible displacement of 12 bits, but
> >>>>>> restricted to an 8 byte aligned address.
> >>>>>>
> >>>>>> Of course, this idea isn't applicable to just byte aligned
> >>>>>> instructions, though its benefit diminishes as you increase the
> >>>>>> instruction alignment requirements.
> >>>>>>
> >>>>>> Whether this is a good idea or not, I don't know.
> >>>>>
> >>>>> Ok, I understand. So the immediate field is fixed size and has
> >>>>> scale data type bits indicating it is a count of int8,int16,int32,
> >>>>> and a signed offset count of those sized words.
> >>>>
> >>>> Yes, although I doubt you need to support all three sizes.
> >>>
> >>> If we have a 16-bit immediate field,
> >>> and bit[15]==0 means bits [14:0] are a signed int8 offset count,
> >>> and bits [15:14]==10 means int16 offset count
> >>>
> >>> then the 15-bit int8 count is redundant with the 14-bit int16 count.
> >>>
> >>> So that prefix should select a different word size, maybe int24?
> >>> Or just have two scale sizes, int8 and int32.
> >> That is what I would suggest.
> >>>>> The scale would be that of the smallest alignment of the 'from' and 'to'
> >>>>> instructions, which is scaled up by inserting alignment NOPs before
> >>>>> both.
> >>>>
> >>>> No need to align the "from" instruction.
> >>>
> >>> If you want the offset to be a count of int32's
> >>> then both 'from' and 'to' need the same mod-4 alignment.
> > <
> >> Or, you have the rule that the address of the "from" instruction is
> >> rounded up to the nearest size used for the displacement field. i.e. if
> >> the address of the from instruction is say xxx03, and the displacement
> >> is scaled to 4 byte values, the the xxx03 is "rounded up" to xxx04.
> > <
> > Rounding is significantly (several gates of delay) more expensive than
> > truncation (free).
> Fair enough. I think this whole thing is a little overblown, as it
> really applies only to systems with byte aligned (or perhaps half word
> aligned without a pairing requirement) systems, which, other than X86 I
> think are pretty rare. If you stick with 32 bit instructions, then I
> think Terje's original idea is just not worth it.
> --
> - Stephen Fuld
> (e-mail address disguised to prevent spam)

I agree. With 32-bit or more instructions the displacement field can be large
enough to cover practically all branch cases. There are seldom code modules
larger than 16MB meaning 24-bits is probably adequate. The branch
displacement does not need to be able to cover the whole physical address
space when virtual addressing is available. For conditional branches a
displacement of 16-bits covers virtually all cases. If there is the odd case
where the branch displacement is not large enough it is possible to load a
value into a register and branch to that.

On 3/1/2023 8:43 PM, robf...@gmail.com wrote:
> On Wednesday, March 1, 2023 at 6:11:25 PM UTC-5, Stephen Fuld wrote:
>> On 3/1/2023 2:42 PM, MitchAlsup wrote:
>>> On Wednesday, March 1, 2023 at 3:11:12 PM UTC-6, Stephen Fuld wrote:
>>>> On 3/1/2023 11:35 AM, EricP wrote:
>>>>> Stephen Fuld wrote:
>>>>>> On 3/1/2023 10:28 AM, EricP wrote:
>>>>>>> Stephen Fuld wrote:
>>>>>>>> On 3/1/2023 8:06 AM, EricP wrote:
>>>>>>>>> Terje Mathisen wrote:
>>>>>>>>>> Would it be possible or just a bad idea to allow some form of
>>>>>>>>>> variable/fp encoding of branch offsets?
>>>>>>>>>>
>>>>>>>>>> I.e. all small (byte) offsets would be encoded directly, but for
>>>>>>>>>> longer ones you could require the target to be word/dword/qword
>>>>>>>>>> aligned, and therefore allow a much greater range.
>>>>>>>>>>
>>>>>>>>>> It would probably only be useful for inter-module calls/branches...
>>>>>>>>>>
>>>>>>>>>> The main problem is probably that the target address adder is
>>>>>>>>>> already in the critical path, so you can't just add a little
>>>>>>>>>> shifter there as well.
>>>>>>>>>>
>>>>>>>>>> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of
>>>>>>>>>> this, right?)
>>>>>>>>>>
>>>>>>>>>> Terje
>>>>>>>>>
>>>>>>>>> As with any variable length instruction, extracting its size
>>>>>>>>> in the parse or decode stage is critical for concurrent decode.
>>>>>>>>> So ideally this offset *won't* be an "fp-like" data item with an
>>>>>>>>> "exponent" field appended to the opcode, but the instruction size
>>>>>>>>> in words is in the first byte and the internal instruction format
>>>>>>>>> is sorted out by decode.
>>>>>>>>>
>>>>>>>>> RIP-relative offsets are often relative to the incremented RIP
>>>>>>>>> and include the variable instruction's length. The alignment
>>>>>>>>> is for both the 'from' and 'to' addresses and aligning just the
>>>>>>>>> destination to 32 or 64 bits won't allow encoding a larger range.
>>>>>>>>>
>>>>>>>>> The issue I had is when instructions are not byte aligned,
>>>>>>>>> in my case 16-bit words. For branches the immediate field is a
>>>>>>>>> relative _word_ count to get one extra bit of offset range.
>>>>>>>>> But what to do when the immediate field is a 64-bit value:
>>>>>>>>> should that still be a word offset count,
>>>>>>>>> or should it switch to being a byte offset count?
>>>>>>>>>
>>>>>>>>> For LD and ST the immediate offset is always a byte offset,
>>>>>>>>> even if it is RIP-relative addressing.
>>>>>>>>>
>>>>>>>>> In my naming convention, Branch is to relative offset,
>>>>>>>>> Jump is to an absolute address.
>>>>>>>>>
>>>>>>>>> I have a "BR reg" with the offset in a register,
>>>>>>>>> intended for use in position-independent SWITCH statements.
>>>>>>>>> A scaled-indexed LD of the offset onto a register, then BR reg.
>>>>>>>>> But should that register offset be a byte count or a word count?
>>>>>>>>> Or should I have two "BR reg" instructions, one for each?
>>>>>>>>
>>>>>>>> I, perhaps mistakenly, interpreted Terje's suggestion differently.
>>>>>>>> I don't think he was suggesting variable length instructions, but an
>>>>>>>> orthogonal idea. Let's take an example. Suppose you have 10 bits
>>>>>>>> available for a branch offset. If the high order bit is zero, the
>>>>>>>> low order nine bits give a byte address. But if the high order bit
>>>>>>>> is one, you get the address by appending say 3 zero bits to the low
>>>>>>>> order 9 bits, giving a possible displacement of 12 bits, but
>>>>>>>> restricted to an 8 byte aligned address.
>>>>>>>>
>>>>>>>> Of course, this idea isn't applicable to just byte aligned
>>>>>>>> instructions, though its benefit diminishes as you increase the
>>>>>>>> instruction alignment requirements.
>>>>>>>>
>>>>>>>> Whether this is a good idea or not, I don't know.
>>>>>>>
>>>>>>> Ok, I understand. So the immediate field is fixed size and has
>>>>>>> scale data type bits indicating it is a count of int8,int16,int32,
>>>>>>> and a signed offset count of those sized words.
>>>>>>
>>>>>> Yes, although I doubt you need to support all three sizes.
>>>>>
>>>>> If we have a 16-bit immediate field,
>>>>> and bit[15]==0 means bits [14:0] are a signed int8 offset count,
>>>>> and bits [15:14]==10 means int16 offset count
>>>>>
>>>>> then the 15-bit int8 count is redundant with the 14-bit int16 count.
>>>>>
>>>>> So that prefix should select a different word size, maybe int24?
>>>>> Or just have two scale sizes, int8 and int32.
>>>> That is what I would suggest.
>>>>>>> The scale would be that of the smallest alignment of the 'from' and 'to'
>>>>>>> instructions, which is scaled up by inserting alignment NOPs before
>>>>>>> both.
>>>>>>
>>>>>> No need to align the "from" instruction.
>>>>>
>>>>> If you want the offset to be a count of int32's
>>>>> then both 'from' and 'to' need the same mod-4 alignment.
>>> <
>>>> Or, you have the rule that the address of the "from" instruction is
>>>> rounded up to the nearest size used for the displacement field. i.e. if
>>>> the address of the from instruction is say xxx03, and the displacement
>>>> is scaled to 4 byte values, the the xxx03 is "rounded up" to xxx04.
>>> <
>>> Rounding is significantly (several gates of delay) more expensive than
>>> truncation (free).
>> Fair enough. I think this whole thing is a little overblown, as it
>> really applies only to systems with byte aligned (or perhaps half word
>> aligned without a pairing requirement) systems, which, other than X86 I
>> think are pretty rare. If you stick with 32 bit instructions, then I
>> think Terje's original idea is just not worth it.
>> --
>> - Stephen Fuld
>> (e-mail address disguised to prevent spam)
>
> I agree. With 32-bit or more instructions the displacement field can be large
> enough to cover practically all branch cases. There are seldom code modules
> larger than 16MB meaning 24-bits is probably adequate.

Remember, if all instructions are on 32 bit boundaries, you "gain" two
bits of range by appending two zero bits to the displacement. So 16MP
only requires 14 bits, not 16.

> The branch
> displacement does not need to be able to cover the whole physical address
> space when virtual addressing is available. For conditional branches a
> displacement of 16-bits covers virtually all cases. If there is the odd case
> where the branch displacement is not large enough it is possible to load a
> value into a register and branch to that.

Yes, I agree.

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

On 3/1/2023 10:31 PM, Stephen Fuld wrote:
> On 3/1/2023 8:43 PM, robf...@gmail.com wrote:
>> On Wednesday, March 1, 2023 at 6:11:25 PM UTC-5, Stephen Fuld wrote:
>>> On 3/1/2023 2:42 PM, MitchAlsup wrote:
>>>> On Wednesday, March 1, 2023 at 3:11:12 PM UTC-6, Stephen Fuld wrote:
>>>>> On 3/1/2023 11:35 AM, EricP wrote:
>>>>>> Stephen Fuld wrote:
>>>>>>> On 3/1/2023 10:28 AM, EricP wrote:
>>>>>>>> Stephen Fuld wrote:
>>>>>>>>> On 3/1/2023 8:06 AM, EricP wrote:
>>>>>>>>>> Terje Mathisen wrote:
>>>>>>>>>>> Would it be possible or just a bad idea to allow some form of
>>>>>>>>>>> variable/fp encoding of branch offsets?
>>>>>>>>>>>
>>>>>>>>>>> I.e. all small (byte) offsets would be encoded directly, but for
>>>>>>>>>>> longer ones you could require the target to be word/dword/qword
>>>>>>>>>>> aligned, and therefore allow a much greater range.
>>>>>>>>>>>
>>>>>>>>>>> It would probably only be useful for inter-module
>>>>>>>>>>> calls/branches...
>>>>>>>>>>>
>>>>>>>>>>> The main problem is probably that the target address adder is
>>>>>>>>>>> already in the critical path, so you can't just add a little
>>>>>>>>>>> shifter there as well.
>>>>>>>>>>>
>>>>>>>>>>> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing
>>>>>>>>>>> some of
>>>>>>>>>>> this, right?)
>>>>>>>>>>>
>>>>>>>>>>> Terje
>>>>>>>>>>
>>>>>>>>>> As with any variable length instruction, extracting its size
>>>>>>>>>> in the parse or decode stage is critical for concurrent decode.
>>>>>>>>>> So ideally this offset *won't* be an "fp-like" data item with an
>>>>>>>>>> "exponent" field appended to the opcode, but the instruction size
>>>>>>>>>> in words is in the first byte and the internal instruction format
>>>>>>>>>> is sorted out by decode.
>>>>>>>>>>
>>>>>>>>>> RIP-relative offsets are often relative to the incremented RIP
>>>>>>>>>> and include the variable instruction's length. The alignment
>>>>>>>>>> is for both the 'from' and 'to' addresses and aligning just the
>>>>>>>>>> destination to 32 or 64 bits won't allow encoding a larger range.
>>>>>>>>>>
>>>>>>>>>> The issue I had is when instructions are not byte aligned,
>>>>>>>>>> in my case 16-bit words. For branches the immediate field is a
>>>>>>>>>> relative _word_ count to get one extra bit of offset range.
>>>>>>>>>> But what to do when the immediate field is a 64-bit value:
>>>>>>>>>> should that still be a word offset count,
>>>>>>>>>> or should it switch to being a byte offset count?
>>>>>>>>>>
>>>>>>>>>> For LD and ST the immediate offset is always a byte offset,
>>>>>>>>>> even if it is RIP-relative addressing.
>>>>>>>>>>
>>>>>>>>>> In my naming convention, Branch is to relative offset,
>>>>>>>>>> Jump is to an absolute address.
>>>>>>>>>>
>>>>>>>>>> I have a "BR reg" with the offset in a register,
>>>>>>>>>> intended for use in position-independent SWITCH statements.
>>>>>>>>>> A scaled-indexed LD of the offset onto a register, then BR reg.
>>>>>>>>>> But should that register offset be a byte count or a word count?
>>>>>>>>>> Or should I have two "BR reg" instructions, one for each?
>>>>>>>>>
>>>>>>>>> I, perhaps mistakenly, interpreted Terje's suggestion differently.
>>>>>>>>> I don't think he was suggesting variable length instructions,
>>>>>>>>> but an
>>>>>>>>> orthogonal idea. Let's take an example. Suppose you have 10 bits
>>>>>>>>> available for a branch offset. If the high order bit is zero, the
>>>>>>>>> low order nine bits give a byte address. But if the high order bit
>>>>>>>>> is one, you get the address by appending say 3 zero bits to the
>>>>>>>>> low
>>>>>>>>> order 9 bits, giving a possible displacement of 12 bits, but
>>>>>>>>> restricted to an 8 byte aligned address.
>>>>>>>>>
>>>>>>>>> Of course, this idea isn't applicable to just byte aligned
>>>>>>>>> instructions, though its benefit diminishes as you increase the
>>>>>>>>> instruction alignment requirements.
>>>>>>>>>
>>>>>>>>> Whether this is a good idea or not, I don't know.
>>>>>>>>
>>>>>>>> Ok, I understand. So the immediate field is fixed size and has
>>>>>>>> scale data type bits indicating it is a count of int8,int16,int32,
>>>>>>>> and a signed offset count of those sized words.
>>>>>>>
>>>>>>> Yes, although I doubt you need to support all three sizes.
>>>>>>
>>>>>> If we have a 16-bit immediate field,
>>>>>> and bit[15]==0 means bits [14:0] are a signed int8 offset count,
>>>>>> and bits [15:14]==10 means int16 offset count
>>>>>>
>>>>>> then the 15-bit int8 count is redundant with the 14-bit int16 count.
>>>>>>
>>>>>> So that prefix should select a different word size, maybe int24?
>>>>>> Or just have two scale sizes, int8 and int32.
>>>>> That is what I would suggest.
>>>>>>>> The scale would be that of the smallest alignment of the 'from'
>>>>>>>> and 'to'
>>>>>>>> instructions, which is scaled up by inserting alignment NOPs before
>>>>>>>> both.
>>>>>>>
>>>>>>> No need to align the "from" instruction.
>>>>>>
>>>>>> If you want the offset to be a count of int32's
>>>>>> then both 'from' and 'to' need the same mod-4 alignment.
>>>> <
>>>>> Or, you have the rule that the address of the "from" instruction is
>>>>> rounded up to the nearest size used for the displacement field.
>>>>> i.e. if
>>>>> the address of the from instruction is say xxx03, and the displacement
>>>>> is scaled to 4 byte values, the the xxx03 is "rounded up" to xxx04.
>>>> <
>>>> Rounding is significantly (several gates of delay) more expensive than
>>>> truncation (free).
>>> Fair enough. I think this whole thing is a little overblown, as it
>>> really applies only to systems with byte aligned (or perhaps half word
>>> aligned without a pairing requirement) systems, which, other than X86 I
>>> think are pretty rare. If you stick with 32 bit instructions, then I
>>> think Terje's original idea is just not worth it.
>>> --
>>> - Stephen Fuld
>>> (e-mail address disguised to prevent spam)
>>
>> I agree. With 32-bit or more instructions the displacement field can
>> be large
>> enough to cover practically all branch cases. There are seldom code
>> modules
>> larger than 16MB meaning 24-bits is probably adequate.
>
> Remember, if all instructions are on 32 bit boundaries, you "gain" two
> bits of range by appending two zero bits to the displacement.  So 16MP
> only requires 14 bits, not 16.

MitchAlsup wrote:
> On Wednesday, March 1, 2023 at 2:14:22 AM UTC-6, Terje Mathisen wrote:
>> Would it be possible or just a bad idea to allow some form of
>> variable/fp encoding of branch offsets?
>>
>> I.e. all small (byte) offsets would be encoded directly, but for longer
>> ones you could require the target to be word/dword/qword aligned, and
>> therefore allow a much greater range.
>>
>> It would probably only be useful for inter-module calls/branches...
> <
> It is generally OK to place entry-points on cache line boundaries (about 64Byte
> alignments) so you get 8 low order bits (which word instruction machines
> already use the lowest 2-bits.) A gain of 6-bits.
> <
> It is generally not OK to require cache line alignment on labels within a
> subroutine.

Yeah, that was my assumption (see above), so that this would only be
applicable for OS/library interfaces, but I suspect that it is far
better to simply allow large/arbitrary sized immediates to be able to
reach wherever the target is located.
> <
> It is generally a good idea that BR and CALL use the same multiplexer
> and address generator. So, mainly my first paragraph above is in conflict
> with the leading sentence of this paragraph.
>>
>> The main problem is probably that the target address adder is already in
>> the critical path, so you can't just add a little shifter there as well.
>>
>> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of this,
>> right?)
> <
> In a pipeline microarchitecture, the added calculating branch targets is
> seldom the adder performing memory address generation.

??? I don't think I understand this paragraph?

Terje

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

EricP wrote:
> Stephen Fuld wrote:
>> On 3/1/2023 10:28 AM, EricP wrote:
>>> Stephen Fuld wrote:
>>>> On 3/1/2023 8:06 AM, EricP wrote:
>>>>> Terje Mathisen wrote:
>>>>>> Would it be possible or just a bad idea to allow some form of
>>>>>> variable/fp encoding of branch offsets?
>>>>>>
>>>>>> I.e. all small (byte) offsets would be encoded directly, but for
>>>>>> longer ones you could require the target to be word/dword/qword
>>>>>> aligned, and therefore allow a much greater range.
>>>>>>
>>>>>> It would probably only be useful for inter-module calls/branches...
>>>>>>
>>>>>> The main problem is probably that the target address adder is
>>>>>> already in the critical path, so you can't just add a little
>>>>>> shifter there as well.
>>>>>>
>>>>>> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of
>>>>>> this, right?)
>>>>>>
>>>>>> Terje
>>>>>
>>>>> As with any variable length instruction, extracting its size
>>>>> in the parse or decode stage is critical for concurrent decode.
>>>>> So ideally this offset *won't* be an "fp-like" data item with an
>>>>> "exponent" field appended to the opcode, but the instruction size
>>>>> in words is in the first byte and the internal instruction format
>>>>> is sorted out by decode.
>>>>>
>>>>> RIP-relative offsets are often relative to the incremented RIP
>>>>> and include the variable instruction's length. The alignment
>>>>> is for both the 'from' and 'to' addresses and aligning just the
>>>>> destination to 32 or 64 bits won't allow encoding a larger range.
>>>>>
>>>>> The issue I had is when instructions are not byte aligned,
>>>>> in my case 16-bit words. For branches the immediate field is a
>>>>> relative _word_ count to get one extra bit of offset range.
>>>>> But what to do when the immediate field is a 64-bit value:
>>>>> should that still be a word offset count,
>>>>> or should it switch to being a byte offset count?
>>>>>
>>>>> For LD and ST the immediate offset is always a byte offset,
>>>>> even if it is RIP-relative addressing.
>>>>>
>>>>> In my naming convention, Branch is to relative offset,
>>>>> Jump is to an absolute address.
>>>>>
>>>>> I have a "BR reg" with the offset in a register,
>>>>> intended for use in position-independent SWITCH statements.
>>>>> A scaled-indexed LD of the offset onto a register, then BR reg.
>>>>> But should that register offset be a byte count or a word count?
>>>>> Or should I have two "BR reg" instructions, one for each?
>>>>
>>>> I, perhaps mistakenly, interpreted Terje's suggestion differently.
>>>> I don't think he was suggesting variable length instructions, but an
>>>> orthogonal idea.  Let's take an example.   Suppose you have 10 bits
>>>> available for a branch offset. If the high order bit is zero, the
>>>> low order nine bits give a byte address.  But if the high order bit
>>>> is one, you get the address by appending say 3 zero bits to the low
>>>> order 9 bits, giving a possible displacement of 12 bits, but
>>>> restricted to an 8 byte aligned address.
>>>>
>>>> Of course, this idea isn't applicable to just byte aligned
>>>> instructions, though its benefit diminishes as you increase the
>>>> instruction alignment requirements.
>>>>
>>>> Whether this is a good idea or not, I don't know.
>>>
>>> Ok, I understand. So the immediate field is fixed size and has
>>> scale data type bits indicating it is a count of int8,int16,int32,
>>> and a signed offset count of those sized words.
>>
>> Yes, although I doubt you need to support all three sizes.
>
> If we have a 16-bit immediate field,
> and bit[15]==0 means bits [14:0] are a signed int8 offset count,
> and bits [15:14]==10 means int16 offset count
>
> then the 15-bit int8 count is redundant with the 14-bit int16 count.

Right, so this is obviously not feasible for a single-bit scaling.
Using 4/8/16-byte alignment makes a bit more sense. (But probably still
a bad idea.)

>
> So that prefix should select a different word size, maybe int24?
> Or just have two scale sizes, int8 and int32.
>
>>> The scale would be that of the smallest alignment of the 'from' and 'to'
>>> instructions, which is scaled up by inserting alignment NOPs before
>>> both.
>>
>> No need to align the "from" instruction.
>
> If you want the offset to be a count of int32's
> then both 'from' and 'to' need the same mod-4 alignment.
>
> That is, in order to use an int32 count as the offset then
> both BR and target instruction addresses bits [1:0] must be the same.

I did consider this and realized that for a dword-aligned target, the
source address would simply ignore any lower-order bytes and instead use
the truncated dword as the source. (Same for 8/16/32/64-byte aligned
destinations, whichever you decide that it makes sense to support.

Terje
>
>>> I suppose it depends on the size of the immediate field as to how
>>> often it would have to insert NOPs so that it can use a larger scale
>>> to bring a destination back into range.
>>
>> Yes.  And also the mimimum size of an instruction.  E.g. for CPUs with
>> 32 bit instructions, you "automatically" get a factor of four in the
>> range of the branch instructions.
>

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

Terje wrote:
>The main problem is probably that the target address adder is already in
>the critical path, so you can't just add a little shifter there as well.

It is not in a critical path if you have branch prediction, and the target address
is needed only at the end of a long pipeline.

The main problem is that you don't know if a target address in a different module
is aligned by a higher power of 2. A misalignment error will only be detected at
the link stage.

>(Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of this, right?)
The LEA instruction in x86 is implemented in the ALU, rather than the AGU in modern
processors. Sometimes, it requires 2 µops. Some old processors that have LEA in
the AGU have an extra delay because the address calculation is in a different
pipeline stage than the ALU.

Some cases of reading from a memory operand have an
extra delay if the address calculation is complex.

On Thursday, March 2, 2023 at 1:45:05 AM UTC-6, Terje Mathisen wrote:
> MitchAlsup wrote:
> > On Wednesday, March 1, 2023 at 2:14:22 AM UTC-6, Terje Mathisen wrote:
> >> Would it be possible or just a bad idea to allow some form of
> >> variable/fp encoding of branch offsets?
> >>
> >> I.e. all small (byte) offsets would be encoded directly, but for longer
> >> ones you could require the target to be word/dword/qword aligned, and
> >> therefore allow a much greater range.
> >>
> >> It would probably only be useful for inter-module calls/branches...
> > <
> > It is generally OK to place entry-points on cache line boundaries (about 64Byte
> > alignments) so you get 8 low order bits (which word instruction machines
> > already use the lowest 2-bits.) A gain of 6-bits.
> > <
> > It is generally not OK to require cache line alignment on labels within a
> > subroutine.
> Yeah, that was my assumption (see above), so that this would only be
> applicable for OS/library interfaces, but I suspect that it is far
> better to simply allow large/arbitrary sized immediates to be able to
> reach wherever the target is located.
> > <
> > It is generally a good idea that BR and CALL use the same multiplexer
> > and address generator. So, mainly my first paragraph above is in conflict
> > with the leading sentence of this paragraph.
> >>
> >> The main problem is probably that the target address adder is already in
> >> the critical path, so you can't just add a little shifter there as well.
> >>
> >> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of this,
> >> right?)
> > <
> > In a pipeline microarchitecture, the added calculating branch targets is
> > seldom the adder performing memory address generation.
<
> ??? I don't think I understand this paragraph?
<
There is an adder dedicated to branch target calculations that exists in the
DECODE stage of the pipeline. There is the data AGEN adder that exists in
the EXECUTE stage of the pipeline. You don't move logic across stage
boundaries.
<
> Terje
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

MitchAlsup wrote:
> On Thursday, March 2, 2023 at 1:45:05 AM UTC-6, Terje Mathisen wrote:
>> MitchAlsup wrote:
>>> On Wednesday, March 1, 2023 at 2:14:22 AM UTC-6, Terje Mathisen wrote:
>>>> Would it be possible or just a bad idea to allow some form of
>>>> variable/fp encoding of branch offsets?
>>>>
>>>> I.e. all small (byte) offsets would be encoded directly, but for longer
>>>> ones you could require the target to be word/dword/qword aligned, and
>>>> therefore allow a much greater range.
>>>>
>>>> It would probably only be useful for inter-module calls/branches...
>>> <
>>> It is generally OK to place entry-points on cache line boundaries (about 64Byte
>>> alignments) so you get 8 low order bits (which word instruction machines
>>> already use the lowest 2-bits.) A gain of 6-bits.
>>> <
>>> It is generally not OK to require cache line alignment on labels within a
>>> subroutine.
>> Yeah, that was my assumption (see above), so that this would only be
>> applicable for OS/library interfaces, but I suspect that it is far
>> better to simply allow large/arbitrary sized immediates to be able to
>> reach wherever the target is located.
>>> <
>>> It is generally a good idea that BR and CALL use the same multiplexer
>>> and address generator. So, mainly my first paragraph above is in conflict
>>> with the leading sentence of this paragraph.
>>>>
>>>> The main problem is probably that the target address adder is already in
>>>> the critical path, so you can't just add a little shifter there as well.
>>>>
>>>> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of this,
>>>> right?)
>>> <
>>> In a pipeline microarchitecture, the added calculating branch targets is
>>> seldom the adder performing memory address generation.
> <
>> ??? I don't think I understand this paragraph?
> <
> There is an adder dedicated to branch target calculations that exists in the
> DECODE stage of the pipeline. There is the data AGEN adder that exists in
> the EXECUTE stage of the pipeline. You don't move logic across stage
> boundaries.

OK, that makes sense. It was the small typo where you wrote "the added
calculating branch targets" which I now understand should have been "the
adder calculating..." which caused my confusion.

Terje

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

Agner Fog <agfo@dtu.dk> schrieb:
> Terje wrote:
>>The main problem is probably that the target address adder is already in
>>the critical path, so you can't just add a little shifter there as well.
>
> It is not in a critical path if you have branch prediction, and the target address
> is needed only at the end of a long pipeline.
>
> The main problem is that you don't know if a target address in a different module
> is aligned by a higher power of 2. A misalignment error will only be detected at
> the link stage.

That can be addressed in the ABI prescribing the alignment of functions
in general.

It would also be possible to prescribe different alignment for internal
and external functions, to save space. But that would have to adddress
the question of call via function pointers (e.g. a vtab). And
if the compiler does devirtualization... that can get messy.

On Thursday, March 2, 2023 at 11:39:30 PM UTC-7, Thomas Koenig wrote:
> Agner Fog <ag...@dtu.dk> schrieb:
> > Terje wrote:
> >>The main problem is probably that the target address adder is already in
> >>the critical path, so you can't just add a little shifter there as well..
> >
> > It is not in a critical path if you have branch prediction, and the target address
> > is needed only at the end of a long pipeline.
> >
> > The main problem is that you don't know if a target address in a different module
> > is aligned by a higher power of 2. A misalignment error will only be detected at
> > the link stage.
> That can be addressed in the ABI prescribing the alignment of functions
> in general.
>
> It would also be possible to prescribe different alignment for internal
> and external functions, to save space. But that would have to adddress
> the question of call via function pointers (e.g. a vtab). And
> if the compiler does devirtualization... that can get messy.

Of course, in the typical case which I've seen actually existing in the
wild, this issue simply does not arise.

There is the short form of branch, which is 16 bits long, and contains
an 8-bit relative offset. This is a multiple of 16 bits, since instructions
are aligned on 16 bit boundaries, as it's important not to waste bits
in such a short address.

There is the long form of branch, which is 32 bits long. There is a
16-bit address field in the instruction. This is in bytes; the last bit is
therefore wasted, this is for consistency with all other memory
reference instructions, where the address field is also in bytes.

Obviously, all jumps to external addresses must be in the long form.

Attempts to... basically recompile programs in the link stage... are
a bad idea, I would think. Of course, some new advanced architecture
might do things differently from traditional ones.

John Savard

On 3/1/2023 12:44 PM, MitchAlsup wrote:
> On Wednesday, March 1, 2023 at 10:06:45 AM UTC-6, EricP wrote:
>> Terje Mathisen wrote:
>>> Would it be possible or just a bad idea to allow some form of
>>> variable/fp encoding of branch offsets?
>>>
>>> I.e. all small (byte) offsets would be encoded directly, but for longer
>>> ones you could require the target to be word/dword/qword aligned, and
>>> therefore allow a much greater range.
>>>
>>> It would probably only be useful for inter-module calls/branches...
>>>
>>> The main problem is probably that the target address adder is already in
>>> the critical path, so you can't just add a little shifter there as well.
>>>
>>> (Even though LEA r1,[r2+8*r3+0x12345678] is already doing some of this,
>>> right?)
>>>
>>> Terje
>> As with any variable length instruction, extracting its size
>> in the parse or decode stage is critical for concurrent decode.
>> So ideally this offset *won't* be an "fp-like" data item with an
>> "exponent" field appended to the opcode, but the instruction size
>> in words is in the first byte and the internal instruction format
>> is sorted out by decode.
>>
>> RIP-relative offsets are often relative to the incremented RIP
>> and include the variable instruction's length. The alignment
>> is for both the 'from' and 'to' addresses and aligning just the
>> destination to 32 or 64 bits won't allow encoding a larger range.
>>
>> The issue I had is when instructions are not byte aligned,
>> in my case 16-bit words. For branches the immediate field is a
>> relative _word_ count to get one extra bit of offset range.
>> But what to do when the immediate field is a 64-bit value:
>> should that still be a word offset count,
>> or should it switch to being a byte offset count?
> <
> Item 1
>>
>> For LD and ST the immediate offset is always a byte offset,
>> even if it is RIP-relative addressing.
>>
>> In my naming convention, Branch is to relative offset,
>> Jump is to an absolute address.
>>
>> I have a "BR reg" with the offset in a register,
>> intended for use in position-independent SWITCH statements.
>> A scaled-indexed LD of the offset onto a register, then BR reg.
>> But should that register offset be a byte count or a word count?
>> Or should I have two "BR reg" instructions, one for each?
> <
> I agree that Branches should be to displacements (IP = IP+DISP)
> I agree that JUMPs should be to absolute locations (IP = value)
> <
> The timing in the pipeline where reg becomes available is in conflict
> with the time when the next fetch address is needed. Reading and
> forwarding take significantly longer than IP+DISP calculation. So,
> this typically adds 1 cycle of delay to BR reg forms.
> <
> Item 1::
> <
> My BR and CALL instructions have a 2^28-bit range from 26-bit
> displacement.
> But when I switch to the forms with constants, I switch to
> absolute addressing.

My BRA and BSR instructions are 20 bits (relative).
There are also absolute-48 bit versions (64-bit encoding).

Technically, there are also relative 33 bit branches (also a 64-bit
encoding), but these will be skipped by the branch predictor (and thus
slower than either the Disp20 or Abs48 encodings). These will need to
always take the "slow path" (via the AGU and explicit branch mechanism).

In my case, branch displacements are always in terms of 16 bit units.
Abs48 gives a byte address, but currently the LSB is effectively MBZ
(and the instruction stream has a mandatory 16-bit alignment).

In my case:
BRA disp
Is handled by the branch predictor (in ID1), and has 2 cycle of latency.

Avoiding the latency cycle would require handling branch prediction
during the IF stage.

Most conditional branches depend on whether or not the predictor
predicts them, etc. Branches will be skipped by the branch predictor if
they cross a 16 MB boundary (mostly because an adder and carry
propagation across 24 bits is faster than 48 bits).

The 'RTS' instruction (decoded as 'JMP LR'), along with 'JMP R1' are
treated as special cases by the branch predictor (the relevant registers
are fed into it via a side-channel). These will be skipped if the
register encodes a branch into a different operating mode (or if the
register's value was being modified by the EX stages).

At present, all the LR style values are encoded in Inter-ISA form (LSB
set with mode bits in the high part of the register), mostly so that
branches between function pointers in different ISA modes will work as
expected. The branch predictor verifies that the target mode matches the
current mode.

Note that 'JMP R1' is special, in that previously is assumed "LR
semantics" (always assume that the register is Inter-ISA, ignoring the
LSB), but now both implicitly require the LSB to be set (partly as a
"lint" feature; If the LSB is not set it likely means the LR value has
been corrupted).

For things like function pointers, the LSB would also be set and the
mode bits are encoded in the high order bits, partly as a way to
potentially allow function pointers to be shared between the base ISA
and XG2 modes.

There is also a possible future where the compiler can mix the ISA modes
on a per-function basis. Well, apart from the issue that 'BSR Disp20'
can't encode Inter-ISA cases, which would require effectively generating
a function pointer to the target and then calling through this, if the
modes differed. At present, BGBCC only generates binaries for a single
ISA mode (apart from its limited ability to encode RISC-V fragments).

If the branch predictor does predict a branch, the operation for the
following cycle is also automatically marked as flushed (if there is a
branch mispredict, it is needed to initiate a branch to the following
instruction, so it having been preemptively flushed has no visible
effect in this case).

All other branches will take the slower path, having their address
calculated by the AGU, and then dispatched via the EX1 and EX2 stages
(taking around 8 clock cycles). The branch is signaled in EX1, but the
branch mechanism doesn't really start to take action until EX2, mostly
for timing/latency reasons. The mechanism effectively invalidates
anything currently in the pipeline following the branch, then signals
the L1 I$ to start fetching from a new location (crossing back through
the branch-predictor and then to the L1 I-cache).

....