On Friday, March 3, 2023 at 12:32:06 PM UTC-6, BGB wrote:
> 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.
<
I scan ahead looking for branches as instructions fill the inst-buffer.
This gives me time to fetch the targets of the branches often before
the branch is decoded, leading to zero-delay in many cases (BR at end
of basic block), but averaging 1.03-cycles over all branches. Thus,
a delay slot does not buy enough to enter consideration.
>
> 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).
<
Predicate instructions are not predicted in my ISA.
LOOP instructions are not predicted ...
BR and CALL and RET and EXIT are not predicted.
only real conditional branches that stand to gain something are predicted.
<snip>
>
> 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).
<
This sounds like a source of cycles that end up doing noting positive to the
application running.....
>
> ...

> 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.

So... floating point branches?

Quadibloc <jsavard@ecn.ab.ca> schrieb:
> 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.

What does "in the wild" actually mean?

> 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.

For architectures which have that, yes. For RISC architectures,
usually instructions are situated on mutliples of four bytes.
But they don't usually have eight-bit offsets, either, which would
make little sense in a 32-bit instruction format.

> 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.

I'm not sure what you which architecture you are referring to.

> 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.

Have you heard of LTO?

> Of course, some new advanced architecture
> might do things differently from traditional ones.

Old-style RISC is pretty traditional, I would think.

On 3/3/2023 3:01 PM, MitchAlsup wrote:
> On Friday, March 3, 2023 at 12:32:06 PM UTC-6, BGB wrote:
>> 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.
> <
> I scan ahead looking for branches as instructions fill the inst-buffer.
> This gives me time to fetch the targets of the branches often before
> the branch is decoded, leading to zero-delay in many cases (BR at end
> of basic block), but averaging 1.03-cycles over all branches. Thus,
> a delay slot does not buy enough to enter consideration.

There are no delay-slot instructions.

But, there is a "dead cycle" following every branch where a delay slot
could have existed, and if there was not a mechanism to flush this
location, a delay-slot would magically appear.

Some amount of the "boot time sanity checks" were specifically checking
to make sure delay-slot like effects were not happening. Another
long-standing bug itself turned out to be related to a related effect
(namely, flushed instructions were incorrectly generating interlock
stalls and fouling up the branch mechanism).

Though, a few of the ancestor/inspiration ISAs, namely SH-4 and TMS320,
did have branch delay slots.

>>
>> 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).
> <
> Predicate instructions are not predicted in my ISA.
> LOOP instructions are not predicted ...
> BR and CALL and RET and EXIT are not predicted.
> only real conditional branches that stand to gain something are predicted.
> <snip>

The branch predictor is basically functioning as a general purpose
"early branch handler", so deals with both conditional and unconditional
branches (treating unconditional branches as "assume always taken").

There are limits to what it can handle though.

If it is an unknown type of branch or if it crosses a 16MB boundary or
similar, it throws up its hands and lets the slow path deal with it. The
slow path also takes over whenever the branch predictor also guesses a
branch wrong.

Effectively, the address output of the branch predictor looks sort of like:
Addr[47:24] = PC[47:24]
Addr[23: 1] = PC[23: 1] + Disp
Addr[ 0] = 0

Where it uses the carry output from the adder to determine whether or
not to use its predicted address (if it can't be handled with a
bit-slice, the branch predictor opts-out).

>>
>> 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).
> <
> This sounds like a source of cycles that end up doing noting positive to the
> application running.....

Ideally, one wants to avoid slow-path branches.

So, some examples:
Fast Path (~ 2c):
BRA Disp8 //16-bit
BT Disp8 //16-bit
BF Disp8 //16-bit
BRA Disp20
BSR Disp20
BT Disp20
BF Disp20
Bxx Rn, Disp8 {BEQ/BNE/BLT/BGE/BLE/BGT}
BRA Abs48 //64-bit
BSR Abs48 //64-bit
RTS
JMP R1
Slow Path (~ 8c):
JMP Rn // Rn => PC
JSR Rn // PC => LR; Rn => PC
BRAF Rn // (PC, Rn) => PC
BSRF Rn // PC => LR; (PC, Rn) => PC
BRA Disp33 //64-bit
BSR Disp33 //64-bit

The fast-path cases represent the vast majority of branch instructions.

Main reason Abs48 is in the fast path is mostly because handling it does
not require a carry-chain (whereas Disp33 would require carry across the
full 48 bits; so is left for the slow path).

