Thomas Koenig wrote:

> MitchAlsup <mitchalsup@aol.com> schrieb:
>
> #include <stdint.h>

> uint32_t div25 (uint32_t n)
> {
> return n / 25;
> }

> yields

> div25:
> lis 9,0x51eb // cycle 1
> ori 9,9,0x851f // cycle 2
> mulhwu 3,3,9 // cycle 3-6
> srwi 3,3,3 // cycle 7
> blr // cycle 8

div25:
CARRY R8,{{O}} // cycle 1
MUL R1,R1,#0x51eb851f // cycle 1-4
SLL R1,R8,#35 // cycle 5
RET // cycle 6

Thomas Koenig wrote:

> MitchAlsup <mitchalsup@aol.com> schrieb:
>> Paul A. Clayton wrote:
>>
>>> On 12/7/23 1:55 PM, MitchAlsup wrote:

>>>>> What about multiply-high-no-carry-in?
>>>>
>>>>       CARRY   R9,{{O}}    // carry applies to next inst
>>>>                           // no carry in yes carry out
>>>>       MUL     R10,Rx,Ry   // {R9,R10} contain result
>>
>>> I was thinking of a single register result.
>>
>> How can a single 64-bit register hold a 128-bit result ??

> Sometimes, you don't need the whole result; the upper bits suffice.

> Consider dividing a 32-bit unsigned number n on a 32-bit system
> by 25 (equally applicable to similar examples with 64-bit systems,
> but I happen to have the numbers at hand).

> In plain C, you could do this by

> uint32_t res = ((uint64_t) n * (uint64_t) 1374389535) >> 35;

This only gives you 29 bits of significance.

What if you also need the remainder ??

MitchAlsup <mitchalsup@aol.com> schrieb:
> Thomas Koenig wrote:
>
>> MitchAlsup <mitchalsup@aol.com> schrieb:
>>> Paul A. Clayton wrote:
>>>
>>>> On 12/7/23 1:55 PM, MitchAlsup wrote:
>
>>>>>> What about multiply-high-no-carry-in?
>>>>>
>>>>>       CARRY   R9,{{O}}    // carry applies to next inst
>>>>>                           // no carry in yes carry out
>>>>>       MUL     R10,Rx,Ry   // {R9,R10} contain result
>>>
>>>> I was thinking of a single register result.
>>>
>>> How can a single 64-bit register hold a 128-bit result ??
>
>> Sometimes, you don't need the whole result; the upper bits suffice.
>
>> Consider dividing a 32-bit unsigned number n on a 32-bit system
>> by 25 (equally applicable to similar examples with 64-bit systems,
>> but I happen to have the numbers at hand).
>
>> In plain C, you could do this by
>
>> uint32_t res = ((uint64_t) n * (uint64_t) 1374389535) >> 35;
>
> This only gives you 29 bits of significance.

Because that's all it takes, dividing by 25 reduces the number
of significant bits.

> What if you also need the remainder ??

Multiply and subtract.

MitchAlsup <mitchalsup@aol.com> schrieb:
> Thomas Koenig wrote:
>
>> MitchAlsup <mitchalsup@aol.com> schrieb:
>>
>> #include <stdint.h>
>
>> uint32_t div25 (uint32_t n)
>> {
>> return n / 25;
>> }
>
>> yields
>
>> div25:
>> lis 9,0x51eb // cycle 1
>> ori 9,9,0x851f // cycle 2
>> mulhwu 3,3,9 // cycle 3-6
>> srwi 3,3,3 // cycle 7
>> blr // cycle 8
>
> div25:
> CARRY R8,{{O}} // cycle 1
> MUL R1,R1,#0x51eb851f // cycle 1-4
> SLL R1,R8,#35 // cycle 5
> RET // cycle 6

Then let's use a 64-bit example:

#include <stdint.h>

uint64_t div (uint64_t n)
{ return n / 37;
}

which becomes

div:
..LFB0:
.cfi_startproc
movabsq $-2492803253203993461, %rax
mulq %rdi
movq %rdx, %rax
shrq $5, %rax
ret

on x86_64 (so, use the high result only and shift it five bits to
the right) and, with Power10,

div:
pli 10,3714566310
pli 9,232160395
rldimi 9,10,32,0
mulhdu 3,3,9
srdi 3,3,5
blr

(The first three instructions are pasting together the constant, which
of course My 66000 can do much better :-)