Generally, the AGU also deals with Addr48+Disp33 cases (though the
Disp33 effectively expands to 36-bits due to the 1/2/4/8 scale).

On Friday, March 3, 2023 at 2:37:44 PM UTC-7, Thomas Koenig wrote:
> Quadibloc <jsa...@ecn.ab.ca> schrieb:

> > 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.
>
> I'm not sure what you which architecture you are referring to.

One example of this is the TI 9900 chip.

I think the original PDP-11 is another example.

John Savard

It appears that Quadibloc <jsavard@ecn.ab.ca> said:
>On Friday, March 3, 2023 at 2:37:44 PM UTC-7, Thomas Koenig wrote:
>> Quadibloc <jsa...@ecn.ab.ca> schrieb:
>
>> > 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.
>>
>> I'm not sure what you which architecture you are referring to.

On S/360, branch addreesses are computed the same way as any other
address, but instructions are halfword (16 bit) aligned so the low bit
in the displacement is wasted. S/390 finally added relative branches
where the operand is a 16 or 32 bit value that is shifted one bit to
the left, so there's no wasted address bit. Since it had 32 bit
addressing, the long relative branch could branch anywhere. zSeries
expanded addresses to 64 bits but the relative branch instructions
stayed the same.

The PDP-11 had a full set of conditional and unconditional branches
which contained an 8-bit signed offset, shifted one bit since
instructions were 16-bit word aligned. It also had JMP and JSR
instructions that had the regular address modes including absolute
addresses or 16 bit index offset.

The Unix PDP-11 assemblers had conditional jump pseudo instructions
that would turn into a branch if the target was close enough, a
reverse branch over a jump otherwise. There were a few papers on how
to generate the code; the usual one was to start by assuming all the
jumps were in the long form, then loop looking for one it could
shorten, adjust the instruction addressess, repeat until done.

An obvious improvement is to chain branches, look for a jump to the
same address that is close enough for a short branch to that jump.
Unforunately, that turned out to be NP-complete.

--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

On Friday, March 3, 2023 at 8:56:07 PM UTC-6, John Levine wrote:
> It appears that Quadibloc <jsa...@ecn.ab.ca> said:
> >On Friday, March 3, 2023 at 2:37:44 PM UTC-7, Thomas Koenig wrote:
> >> Quadibloc <jsa...@ecn.ab.ca> schrieb:
> >
> >> > 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.
> >>
> >> I'm not sure what you which architecture you are referring to.
> On S/360, branch addreesses are computed the same way as any other
> address, but instructions are halfword (16 bit) aligned so the low bit
> in the displacement is wasted. S/390 finally added relative branches
> where the operand is a 16 or 32 bit value that is shifted one bit to
> the left, so there's no wasted address bit. Since it had 32 bit
> addressing, the long relative branch could branch anywhere. zSeries
> expanded addresses to 64 bits but the relative branch instructions
> stayed the same.
>
> The PDP-11 had a full set of conditional and unconditional branches
> which contained an 8-bit signed offset, shifted one bit since
> instructions were 16-bit word aligned. It also had JMP and JSR
> instructions that had the regular address modes including absolute
> addresses or 16 bit index offset.
>
> The Unix PDP-11 assemblers had conditional jump pseudo instructions
> that would turn into a branch if the target was close enough, a
> reverse branch over a jump otherwise. There were a few papers on how
> to generate the code; the usual one was to start by assuming all the
> jumps were in the long form, then loop looking for one it could
> shorten, adjust the instruction addressess, repeat until done.
<
In effect, the Mc88K link process worked just like this--assume the
branch displacement was not big enough, and have the linker shrink
the code when it was long enough. Shrinking means that already resolved
branch targets would not change when a shrink occurred.
>
> An obvious improvement is to chain branches, look for a jump to the
> same address that is close enough for a short branch to that jump.
> Unforunately, that turned out to be NP-complete.
<
And it is so rare to find a subroutine with more than 65K instructions
in it that the complexity is unwarranted.
>
>
>
> --
> Regards,
> John Levine, jo...@taugh.com, Primary Perpetrator of "The Internet for Dummies",
> Please consider the environment before reading this e-mail. https://jl.ly

>And it is so rare to find a subroutine with more than 65K instructions
>in it that the complexity is unwarranted.

The PC increment does not need to increment many more than 16 of the LSBs.
PC lowest 20 bits could be incremented / adjusted by branch instructions while
the remaining upper bits remain unchanged. 65C816 only increments across the
16 LSBs. It is tempting to just load 16 bits of the branch target field directly into
the low order 16 bits of the PC, ignoring the upper bits. It would save an adder.
It could be done if routines were always packed entirely in a 64kB space.
Positioning of code would need to be limited to 64kB blocks for PIC. Thor2023
just happens to be using 64kB memory pages.

Thor2023 is using a branch target buffer accessed in the IFETCH stage to do branch
predictions. Next a branch predictor in the decode stage can override the target
buffer prediction. Finally, a perceptron predictor may be used from the execute stage.

Radically altered branches for Thor2023. Decided to use fused compare-and-branch
instead of a separate compare preceding the branch. Too many bits were being
wasted on the branch displacement, when it was possible instead to include a
second register spec. The displacement bits are reduced to 16 from 24 and a six
bit register spec added. In addition to RR branches, RI branches are also supported
now. There was enough room for an eight-bit immediate in the branch instruction;
larger immediates can also be compared using postfix immediate values.

Unconditional branches have had their range extended by four address bits to
128MB (28-bits).

Memory indirect branching using tables is now in the ISA.

On 3/3/2023 1:27 PM, mac wrote:
>> 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.
>
> So... floating point branches?

Only by a very strained definition of "floating point", as there are no
non-integer branch displacements, and what you might call the "exponent"
can only have two values, and they are not "consecutive" powers of two,
and, of course, no signed values. But other than those . . . :-)

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

Stephen Fuld wrote:
> On 3/3/2023 1:27 PM, mac wrote:
>>> 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.
>>
>> So... floating point branches?
>
> Only by a very strained definition of "floating point", as there are no
> non-integer branch displacements, and what you might call the "exponent"
> can only have two values, and they are not "consecutive" powers of two,
> and, of course, no signed values.  But other than those  . . .  :-)

Signed is obviously OK, we want to be able to branch in both directions!

Otherwise you are spot on. :-)

My idea was really based on using a different ABI for
exported/public/intermodule targets, so that these would always have to
be generated with the required alignment (probably 8 or 16 bytes as the
most feasible), then getting a similarly extended addressing range for
code that needs to reach them without using a full 64-bit address.

I still don't think it would be a net win anywhere but if you only
expose the ideas that you are sure to be a win, then you won't get any
external opinions, like I'm getting here. :-)

Terje

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

On 3/4/2023 1:37 AM, Terje Mathisen wrote:
> Stephen Fuld wrote:
>> On 3/3/2023 1:27 PM, mac wrote:
>>>> 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.
>>>
>>> So... floating point branches?
>>
>> Only by a very strained definition of "floating point", as there are
>> no non-integer branch displacements, and what you might call the
>> "exponent" can only have two values, and they are not "consecutive"
>> powers of two, and, of course, no signed values.  But other than
>> those  . . .  :-)
>
> Signed is obviously OK, we want to be able to branch in both directions!

Of course. Sorry, I got carried away. :-)

>
> Otherwise you are spot on. :-)
>
> My idea was really based on using a different ABI for
> exported/public/intermodule targets, so that these would always have to
> be generated with the required alignment (probably 8 or 16 bytes as the
> most feasible), then getting a similarly extended addressing range for
> code that needs to reach them without using a full 64-bit address.
>
> I still don't think it would be a net win anywhere but if you only
> expose the ideas that you are sure to be a win, then you won't get any
> external opinions, like I'm getting here. :-)

I agree with both of those points. :-)

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

On Friday, March 3, 2023 at 9:24:11 PM UTC-7, MitchAlsup wrote:
> On Friday, March 3, 2023 at 8:56:07 PM UTC-6, John Levine wrote:

> > An obvious improvement is to chain branches, look for a jump to the
> > same address that is close enough for a short branch to that jump.
> > Unforunately, that turned out to be NP-complete.

> And it is so rare to find a subroutine with more than 65K instructions
> in it that the complexity is unwarranted.

Um, this would apply to the case of subroutines with more than 256
instructions.

It would be _very_ rare to find a routine with more than 65,536 instructions
(each at least 16 bits in size) in it on a PDP-11 simply because its address
space (except for high-end models with special memory extension hardware)
was 65,536 bytes.

John Savard

According to Terje Mathisen <terje.mathisen@tmsw.no>:
>My idea was really based on using a different ABI for
>exported/public/intermodule targets, so that these would always have to
>be generated with the required alignment (probably 8 or 16 bytes as the
>most feasible), then getting a similarly extended addressing range for
>code that needs to reach them without using a full 64-bit address.