A hypothetical My66000 code could be

mulhu r1, r1, #-2492803253203993461
srl r1, r1, #5
ret

On 12/12/2023 12:09 AM, Thomas Koenig wrote:
> MitchAlsup <mitchalsup@aol.com> schrieb:
>> Thomas Koenig wrote:
>>
>>> MitchAlsup <mitchalsup@aol.com> schrieb:
>>>
>>> #include <stdint.h>
>>
>>> uint32_t div25 (uint32_t n)
>>> {
>>> return n / 25;
>>> }
>>
>>> yields
>>
>>> div25:
>>> lis 9,0x51eb // cycle 1
>>> ori 9,9,0x851f // cycle 2
>>> mulhwu 3,3,9 // cycle 3-6
>>> srwi 3,3,3 // cycle 7
>>> blr // cycle 8
>>
>> div25:
>> CARRY R8,{{O}} // cycle 1
>> MUL R1,R1,#0x51eb851f // cycle 1-4
>> SLL R1,R8,#35 // cycle 5
>> RET // cycle 6
>
> Then let's use a 64-bit example:
>
> #include <stdint.h>
>
> uint64_t div (uint64_t n)
> {
> return n / 37;
> }
>
> which becomes
>
> div:
> .LFB0:
> .cfi_startproc
> movabsq $-2492803253203993461, %rax
> mulq %rdi
> movq %rdx, %rax
> shrq $5, %rax
> ret
>
> on x86_64 (so, use the high result only and shift it five bits to
> the right) and, with Power10,
>
> div:
> pli 10,3714566310
> pli 9,232160395
> rldimi 9,10,32,0
> mulhdu 3,3,9
> srdi 3,3,5
> blr
>
> (The first three instructions are pasting together the constant, which
> of course My 66000 can do much better :-)
>
> A hypothetical My66000 code could be
>
> mulhu r1, r1, #-2492803253203993461
> srl r1, r1, #5
> ret
>

And, for comparison, on BJX2 (with the MULQ extension):
MOV -2492803253203993461, R3
MULHU.Q R4, R3, R2
SHLD.Q R2, -5, R2
RTS
....

Though, this will take 24 bytes to encode, and wont be fast.

Also, currently the only instructions that take 64 bit immediate values are:
MOV Imm64, Rn
ADD Imm64, Rn
PLDCXH Imm64, Xn //4x Binary16 to 4x Binary32

....

On 2023-12-12 4:00 a.m., BGB wrote:
> On 12/12/2023 12:09 AM, Thomas Koenig wrote:
>> MitchAlsup <mitchalsup@aol.com> schrieb:
>>> Thomas Koenig wrote:
>>>
>>>> MitchAlsup <mitchalsup@aol.com> schrieb:
>>>>
>>>> #include <stdint.h>
>>>
>>>> uint32_t div25 (uint32_t n)
>>>> {
>>>>    return n / 25;
>>>> }
>>>
>>>> yields
>>>
>>>> div25:
>>>>          lis 9,0x51eb        // cycle 1
>>>>          ori 9,9,0x851f    // cycle 2
>>>>          mulhwu 3,3,9        // cycle 3-6
>>>>          srwi 3,3,3        // cycle 7
>>>>          blr            // cycle 8
>>>
>>> div25:
>>>     CARRY R8,{{O}}       // cycle 1
>>>     MUL R1,R1,#0x51eb851f    // cycle 1-4
>>>     SLL R1,R8,#35        // cycle 5
>>>     RET            // cycle 6
>>
>> Then let's use a 64-bit example:
>>
>> #include <stdint.h>
>>
>> uint64_t div (uint64_t n)
>> {
>>    return n / 37;
>> }
>>
>> which becomes
>>
>> div:
>> .LFB0:
>>          .cfi_startproc
>>          movabsq $-2492803253203993461, %rax
>>          mulq    %rdi
>>          movq    %rdx, %rax
>>          shrq    $5, %rax
>>          ret
>>
>> on x86_64 (so, use the high result only and shift it five bits to
>> the right) and, with Power10,
>>
>> div:
>>          pli 10,3714566310
>>          pli 9,232160395
>>          rldimi 9,10,32,0
>>          mulhdu 3,3,9
>>          srdi 3,3,5
>>          blr
>>
>> (The first three instructions are pasting together the constant, which
>> of course My 66000 can do much better :-)
>>
>> A hypothetical My66000 code could be
>>
>>        mulhu    r1, r1, #-2492803253203993461
>>        srl    r1, r1, #5
>>        ret
>>
>
> And, for comparison, on BJX2 (with the MULQ extension):
>   MOV -2492803253203993461, R3
>   MULHU.Q R4, R3, R2
>   SHLD.Q R2, -5, R2
>   RTS
> ...
>
> Though, this will take 24 bytes to encode, and wont be fast.
>
> Also, currently the only instructions that take 64 bit immediate values
> are:
>   MOV Imm64, Rn
>   ADD Imm64, Rn
>   PLDCXH Imm64, Xn  //4x Binary16 to 4x Binary32
>
> ...
>
Q+ is almost the same as MY66000