I've seen ABIs where public routines have to be word aligned and there
is stuff before the routine to help with debugging, e.g., routine name
and argument signature.

I agree that it's not worth an instruction format. In normal code,
external calls should be less common than internal ones, so it's not a
big deal if their encoding is bigger.

--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

According to Quadibloc <jsavard@ecn.ab.ca>:
>On Friday, March 3, 2023 at 9:24:11 PM UTC-7, MitchAlsup wrote:
>> On Friday, March 3, 2023 at 8:56:07 PM UTC-6, John Levine wrote:
>
>> > An obvious improvement is to chain branches, look for a jump to the
>> > same address that is close enough for a short branch to that jump.
>> > Unforunately, that turned out to be NP-complete.
>
>> And it is so rare to find a subroutine with more than 65K instructions
>> in it that the complexity is unwarranted.
>
>Um, this would apply to the case of subroutines with more than 256
>instructions.

Right.

>It would be _very_ rare to find a routine with more than 65,536 instructions
>(each at least 16 bits in size) in it on a PDP-11 simply because its address
>space (except for high-end models with special memory extension hardware)
>was 65,536 bytes.

Even on the high end models, each process only had 16 bit addresses.
The operating system could use all that memory to map multiple
processes but there was no reasonable way to put more than 64K code
and 64K data in one process.

--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

On Saturday, March 4, 2023 at 10:07:34 AM UTC-6, John Levine wrote:
> According to Quadibloc <jsa...@ecn.ab.ca>:
> >On Friday, March 3, 2023 at 9:24:11 PM UTC-7, MitchAlsup wrote:
> >> On Friday, March 3, 2023 at 8:56:07 PM UTC-6, John Levine wrote:
> >
> >> > An obvious improvement is to chain branches, look for a jump to the
> >> > same address that is close enough for a short branch to that jump.
> >> > Unforunately, that turned out to be NP-complete.
> >
> >> And it is so rare to find a subroutine with more than 65K instructions
> >> in it that the complexity is unwarranted.
> >
> >Um, this would apply to the case of subroutines with more than 256
> >instructions.
> Right.
> >It would be _very_ rare to find a routine with more than 65,536 instructions
> >(each at least 16 bits in size) in it on a PDP-11 simply because its address
> >space (except for high-end models with special memory extension hardware)
> >was 65,536 bytes.
> Even on the high end models, each process only had 16 bit addresses.
<
But there was separate code and data spaces of 16-bits each.
<
Also note: the OS in one pair of 16-bit address spaces could access the
code and data in another pair of address spaces using read-from and
write-to instructions (possible after setting up some address space
controls points.)
<
> The operating system could use all that memory to map multiple
> processes but there was no reasonable way to put more than 64K code
> and 64K data in one process.
> --
> Regards,
> John Levine, jo...@taugh.com, Primary Perpetrator of "The Internet for Dummies",
> Please consider the environment before reading this e-mail. https://jl.ly

According to MitchAlsup <MitchAlsup@aol.com>:
>> Even on the high end models, each process only had 16 bit addresses.
><
>But there was separate code and data spaces of 16-bits each.

Yes.

>Also note: the OS in one pair of 16-bit address spaces could access the
>code and data in another pair of address spaces using read-from and
>write-to instructions (possible after setting up some address space
>controls points.)

Yes, but it wasn't that useful. The 11/45 had three modes, kernel,
supervisor, and user, and instructions move to/from previous
instruction/data space which the kernel used to manage the user space.
You couldn't use it from one user process to another.

when I was at Yale, we had some early bitmap terminals. I first did a
hack to map your screen memory into the high half of your process data
space, but it was pretty painful to lose that much address space. Unix
didn't use the supervisor mode so I came up with a hack to put the
screen memory into the supervisor data space, then set the previous
mode in user programs to be supervisor, and it worked. MFPD and MTPD
instructions read and wrote screen memory directly. C didn't generate
those instructions but a little assembler library did the trick and
was plenty fast for the stuff we were doing.

--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