muluh r1,r1,#-2492803253203993461
lsr r1,r1,#5
ret

but ret is only two bytes.

On 12/12/2023 10:27 AM, Robert Finch wrote:
> On 2023-12-12 4:00 a.m., BGB wrote:
>> On 12/12/2023 12:09 AM, Thomas Koenig wrote:
>>> MitchAlsup <mitchalsup@aol.com> schrieb:
>>>> Thomas Koenig wrote:
>>>>
>>>>> MitchAlsup <mitchalsup@aol.com> schrieb:
>>>>>
>>>>> #include <stdint.h>
>>>>
>>>>> uint32_t div25 (uint32_t n)
>>>>> {
>>>>>    return n / 25;
>>>>> }
>>>>
>>>>> yields
>>>>
>>>>> div25:
>>>>>          lis 9,0x51eb        // cycle 1
>>>>>          ori 9,9,0x851f    // cycle 2
>>>>>          mulhwu 3,3,9        // cycle 3-6
>>>>>          srwi 3,3,3        // cycle 7
>>>>>          blr            // cycle 8
>>>>
>>>> div25:
>>>>     CARRY R8,{{O}}       // cycle 1
>>>>     MUL R1,R1,#0x51eb851f    // cycle 1-4
>>>>     SLL R1,R8,#35        // cycle 5
>>>>     RET            // cycle 6
>>>
>>> Then let's use a 64-bit example:
>>>
>>> #include <stdint.h>
>>>
>>> uint64_t div (uint64_t n)
>>> {
>>>    return n / 37;
>>> }
>>>
>>> which becomes
>>>
>>> div:
>>> .LFB0:
>>>          .cfi_startproc
>>>          movabsq $-2492803253203993461, %rax
>>>          mulq    %rdi
>>>          movq    %rdx, %rax
>>>          shrq    $5, %rax
>>>          ret
>>>
>>> on x86_64 (so, use the high result only and shift it five bits to
>>> the right) and, with Power10,
>>>
>>> div:
>>>          pli 10,3714566310
>>>          pli 9,232160395
>>>          rldimi 9,10,32,0
>>>          mulhdu 3,3,9
>>>          srdi 3,3,5
>>>          blr
>>>
>>> (The first three instructions are pasting together the constant, which
>>> of course My 66000 can do much better :-)
>>>
>>> A hypothetical My66000 code could be
>>>
>>>        mulhu    r1, r1, #-2492803253203993461
>>>        srl    r1, r1, #5
>>>        ret
>>>
>>
>> And, for comparison, on BJX2 (with the MULQ extension):
>>    MOV -2492803253203993461, R3
>>    MULHU.Q R4, R3, R2
>>    SHLD.Q R2, -5, R2
>>    RTS
>> ...
>>
>> Though, this will take 24 bytes to encode, and wont be fast.
>>
>> Also, currently the only instructions that take 64 bit immediate
>> values are:
>>    MOV Imm64, Rn
>>    ADD Imm64, Rn
>>    PLDCXH Imm64, Xn  //4x Binary16 to 4x Binary32
>>
>> ...
>>
> Q+ is almost the same as MY66000
>
> muluh r1,r1,#-2492803253203993461
> lsr r1,r1,#5
> ret
>
> but ret is only two bytes.
>

In my case, RTS is 16 bits in Baseline mode, 32 bits in XG2 mode (either
way, it effectively performs a branch to the address held in the link
register).

In my case, it is limited both by the instruction encoding rules
currently only allowing for a 96-bit instruction (which, in turn, and
only express a 64-bit immediate for a few ops).

To be able to encode a multiply with a 64-bit immediate would
effectively require a 128-bit instruction encoding (Say: FE-FE-FF-OP,
with the FF being able to glue a 17-bit immediate onto some instructions
that wouldn't normally be able to have an immediate, and 24+24+17=65).

....

Robert Finch wrote:

> On 2023-12-12 4:00 a.m., BGB wrote:
>> On 12/12/2023 12:09 AM, Thomas Koenig wrote:
>>> MitchAlsup <mitchalsup@aol.com> schrieb:
>>>> Thomas Koenig wrote:
>>>>
>>>>> MitchAlsup <mitchalsup@aol.com> schrieb:
>>>>>
>>>>> #include <stdint.h>
>>>>
>>>>> uint32_t div25 (uint32_t n)
>>>>> {
>>>>>    return n / 25;
>>>>> }
>>>>
>>>>> yields
>>>>
>>>>> div25:
>>>>>          lis 9,0x51eb        // cycle 1
>>>>>          ori 9,9,0x851f    // cycle 2
>>>>>          mulhwu 3,3,9        // cycle 3-6
>>>>>          srwi 3,3,3        // cycle 7
>>>>>          blr            // cycle 8
>>>>
>>>> div25:
>>>>     CARRY R8,{{O}}       // cycle 1
>>>>     MUL R1,R1,#0x51eb851f    // cycle 1-4
>>>>     SLL R1,R8,#35        // cycle 5
>>>>     RET            // cycle 6
>>>
>>> Then let's use a 64-bit example:
>>>
>>> #include <stdint.h>
>>>
>>> uint64_t div (uint64_t n)
>>> {
>>>    return n / 37;
>>> }
>>>
>>> which becomes
>>>
>>> div:
>>> .LFB0:
>>>          .cfi_startproc
>>>          movabsq $-2492803253203993461, %rax
>>>          mulq    %rdi
>>>          movq    %rdx, %rax
>>>          shrq    $5, %rax
>>>          ret
>>>
>>> on x86_64 (so, use the high result only and shift it five bits to
>>> the right) and, with Power10,
>>>
>>> div:
>>>          pli 10,3714566310
>>>          pli 9,232160395
>>>          rldimi 9,10,32,0
>>>          mulhdu 3,3,9
>>>          srdi 3,3,5
>>>          blr
>>>
>>> (The first three instructions are pasting together the constant, which
>>> of course My 66000 can do much better :-)
>>>
>>> A hypothetical My66000 code could be
>>>
>>>        mulhu    r1, r1, #-2492803253203993461
>>>        srl    r1, r1, #5
>>>        ret
>>>
>>
>> And, for comparison, on BJX2 (with the MULQ extension):
>>   MOV -2492803253203993461, R3
>>   MULHU.Q R4, R3, R2
>>   SHLD.Q R2, -5, R2
>>   RTS
>> ...
>>
>> Though, this will take 24 bytes to encode, and wont be fast.
>>
>> Also, currently the only instructions that take 64 bit immediate values
>> are:
>>   MOV Imm64, Rn
>>   ADD Imm64, Rn
>>   PLDCXH Imm64, Xn  //4x Binary16 to 4x Binary32
>>
>> ...
>>
> Q+ is almost the same as MY66000

> muluh r1,r1,#-2492803253203993461
> lsr r1,r1,#5
> ret

> but ret is only two bytes.

When subroutines are aligned to cache line boundaries, that adds nothing.

On 12/12/2023 2:43 PM, MitchAlsup wrote:
> Robert Finch wrote:
>
>> On 2023-12-12 4:00 a.m., BGB wrote:
>>> On 12/12/2023 12:09 AM, Thomas Koenig wrote:
>>>> MitchAlsup <mitchalsup@aol.com> schrieb:
>>>>> Thomas Koenig wrote:
>>>>>
>>>>>> MitchAlsup <mitchalsup@aol.com> schrieb:
>>>>>>
>>>>>> #include <stdint.h>
>>>>>
>>>>>> uint32_t div25 (uint32_t n)
>>>>>> {
>>>>>>    return n / 25;
>>>>>> }
>>>>>
>>>>>> yields
>>>>>
>>>>>> div25:
>>>>>>          lis 9,0x51eb        // cycle 1
>>>>>>          ori 9,9,0x851f    // cycle 2
>>>>>>          mulhwu 3,3,9        // cycle 3-6
>>>>>>          srwi 3,3,3        // cycle 7
>>>>>>          blr            // cycle 8
>>>>>
>>>>> div25:
>>>>>     CARRY R8,{{O}}       // cycle 1
>>>>>     MUL R1,R1,#0x51eb851f    // cycle 1-4
>>>>>     SLL R1,R8,#35        // cycle 5
>>>>>     RET            // cycle 6
>>>>
>>>> Then let's use a 64-bit example:
>>>>
>>>> #include <stdint.h>
>>>>
>>>> uint64_t div (uint64_t n)
>>>> {
>>>>    return n / 37;
>>>> }
>>>>
>>>> which becomes
>>>>
>>>> div:
>>>> .LFB0:
>>>>          .cfi_startproc
>>>>          movabsq $-2492803253203993461, %rax
>>>>          mulq    %rdi
>>>>          movq    %rdx, %rax
>>>>          shrq    $5, %rax
>>>>          ret
>>>>
>>>> on x86_64 (so, use the high result only and shift it five bits to
>>>> the right) and, with Power10,
>>>>
>>>> div:
>>>>          pli 10,3714566310
>>>>          pli 9,232160395
>>>>          rldimi 9,10,32,0
>>>>          mulhdu 3,3,9
>>>>          srdi 3,3,5
>>>>          blr
>>>>
>>>> (The first three instructions are pasting together the constant, which
>>>> of course My 66000 can do much better :-)
>>>>
>>>> A hypothetical My66000 code could be
>>>>
>>>>        mulhu    r1, r1, #-2492803253203993461
>>>>        srl    r1, r1, #5
>>>>        ret
>>>>
>>>
>>> And, for comparison, on BJX2 (with the MULQ extension):
>>>    MOV -2492803253203993461, R3
>>>    MULHU.Q R4, R3, R2
>>>    SHLD.Q R2, -5, R2
>>>    RTS
>>> ...
>>>
>>> Though, this will take 24 bytes to encode, and wont be fast.
>>>
>>> Also, currently the only instructions that take 64 bit immediate
>>> values are:
>>>    MOV Imm64, Rn
>>>    ADD Imm64, Rn
>>>    PLDCXH Imm64, Xn  //4x Binary16 to 4x Binary32
>>>
>>> ...
>>>
>> Q+ is almost the same as MY66000
>
>> muluh r1,r1,#-2492803253203993461
>> lsr r1,r1,#5
>> ret
>
>> but ret is only two bytes.
>
> When subroutines are aligned to cache line boundaries, that adds nothing.

Technically, yes.

Or, even if not, very little, given that RET / RTS is comparably
infrequent...

In other news, did at least go and tweak decoding rules slightly such
that an Op64 prefix can now glue an Imm17s onto most "normal" 3R
instructions, with a few exceptions:
4R and 3R/3RI forms:
These may add either an Imm17s, 4th register, or 3R+Imm9.
This includes the Integer MAC and FMAC instructions.
FPU and FP-SIMD ops, where this encoding encodes a rounding-mode.

This change is N/A for ops not otherwise following the "OP Rm, Ro, Rn"
format.

Or: FFw0-0Vii-F0nm-ZeiZ OP Rm, Imm17s, Rn

This case is mostly intended to allow encoding an immediate form for
many ops which don't otherwise have an immediate form (but does have the
usual drawbacks associated with being a 64-bit encoding).