On Saturday, March 4, 2023 at 2:10:56 PM UTC-6, John Levine wrote:
> According to MitchAlsup <Mitch...@aol.com>:
> >> Even on the high end models, each process only had 16 bit addresses.
> ><
> >But there was separate code and data spaces of 16-bits each.
> Yes.
> >Also note: the OS in one pair of 16-bit address spaces could access the
> >code and data in another pair of address spaces using read-from and
> >write-to instructions (possible after setting up some address space
> >controls points.)
<
> Yes, but it wasn't that useful. The 11/45 had three modes, kernel,
> supervisor, and user, and instructions move to/from previous
> instruction/data space which the kernel used to manage the user space.
> You couldn't use it from one user process to another.
<
That is why the first sentence of the above paragraph started "the OS in".
Nowhere did I imply that applications could perform those instructions.
>
> when I was at Yale, we had some early bitmap terminals. I first did a
> hack to map your screen memory into the high half of your process data
> space, but it was pretty painful to lose that much address space. Unix
> didn't use the supervisor mode so I came up with a hack to put the
> screen memory into the supervisor data space, then set the previous
> mode in user programs to be supervisor, and it worked. MFPD and MTPD
> instructions read and wrote screen memory directly. C didn't generate
> those instructions but a little assembler library did the trick and
> was plenty fast for the stuff we were doing.
<
Cute, but only works with 1 terminal......
> --
> Regards,
> John Levine, jo...@taugh.com, Primary Perpetrator of "The Internet for Dummies",
> Please consider the environment before reading this e-mail. https://jl.ly

>That is why the first sentence of the above paragraph started "the OS in".
>Nowhere did I imply that applications could perform those instructions.

Well, actually, they could, although in the absence of my hack, they
weren't useful because the previous and current address space were the
same.

>> when I was at Yale, we had some early bitmap terminals. I first did a
>> hack to map your screen memory into the high half of your process data
>> space, but it was pretty painful to lose that much address space. Unix
>> didn't use the supervisor mode so I came up with a hack to put the
>> screen memory into the supervisor data space, then set the previous
>> mode in user programs to be supervisor, and it worked. MFPD and MTPD
>> instructions read and wrote screen memory directly. C didn't generate
>> those instructions but a little assembler library did the trick and
>> was plenty fast for the stuff we were doing.
><
>Cute, but only works with 1 terminal......

No, it worked with all 16 terminals. I added a line to the process
switch code so the supervisor addresses pointed to the right chunk of
screen memory for the current process.

--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

MitchAlsup wrote:
[snip]
> 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.

Using the additional low bits of the more aligned form for most
significant bits (or a segment indicator??) would allow the
addition of intermediate bits to be the same for both instruction
types. The conditional (based on instruction type) masking of
those bits would presumably not add that much delay and the carry
propagation delay (and likely delayed use of the most significant
bits of the result) could cover some time for moving the bits.

(The low bits might also be used as non-address data, perhaps a
permission request? This would seem to eliminate timing issues, at
least if those first bits were a carry chunk [the carry could be
set as zero early], and there would be no difference in the upper
part of the address generator.)

Regardless of the method of providing more aligned targets,
whether the additional complexity and delay are worthwhile would
seem to depend on the benefits from the additional alignment
relative to the costs. I suspect the benefit does not justify the
complexity. (I _think_ XTensa had variable alignment calls, so
there may be some cases where it is worthwhile.)

On Wednesday, March 1, 2023 at 3:14:22 AM UTC-5, 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
>

The 68000 had a 16 bit conditional branch, 8 bits of which were a signed offset for the branch target.
Annoyingly, it was a byte offset, so 1 bit was wasted because branching to an odd address is not
allowed (instructions are in multiples of 16 bits).
The 68020 added longer offsets by using the values (I think) of -1 and -3 in the branch offset to flag
that one or two words came after the instruction that were used for the branch offset.