Thomas Koenig <tkoenig@netcologne.de> schrieb:

> A hypothetical My66000 code could be
>
> mulhu r1, r1, #-2492803253203993461
> srl r1, r1, #5
> ret

By "hypothetical" I mean that it isn't in the ISA at the moment.

Thomas Koenig wrote:

> Thomas Koenig <tkoenig@netcologne.de> schrieb:

>> A hypothetical My66000 code could be
>>
>> mulhu r1, r1, #-2492803253203993461
>> srl r1, r1, #5
>> ret

> By "hypothetical" I mean that it isn't in the ISA at the moment.

If I knew what mulhu does I could illuminate::
a) how many bits get multiplied?
b) how many bits are produced?

But assuming h means high, and the widths are 64-bit operands and
128-bit results::

CARRY R1,{{O}{I}}
MUL R2,R1,#-2492803253203993461
SHR R1,R2,<0,5>
RET

MitchAlsup <mitchalsup@aol.com> schrieb:
> Thomas Koenig wrote:
>
>> Thomas Koenig <tkoenig@netcologne.de> schrieb:
>
>>> A hypothetical My66000 code could be
>>>
>>> mulhu r1, r1, #-2492803253203993461
>>> srl r1, r1, #5
>>> ret
>
>> By "hypothetical" I mean that it isn't in the ISA at the moment.
>
> If I knew what mulhu does I could illuminate::
> a) how many bits get multiplied?
> b) how many bits are produced?
>
> But assuming h means high, and the widths are 64-bit operands and
> 128-bit results::
>
> CARRY R1,{{O}{I}}
> MUL R2,R1,#-2492803253203993461
> SHR R1,R2,<0,5>
> RET

That works, but has two disadvantages over the non-Carry
version: It is longer (by one instruction modifier),
and R2 is overwritten with a value which is not needed.
This is why I think that having a "multiply high signed"
and "multiply high unsigned" operation is a good idea even
when My 66000's Carry is implemented.

Thomas Koenig wrote:

> MitchAlsup <mitchalsup@aol.com> schrieb:
>> Thomas Koenig wrote:
>>
>>> Thomas Koenig <tkoenig@netcologne.de> schrieb:
>>
>>>> A hypothetical My66000 code could be
>>>>
>>>> mulhu r1, r1, #-2492803253203993461
>>>> srl r1, r1, #5
>>>> ret
>>
>>> By "hypothetical" I mean that it isn't in the ISA at the moment.
>>
>> If I knew what mulhu does I could illuminate::
>> a) how many bits get multiplied?
>> b) how many bits are produced?
>>
>> But assuming h means high, and the widths are 64-bit operands and
>> 128-bit results::
>>
>> CARRY R1,{{O}{I}}
>> MUL R2,R1,#-2492803253203993461
>> SHR R1,R2,<0,5>
>> RET

> That works, but has two disadvantages over the non-Carry
> version: It is longer (by one instruction modifier),
> and R2 is overwritten with a value which is not needed.
> This is why I think that having a "multiply high signed"
> and "multiply high unsigned" operation is a good idea even
> when My 66000's Carry is implemented.

Heck:: if you are worried about length::

DIV R1,R1,#27
RET

2 words instead of 6.

MitchAlsup <mitchalsup@aol.com> schrieb:
> Thomas Koenig wrote:
>
>> MitchAlsup <mitchalsup@aol.com> schrieb:
>>> Thomas Koenig wrote:
>>>
>>>> Thomas Koenig <tkoenig@netcologne.de> schrieb:
>>>
>>>>> A hypothetical My66000 code could be
>>>>>
>>>>> mulhu r1, r1, #-2492803253203993461
>>>>> srl r1, r1, #5
>>>>> ret
>>>
>>>> By "hypothetical" I mean that it isn't in the ISA at the moment.
>>>
>>> If I knew what mulhu does I could illuminate::
>>> a) how many bits get multiplied?
>>> b) how many bits are produced?
>>>
>>> But assuming h means high, and the widths are 64-bit operands and
>>> 128-bit results::
>>>
>>> CARRY R1,{{O}{I}}
>>> MUL R2,R1,#-2492803253203993461
>>> SHR R1,R2,<0,5>
>>> RET
>
>> That works, but has two disadvantages over the non-Carry
>> version: It is longer (by one instruction modifier),
>> and R2 is overwritten with a value which is not needed.
>> This is why I think that having a "multiply high signed"
>> and "multiply high unsigned" operation is a good idea even
>> when My 66000's Carry is implemented.
>
> Heck:: if you are worried about length::
>
> DIV R1,R1,#27
> RET
>
> 2 words instead of 6.

This is an optimization problem with three objective functions:
Code size, register use and speed. Any solution in which at which
it is no longer possible to improve one of the objective functions
without making the others worse is a valid solution to that problem
(part of the Pareto front, if you want to use that terminology).

The version with the DIV with constant is the smallest, so it
trumps everything else on size. It is, however, likely to be
slower than the other two. It is what I would a compiler to emit
if optimizing for size (-Os), and when not optimizing.

The version with the Carry is likely faster than the DIV with
constant version, but is bigger and uses two registers instead
of one. It is what I would expect a compiler to generate in
the absence of multiply high unsigned and any -O option, except
for -Os.