I had an idea (I'm pretty sure it is not original) of using the following encoding for offsets/immediates:
Allocate an initial value (8 bits, 4 bits, whatever) in your instruction.
If the high bit is zero, the rest of the bits are you value (signed or unsigned, as is appropriate).
If the high bit is one, and the next bit is zero, one additional "chunk" (Instruction addressing granularity
of the ISA) is added. The resulting value is a concatenation of the chunk and the remaining value
bits in the initial value. Additional chunk values can be added by simple extension.

So, using the x86 as an example:
JC label
the opcode is (whatever, say 0x41 for now, I don't feel like looking it up)..
The offset takes up 1 byte if it is within +-63 (ish) bytes, and is encoded as 0b0xxxxxxx (where x bits are the offset value).
The offset takes up 2 bytes if it is within +-8K(ish) bytes, and is encoded as 0xb10xxxxxx xxxxxxxx (2 bytes of offset, 14 bits of offset value).
The offset takes up 3 bytes if it is within +1M(ish) bytes, and is encoded as 0xb110xxxxx xxxxxxxx xxxxxxxx (3 bytes, 21 bits of offset value).
etc.

If the x86 had adopted such a scheme initially, a lot of 6 byte jumps would just be 3 bytes.

The same scheme could be applied to addressing offsets & immediates.
For addressing offsets, you could also get a boost by saying that if it is just a small offset (the initial value in the instruction)
it is automatically scaled by the type size of the thing you are addressing.. If you want a byte offset using the
longer version. Again, this would compact code quite a bit because most things these days are type size aligned.

Note, I have no idea how much this complicates the instruction decoder, but the first encoded value
could be near the front of the instruction so the length decoding could happen early.

Also, this obviously has problems if there are two such values in the instruction, e.g.:
MOV Word Ptr [BP+offset], imm

- Tim

On Wednesday, March 15, 2023 at 9:07:53 AM UTC-5, Timothy McCaffrey wrote:
> On Wednesday, March 1, 2023 at 3:14:22 AM UTC-5, 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
> >
> The 68000 had a 16 bit conditional branch, 8 bits of which were a signed offset for the branch target.
> Annoyingly, it was a byte offset, so 1 bit was wasted because branching to an odd address is not
> allowed (instructions are in multiples of 16 bits).
> The 68020 added longer offsets by using the values (I think) of -1 and -3 in the branch offset to flag
> that one or two words came after the instruction that were used for the branch offset.
>
> I had an idea (I'm pretty sure it is not original) of using the following encoding for offsets/immediates:
> Allocate an initial value (8 bits, 4 bits, whatever) in your instruction.
> If the high bit is zero, the rest of the bits are you value (signed or unsigned, as is appropriate).
> If the high bit is one, and the next bit is zero, one additional "chunk" (Instruction addressing granularity
> of the ISA) is added. The resulting value is a concatenation of the chunk and the remaining value
> bits in the initial value. Additional chunk values can be added by simple extension.
>
> So, using the x86 as an example:
> JC label
> the opcode is (whatever, say 0x41 for now, I don't feel like looking it up).
> The offset takes up 1 byte if it is within +-63 (ish) bytes, and is encoded as 0b0xxxxxxx (where x bits are the offset value).
> The offset takes up 2 bytes if it is within +-8K(ish) bytes, and is encoded as 0xb10xxxxxx xxxxxxxx (2 bytes of offset, 14 bits of offset value).
> The offset takes up 3 bytes if it is within +1M(ish) bytes, and is encoded as 0xb110xxxxx xxxxxxxx xxxxxxxx (3 bytes, 21 bits of offset value).
> etc.
>
> If the x86 had adopted such a scheme initially, a lot of 6 byte jumps would just be 3 bytes.
>
> The same scheme could be applied to addressing offsets & immediates.
> For addressing offsets, you could also get a boost by saying that if it is just a small offset (the initial value in the instruction)
> it is automatically scaled by the type size of the thing you are addressing. If you want a byte offset using the
> longer version. Again, this would compact code quite a bit because most things these days are type size aligned.
>
> Note, I have no idea how much this complicates the instruction decoder, but the first encoded value
> could be near the front of the instruction so the length decoding could happen early.
>
> Also, this obviously has problems if there are two such values in the instruction, e.g.:
> MOV Word Ptr [BP+offset], imm
<
Why??
<
r8_erf: ; @r8_erf
; %bb.0:
add sp,sp,#-128
std #4614300636657501161,[sp,88] // a[0]
std #4645348406721991307,[sp,104] // a[2]
std #4659275911028085274,[sp,112] // a[3]
std #4595861367557309218,[sp,120] // a[4]
std #4599171895595656694,[sp,40] // p[0]
std #4593699784569291823,[sp,56] // p[2]
std #4580293056851789237,[sp,64] // p[3]
std #4559215111867327292,[sp,72] // p[4]
std #4580359811580069319,[sp,80] // p[4]
std #4612966212090462427,[sp] // q[0]
std #4602930165995154489,[sp,16] // q[2]
std #4588882433176075751,[sp,24] // q[3]
std #4567531038595922641,[sp,32] // q[4]
Although nothing prevented the address mode to use longer displacements.
The //s are my comments to myself, but in this case name the constant.
<
Nothing is preventing::
std #4614300636657501161,[ip,ri<<3,.L__const.r8_erf.c]
>
> - Tim