The hypothetical version with "multiply high unsigned" is smaller
than the version with Carry and is better on register use, so
it is better in that sense. If it existed, I would expect a
compiler to always generate that for any optimization level
except -Os. (Small caveat: Maybe hardware has a fiendishly
clever algorithm to divide by 37 in four or less cycles; this
would then be known to the compiler, and it could chose accordingly).

Thomas Koenig wrote:

> MitchAlsup <mitchalsup@aol.com> schrieb:
>> Thomas Koenig wrote:
>>
>>> MitchAlsup <mitchalsup@aol.com> schrieb:
>>>> Thomas Koenig wrote:
>>>>
>>>>> Thomas Koenig <tkoenig@netcologne.de> schrieb:
>>>>
>>>>>> A hypothetical My66000 code could be
>>>>>>
>>>>>> mulhu r1, r1, #-2492803253203993461
>>>>>> srl r1, r1, #5
>>>>>> ret
>>>>
>>>>> By "hypothetical" I mean that it isn't in the ISA at the moment.
>>>>
>>>> If I knew what mulhu does I could illuminate::
>>>> a) how many bits get multiplied?
>>>> b) how many bits are produced?
>>>>
>>>> But assuming h means high, and the widths are 64-bit operands and
>>>> 128-bit results::
>>>>
>>>> CARRY R1,{{O}{I}}
>>>> MUL R2,R1,#-2492803253203993461
>>>> SHR R1,R2,<0,5>
>>>> RET
>>
>>> That works, but has two disadvantages over the non-Carry
>>> version: It is longer (by one instruction modifier),
>>> and R2 is overwritten with a value which is not needed.
>>> This is why I think that having a "multiply high signed"
>>> and "multiply high unsigned" operation is a good idea even
>>> when My 66000's Carry is implemented.
>>
>> Heck:: if you are worried about length::
>>
>> DIV R1,R1,#27
>> RET
>>
>> 2 words instead of 6.

> This is an optimization problem with three objective functions:
> Code size, register use and speed. Any solution in which at which
> it is no longer possible to improve one of the objective functions
> without making the others worse is a valid solution to that problem
> (part of the Pareto front, if you want to use that terminology).

> The version with the DIV with constant is the smallest, so it
> trumps everything else on size. It is, however, likely to be
> slower than the other two. It is what I would a compiler to emit
> if optimizing for size (-Os), and when not optimizing.

Since I do IDIV in the FMAC unit, and integers are not normalized::
FMAC passes both operands through the normalizer's Find First logic
and knows the significance of the numerator and denominator.

Thus, for this case, 27 is detected to have only 5-bits of significance
and the 1-bit per loop* only takes 5 cycles. Giving a fall through time
of 8-cycles total.

(*) assuming a 1-bit at a time loop--which I would not do--but I
still do the normalization steps to make the integers smell like
FP numbers, so, 1 Goldschmidt step and 1 Newton-Raphson step and
you have 8 cycle IDIV for denominators with less than 8-bits of
significance, 10-cycles for denominators of less then 16-bits,...

> The version with the Carry is likely faster than the DIV with
> constant version, but is bigger and uses two registers instead
> of one. It is what I would expect a compiler to generate in
> the absence of multiply high unsigned and any -O option, except
> for -Os.

What if we solve the problem by making IDIV fast instead !!

Given a fast IDIV, is there any use for IMULH ??

> The hypothetical version with "multiply high unsigned" is smaller
> than the version with Carry and is better on register use, so

I should point out that having the constant attached to the
MUL (as is were) you have already saves a register compared to
ISAs without large constants.

> it is better in that sense. If it existed, I would expect a
> compiler to always generate that for any optimization level
> except -Os. (Small caveat: Maybe hardware has a fiendishly
> clever algorithm to divide by 37 in four or less cycles; this
> would then be known to the compiler, and it could chose accordingly).

This is one gigantic reason to use FDIV to perform IDIV--and another
smaller one not to separate register files. FIDVs are in the 17-20
cycle range, why should IDIV not also be in that range ??

On 12/17/23 4:55 PM, MitchAlsup wrote:
[snip]
> What if we solve the problem by making IDIV fast instead !!
>
> Given a fast IDIV, is there any use for IMULH ??

I saw using IMULH (or better a "division based on providing a
reciprocal") as a method to perform common subexpression
elimination on the iterative refinement of the reciprocal for
constants and for reused values. Storing and reusing the
reciprocal just seemed to make sense, though sometimes recomputing
may have less overhead.

Latency is also not the only consideration. Energy use is also a
consideration.

This technique might also be applicable when divisors are not
identical, but I doubt that would be very useful (though I vaguely
recall reading that some scientific computation had such divisions
somewhat commonly).

Hardware memoization of reciprocals has been proposed. I merely
thought that allowing a compiler to cache (and reuse) reciprocals
might be useful.

Thomas Koenig wrote:
> MitchAlsup <mitchalsup@aol.com> schrieb:
>> Thomas Koenig wrote:
>>
>>> Thomas Koenig <tkoenig@netcologne.de> schrieb:
>>
>>>> A hypothetical My66000 code could be
>>>>
>>>> mulhu r1, r1, #-2492803253203993461
>>>> srl r1, r1, #5
>>>> ret
>>
>>> By "hypothetical" I mean that it isn't in the ISA at the moment.
>>
>> If I knew what mulhu does I could illuminate::
>> a) how many bits get multiplied?
>> b) how many bits are produced?
>>
>> But assuming h means high, and the widths are 64-bit operands and
>> 128-bit results::
>>
>> CARRY R1,{{O}{I}}
>> MUL R2,R1,#-2492803253203993461
>> SHR R1,R2,<0,5>
>> RET
>
> That works, but has two disadvantages over the non-Carry
> version: It is longer (by one instruction modifier),
> and R2 is overwritten with a value which is not needed.
> This is why I think that having a "multiply high signed"
> and "multiply high unsigned" operation is a good idea even
> when My 66000's Carry is implemented.

I disagree:

The R2 overwrite really doesn't matter since the OoO circuitry will
quickly notice that the value isn't used at all, and the extra CARRY
modifier does not make the code any slower: It will still take exactly
the latency of MUL + SHR, so presumably 5-6 total cycles.

Since MULHU is very rarely used in regular code (pretty much only in
constant divisions that got replaced with reciprocal muls), this tiny
overhead is a very good deal.

Terje

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

Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
> Thomas Koenig wrote:
>> MitchAlsup <mitchalsup@aol.com> schrieb:
>>> Thomas Koenig wrote:
>>>
>>>> Thomas Koenig <tkoenig@netcologne.de> schrieb:
>>>
>>>>> A hypothetical My66000 code could be
>>>>>
>>>>> mulhu r1, r1, #-2492803253203993461
>>>>> srl r1, r1, #5
>>>>> ret
>>>
>>>> By "hypothetical" I mean that it isn't in the ISA at the moment.
>>>
>>> If I knew what mulhu does I could illuminate::
>>> a) how many bits get multiplied?
>>> b) how many bits are produced?
>>>
>>> But assuming h means high, and the widths are 64-bit operands and
>>> 128-bit results::
>>>
>>> CARRY R1,{{O}{I}}
>>> MUL R2,R1,#-2492803253203993461
>>> SHR R1,R2,<0,5>
>>> RET
>>
>> That works, but has two disadvantages over the non-Carry
>> version: It is longer (by one instruction modifier),
>> and R2 is overwritten with a value which is not needed.
>> This is why I think that having a "multiply high signed"
>> and "multiply high unsigned" operation is a good idea even
>> when My 66000's Carry is implemented.
>
> I disagree:
>
> The R2 overwrite really doesn't matter since the OoO circuitry will
> quickly notice that the value isn't used at all, and the extra CARRY
> modifier does not make the code any slower: It will still take exactly
> the latency of MUL + SHR, so presumably 5-6 total cycles.

You're correct that the register use will probably be elided in
an OoO machine, but the register is still overwritten. This does
not matter for a function that does just that division, but in
larger functions, this can lead to an additional spill/restore.

> Since MULHU is very rarely used in regular code (pretty much only in
> constant divisions that got replaced with reciprocal muls), this tiny
> overhead is a very good deal.

My 66000 has very low register usage, especially due to the encoding
of constants. Another reason are indexed and scaled loads and
stores, which allows fewer registers because, for code like

do i=1,n
a(i) = b(i) + c(i)
end do

there is no need for having a pointer run through a, b and c,
requiring fewer registers.

This is why putting floating point values and integer values into
the same register set actually works well for My 66000, and would
not work so well for others.

Still, when I see an inefficiency, even minor, I tend to remark
on it :-)

Thomas Koenig wrote:

> Still, when I see an inefficiency, even minor, I tend to remark
> on it :-)

And that is why we love you.