On Friday, February 11, 2022 at 5:11:16 PM UTC-6, Thomas Koenig wrote:
> Quadibloc <jsa...@ecn.ab.ca> schrieb:
> > On Friday, February 11, 2022 at 11:28:53 AM UTC-7, MitchAlsup wrote:
> >
> >> If you can encode all the work of those 8 32-bit instructions in 7 36-bit
> >> instructions, you are ahead of the game.
> >
> > That's true. But many people will be skeptical. After all, eight
> > instructions do eight things, seven instructions do seven things.
> Compare and branch could profit a lot from more bits, 36 or 40.
>
> Assume
>
> - 6 bit primary opcode
> - 10 bit for two registers to compare, or for a register and a
> constant
> - 3 bits for comparison code
>
> you are left with either 13, 17 or 21 bits of offset for a 32,
> 36 or 40 bit instruction word. Subtract two bits if you have 64
> registers / a 64-bit constant. (RISC-V needs to have a 7-bit
> primary opcode because of their 16-bit instructions, so it has
> one bit less, and loses one bit due to having 16-bit instructions).
<
This is why it failed to make the cut. However, compare to zero and
branch did under the name of BCND.
<
"On the pipeline" compare and branch only work when the ICache
is in one phase of the clock with DCache is on another phase.
That is: it worked with MIPS 2000, 3000, and became problematic
later on. With Caches needing address setup before rising edge
and delivering data after next rising edge, it "worka nadda".
<
Also note: to make timing work the 16-bit constant was pasted
onto the IP instead of being added to IP. Did not have time for
adding.
>
> It is rather hard to do anything useful with 16 bits with full 32
> registers. Does anybody have data how well RISC-V manages to
> reduce code size with their 16-bit instructions, and if there
> is performance degradation? Unfortunately, I have do not
> have access to a RISC-V machine to run my own analysis.

On Friday, February 11, 2022 at 5:41:24 PM UTC-6, gg...@yahoo.com wrote:
> MitchAlsup <Mitch...@aol.com> wrote:
> > On Friday, February 11, 2022 at 1:49:10 PM UTC-6, Stephen Fuld wrote:
> >> On 2/11/2022 10:35 AM, MitchAlsup wrote:
> >>> On Friday, February 11, 2022 at 11:18:43 AM UTC-6, Stephen Fuld wrote:
> >>>> On 2/11/2022 1:12 AM, Thomas Koenig wrote:
> >>>>> MitchAlsup <Mitch...@aol.com> schrieb:
> >>>>>> On Wednesday, February 9, 2022 at 3:53:18 PM UTC-6, Quadibloc wrote:
> >>>>>>> On Wednesday, February 9, 2022 at 1:58:55 PM UTC-7, gg...@yahoo.com wrote:
> >>>>>>>> And with 64 you can crush the
> >>>>>>>> competition on FPU code which eats registers for breakfast. As a former
> >>>>>>>> game console programmer I can tell you 32 is not enough.
> >>>>>> <
> >>>>>>> This is useful to know. Despite Mitch noting that decoding more than 32 registers
> >>>>>>> is a problem, then, I guess I'll be putting the 128-register bank feature back into
> >>>>>>> my attempts at a high-performance design.
> >>>>>> <
> >>>>>> It is NOT the decoding of registers that is the problem.
> >>>>>> It is that the register specifiers eat too many bits in the instruction.
> >>>>>
> >>>>> ... which is one reason I stared thinking about 40-bit instruction
> >>>>> bundles :-)
> >>> <
> >>>> Mitch has stated that his ideal instruction size is 36 bits, so how
> >>>> about this?
> >>> <
> >>> Just to bring everyone up to speed::
> >>> <
> >>> 36-bits allows one to encode everything My 66000 encodes in 32-bits
> >>> but also to provide room for sized arithmetic {8,16,32,64}×{int,fp},
> >>> saturation, overflow, wrap,...along with CARRY {int, fp}, plus
> >> Did you prematurely send this, or did you intend it to end there?
> >>
> >> Also, it seems you want to use the extra bits for more op-codes or op
> >> code modifiers and not to support 64 GPRs. Is that right? Or some mix
> >> of both?
> > <
> > I intended to imply other things can use those extra bits, but that I don't
> > need to influence those thinking about what they might be used for.
> > <
> > I am not a fan of 64-registers,
> > you gain so little 3%-ish
> The average C code gains 3%, averages lie.
>
> The inner loops of game code can get 10%.
<
All game inner loops gain 10%? I don't think so.
<
Anyway the data is from Stanford circa 1984-ish, so it is quite old.
<
> And 90% of the compute time is in
> 10% of the code. So a overall 9% speedup, while a simple code profile
> without benchmarking says 3%.
<
But that 9% speedup is not for general purpose code.
>
> A new processor needs an edge, and this is an edge.
<
How about being sin() and cos() taking 19 cycles.
How about Context switch from a process in one Guest OS to a process
in another Guest OS taking only 10-cycles.
>
> The RISC approach of cutting features until there is nothing left, leaves
> no reason to buy.
<
Agreed--1980s RISC is academic quality only (RISC-V may fall into this
category too)
>
> Transistors are cheap, throw the kitchen sink at an optional variable width
> opcode extension, kind of like ARM did with Cortex-Thumb2.
> > you lose in subroutines
> > you lose in context switch
> > you lose in memory footprint
> > you eat up 3-4 your instruction bits--which is all you added in the first place !
> > That it is quite likely you make negative forward progress.
> > <
> > A decided choice.
> >> --
> >> - Stephen Fuld
> >> (e-mail address disguised to prevent spam)
> >

> Also note: to make timing work the 16-bit constant was pasted
> onto the IP instead of being added to IP. Did not have time for
> adding.

Hmm... I though SPARC did that, not MIPS. Am I misremembering?

Stefan

MitchAlsup <MitchAlsup@aol.com> schrieb:
> On Friday, February 11, 2022 at 5:11:16 PM UTC-6, Thomas Koenig wrote:
>> Quadibloc <jsa...@ecn.ab.ca> schrieb:
>> > On Friday, February 11, 2022 at 11:28:53 AM UTC-7, MitchAlsup wrote:
>> >
>> >> If you can encode all the work of those 8 32-bit instructions in 7 36-bit
>> >> instructions, you are ahead of the game.
>> >
>> > That's true. But many people will be skeptical. After all, eight
>> > instructions do eight things, seven instructions do seven things.
>> Compare and branch could profit a lot from more bits, 36 or 40.
>>
>> Assume
>>
>> - 6 bit primary opcode
>> - 10 bit for two registers to compare, or for a register and a
>> constant
>> - 3 bits for comparison code
>>
>> you are left with either 13, 17 or 21 bits of offset for a 32,
>> 36 or 40 bit instruction word. Subtract two bits if you have 64
>> registers / a 64-bit constant. (RISC-V needs to have a 7-bit
>> primary opcode because of their 16-bit instructions, so it has
>> one bit less, and loses one bit due to having 16-bit instructions).
><
> This is why it failed to make the cut. However, compare to zero and
> branch did under the name of BCND.

Makes sense, this is the most frequent case (especially when
checking for null pointers).
><
> "On the pipeline" compare and branch only work when the ICache
> is in one phase of the clock with DCache is on another phase.
> That is: it worked with MIPS 2000, 3000, and became problematic
> later on. With Caches needing address setup before rising edge
> and delivering data after next rising edge, it "worka nadda".

Does not have to be done like that - it would simply be one
instruction instead of

cmpidi rx,const
beq offset

and could indeed be cracked into two instructions, with a
user-invisible status in between.

Slightly different topic: When talking about what to put into
a half-sized instruction set, it is trivially true that

mr ra,rb
add ra,rc

which could be made up of two n/2 bit instructions is equivalent to

add ra,rb,rc

which is a classic n-bit instuction, and could be fused into one.

On 12.02.2022 05:47, Stefan Monnier wrote:
>> Also note: to make timing work the 16-bit constant was pasted
>> onto the IP instead of being added to IP. Did not have time for
>> adding.
>
> Hmm... I though SPARC did that, not MIPS. Am I misremembering?
>
>
> Stefan

MIPS added sign-extended 16 bit displacements (bxx instructions), and
pasted 26 bit jump targets shifted left by 2 (jxx instructions).

Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> Also note: to make timing work the 16-bit constant was pasted
>> onto the IP instead of being added to IP. Did not have time for
>> adding.
>
>Hmm... I though SPARC did that, not MIPS. Am I misremembering?

The MIPS b instructions are relative, the MIPS j and jal instructions
are absolute, but have only 26 bits of address in the instruction; the
lower 2 bits are 0, the upper 4 bits are unchanged (i.e., j and jal
only branch within the same 256MB-Block, which was ok in 1986 when
MIPS started, but became uncomfortable as soon as virtual memories
exceeded 256MB).

I think everything is relative in SPARC. I am not that familiar with
SPARC, but we certainly treat SPARC code as relocatable in Gforth (and
nobody has complained), while we disable dynamic native code
generation on MIPS (because the code is not relocatable to arbitrary
places) because of j and jal (the MIPS load delay slot and the delay
slots associated with the hi and lo registers are also incompatible
with the assumptions about composability of code that we use in
dynamic native code generation; it's interesting how many of the
seemingly clever ideas of MIPS turn into problems in this context).

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Thomas Koenig <tkoenig@netcologne.de> writes:
>It is rather hard to do anything useful with 16 bits with full 32
>registers. Does anybody have data how well RISC-V manages to
>reduce code size with their 16-bit instructions, and if there
>is performance degradation?

Why should there be a performance degradation? If an instruction
cannot be encoded in 16 bits, the 32-bit encoding is used.

So the only question is how much the code size is reduced:
<https://arxiv.org/pdf/1607.02318.pdf> reports in Table III that RC64G
has a factor 1.34 more dynamic instruction bytes than RV64GC (geomean
over all benchmarks). It does not report static instruction bytes.

>Unfortunately, I have do not
>have access to a RISC-V machine to run my own analysis.

RISC-V has been supported by QEMU for a long time. E.g., we tested
Gforth on RISC-V (on QEMU) in 2018.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

On Friday, February 11, 2022 at 10:48:00 PM UTC-6, Stefan Monnier wrote:
> > Also note: to make timing work the 16-bit constant was pasted
> > onto the IP instead of being added to IP. Did not have time for
> > adding.
> Hmm... I though SPARC did that, not MIPS. Am I misremembering?
>
Could be either one of us.
>
> Stefan

On Saturday, February 12, 2022 at 3:35:48 AM UTC-6, Thomas Koenig wrote:
> MitchAlsup <Mitch...@aol.com> schrieb:
> > On Friday, February 11, 2022 at 5:11:16 PM UTC-6, Thomas Koenig wrote:
> >> Quadibloc <jsa...@ecn.ab.ca> schrieb:
> >> > On Friday, February 11, 2022 at 11:28:53 AM UTC-7, MitchAlsup wrote:
> >> >
> >> >> If you can encode all the work of those 8 32-bit instructions in 7 36-bit
> >> >> instructions, you are ahead of the game.
> >> >
> >> > That's true. But many people will be skeptical. After all, eight
> >> > instructions do eight things, seven instructions do seven things.
> >> Compare and branch could profit a lot from more bits, 36 or 40.
> >>
> >> Assume
> >>
> >> - 6 bit primary opcode
> >> - 10 bit for two registers to compare, or for a register and a
> >> constant
> >> - 3 bits for comparison code
> >>
> >> you are left with either 13, 17 or 21 bits of offset for a 32,
> >> 36 or 40 bit instruction word. Subtract two bits if you have 64
> >> registers / a 64-bit constant. (RISC-V needs to have a 7-bit
> >> primary opcode because of their 16-bit instructions, so it has
> >> one bit less, and loses one bit due to having 16-bit instructions).
> ><
> > This is why it failed to make the cut. However, compare to zero and
> > branch did under the name of BCND.
<
> Makes sense, this is the most frequent case (especially when
> checking for null pointers).
> ><
> > "On the pipeline" compare and branch only work when the ICache
> > is in one phase of the clock with DCache is on another phase.
> > That is: it worked with MIPS 2000, 3000, and became problematic
> > later on. With Caches needing address setup before rising edge
> > and delivering data after next rising edge, it "worka nadda".
<
> Does not have to be done like that - it would simply be one
> instruction instead of
>
> cmpidi rx,const
> beq offset
>
> and could indeed be cracked into two instructions, with a
> user-invisible status in between.
<
Those 2 instructions can be fused and CoIssued taking only
1 pipeline slot on machines that fetch wider than instruction
size. So, having 2 is not a performance problem on modern
machines.
<
1 versus 2 is only a code density issue not a performance one.
>
> Slightly different topic: When talking about what to put into
> a half-sized instruction set, it is trivially true that
>
> mr ra,rb
> add ra,rc
>
> which could be made up of two n/2 bit instructions is equivalent to
>
> add ra,rb,rc
>
> which is a classic n-bit instuction, and could be fused into one.
<
Yes, that was the point of the 68K guys when we were doing M88K.

Thomas Koenig wrote:
> Quadibloc <jsavard@ecn.ab.ca> schrieb:
>> On Friday, February 11, 2022 at 11:28:53 AM UTC-7, MitchAlsup wrote:
>>
>>> If you can encode all the work of those 8 32-bit instructions in 7 36-bit
>>> instructions, you are ahead of the game.
>> That's true. But many people will be skeptical. After all, eight
>> instructions do eight things, seven instructions do seven things.
>
> Compare and branch could profit a lot from more bits, 36 or 40.
>
> Assume
>
> - 6 bit primary opcode
> - 10 bit for two registers to compare, or for a register and a
> constant
> - 3 bits for comparison code
>
> you are left with either 13, 17 or 21 bits of offset for a 32,
> 36 or 40 bit instruction word. Subtract two bits if you have 64
> registers / a 64-bit constant. (RISC-V needs to have a 7-bit
> primary opcode because of their 16-bit instructions, so it has
> one bit less, and loses one bit due to having 16-bit instructions).
>
> It is rather hard to do anything useful with 16 bits with full 32
> registers. Does anybody have data how well RISC-V manages to
> reduce code size with their 16-bit instructions, and if there
> is performance degradation? Unfortunately, I have do not
> have access to a RISC-V machine to run my own analysis.

I have a related unread paper in my in-pile which
refers to RISC-V compare-and-branch fusion.
I have not seen much RISC-V performance analysis as
there is little to compare with x64 or Arm.

The Renewed Case for the Reduced Instruction Set Computer:
Avoiding ISA Bloat with Macro-Op Fusion for RISC-V 2016
https://arxiv.org/abs/1607.02318

On 2/12/22 03:35, Thomas Koenig wrote:
....snip...
>
> Slightly different topic: When talking about what to put into
> a half-sized instruction set, it is trivially true that
>
> mr ra,rb
> add ra,rc
>
> which could be made up of two n/2 bit instructions is equivalent to
>
> add ra,rb,rc
>
> which is a classic n-bit instuction, and could be fused into one.

This is the choice I made in the MCore instruction set where all instructions
where 16-bits. The statistics we saw then on code bases showed that
only about 15% (IIRC) of the instructions (statically) required the extra
register move. The MCore didn't last long enough for a version that
fused.

Brian

Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
> Thomas Koenig <tkoenig@netcologne.de> writes:
>>It is rather hard to do anything useful with 16 bits with full 32
>>registers. Does anybody have data how well RISC-V manages to
>>reduce code size with their 16-bit instructions, and if there
>>is performance degradation?
>
> Why should there be a performance degradation? If an instruction
> cannot be encoded in 16 bits, the 32-bit encoding is used.

Depends on what exactly the gode generator is doing (which is why
I was asking).

If it simply emits 16-bit assembler instructions for those 32-bit
insructions that happen to fit to the reduced subset, OK.

If it takes the reduced register set into account and arranges
registers differently, increases the number of instructions to fit
restricted register sizes, or even introduces addtional load/store
instructions, then it could indeed matter.

I simply don't know (which is why I asked).

>
> So the only question is how much the code size is reduced:
><https://arxiv.org/pdf/1607.02318.pdf> reports in Table III that RC64G
> has a factor 1.34 more dynamic instruction bytes than RV64GC (geomean
> over all benchmarks). It does not report static instruction bytes.
>
>>Unfortunately, I have do not
>>have access to a RISC-V machine to run my own analysis.
>
> RISC-V has been supported by QEMU for a long time. E.g., we tested
> Gforth on RISC-V (on QEMU) in 2018.

I don't think I will be setting up QEMU for that.

I could check the LoongArch machines, though.

On 2/12/2022 10:34 AM, Thomas Koenig wrote:
> Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>> Thomas Koenig <tkoenig@netcologne.de> writes:
>>> It is rather hard to do anything useful with 16 bits with full 32
>>> registers. Does anybody have data how well RISC-V manages to
>>> reduce code size with their 16-bit instructions, and if there
>>> is performance degradation?
>>
>> Why should there be a performance degradation? If an instruction
>> cannot be encoded in 16 bits, the 32-bit encoding is used.
>
> Depends on what exactly the gode generator is doing (which is why
> I was asking).
>
> If it simply emits 16-bit assembler instructions for those 32-bit
> insructions that happen to fit to the reduced subset, OK.
>

In "most" 16/32 ISA designs, this would presumably be the approach that
is used (use a 16-bit if it can be encoded as such, 32-bit otherwise).

> If it takes the reduced register set into account and arranges
> registers differently, increases the number of instructions to fit
> restricted register sizes, or even introduces addtional load/store
> instructions, then it could indeed matter.
>
> I simply don't know (which is why I asked).
>

FWIW: BGBCC does an optimization like that mentioned in size-optimized
mode (on BJX2), namely restricting most functions to the R0..R15 range,
and generally trying to allocate low-numbered registers before
high-numbered registers (when R16..R31 are enabled).

This approach is mostly abandoned in speed-optimized mode though (which
nearly always enables these, and prioritizes grabbing up a more
registers when possible, rather than spilling an existing value to the
stack).

A similar approach may be applicable to 32/64 registers, since the use
of R32..R63 comes with a cost in terms of code density and how much WEX
can be used (may cause 64-bit / Op64 encodings to be used, which require
64 bits to encode and can't be put in a bundle).

For now, the 64-bit ABI mostly ignores R32..R63, and the 128-bit ABI
uses them by default.

It is possible I could have add a special mode for the 64-bit ABI,
namely a "Enable use of R32..R63 if the register pressure is
sufficiently high" heuristic.

As noted, this is because most of the normal 32-bit encodings are
limited to a 5-bit register field.

Note, this will be N/A if XGPR is not enabled (it is treated as an
optional extension in the 64-bit ABI, only required for 128-bit; but
this is mostly because limiting the 128-bit ABI to 32 GPRs would have
the detrimental effect of significantly increasing the number of
register spills; I expect the 128-bit ABI to otherwise perform worse
than the 64-bit ABI, in general...).

>>
>> So the only question is how much the code size is reduced:
>> <https://arxiv.org/pdf/1607.02318.pdf> reports in Table III that RC64G
>> has a factor 1.34 more dynamic instruction bytes than RV64GC (geomean
>> over all benchmarks). It does not report static instruction bytes.
>>
>>> Unfortunately, I have do not
>>> have access to a RISC-V machine to run my own analysis.
>>
>> RISC-V has been supported by QEMU for a long time. E.g., we tested
>> Gforth on RISC-V (on QEMU) in 2018.
>
> I don't think I will be setting up QEMU for that.
>
> I could check the LoongArch machines, though.

On 2/12/2022 9:36 AM, EricP wrote:
> Thomas Koenig wrote:
>> Quadibloc <jsavard@ecn.ab.ca> schrieb:
>>> On Friday, February 11, 2022 at 11:28:53 AM UTC-7, MitchAlsup wrote:
>>>
>>>> If you can encode all the work of those 8 32-bit instructions in 7
>>>> 36-bit instructions, you are ahead of the game.
>>> That's true. But many people will be skeptical. After all, eight
>>> instructions do eight things, seven instructions do seven things.
>>
>> Compare and branch could profit a lot from more bits, 36 or 40.
>>
>> Assume
>>
>> - 6 bit primary opcode
>> - 10 bit for two registers to compare, or for a register and a
>>   constant
>> - 3 bits for comparison code
>>
>> you are left with either 13, 17 or 21 bits of offset for a 32,
>> 36 or 40 bit instruction word.  Subtract two bits if you have 64
>> registers / a 64-bit constant.  (RISC-V needs to have a 7-bit
>> primary opcode because of their 16-bit instructions, so it has
>> one bit less, and loses one bit due to having 16-bit instructions).
>>
>> It is rather hard to do anything useful with 16 bits with full 32
>> registers.  Does anybody have data how well RISC-V manages to
>> reduce code size with their 16-bit instructions, and if there
>> is performance degradation?  Unfortunately, I have do not
>> have access to a RISC-V machine to run my own analysis.
>
> I have a related unread paper in my in-pile which
> refers to RISC-V compare-and-branch fusion.
> I have not seen much RISC-V performance analysis as
> there is little to compare with x64 or Arm.
>
> The Renewed Case for the Reduced Instruction Set Computer:
> Avoiding ISA Bloat with Macro-Op Fusion for RISC-V 2016
> https://arxiv.org/abs/1607.02318
>
>

In my own testing (BJX2 has compare-and-branch as an optional feature),
the relative speed difference between this and a 2-op CMPxx+BT/BF, tends
to be small enough to mostly disappear in the noise.

Though, it can be noted though that BJX2 only has 2R encodings:
Bxx Rm, Rn, Lbl8

Whereas, a fair number of comparisons involve a constant, in which case,
say:
CMPGT 123, R4
BT .L0
And:
LDI 123, R5
BGT R5, R4, .L0
Are the same number of clock cycles.

In order to do any better than this, one would also require
compare-and-branch encodings which have an immediate field, say:
BGT 123, R4, .L0

But, this has the drawback of effectively requiring two immediate
fields: one for the compared value, another for the branch displacement.

Cost and timing would also seem to prefer the CMPxx+BT/BF scheme.
Also, the use of a flag bit is useful for predicated instructions:
if(x>255)
{
y=4*x+1;
}else
{
y=8*x-3;
}
As, say:
CMPGT 255, R4
SHAD?T R4, 2, R5 | SHAD?F R4, 3, R5
ADD?T R5, 1, R6 | SUB?F R5, 3, R6

And, unlike full condition-codes, this can be pulled off with ~ 2 bits
of entropy rather than ~ 4 (though, one could potentially also use 4
bits of entropy to encode 3 different predicate bits).

....

On Saturday, February 12, 2022 at 3:59:29 PM UTC-6, BGB wrote:
> On 2/12/2022 9:36 AM, EricP wrote:
> > Thomas Koenig wrote:
> >> Quadibloc <jsa...@ecn.ab.ca> schrieb:
> >>> On Friday, February 11, 2022 at 11:28:53 AM UTC-7, MitchAlsup wrote:
> >>>
> >>>> If you can encode all the work of those 8 32-bit instructions in 7
> >>>> 36-bit instructions, you are ahead of the game.
> >>> That's true. But many people will be skeptical. After all, eight
> >>> instructions do eight things, seven instructions do seven things.
> >>
> >> Compare and branch could profit a lot from more bits, 36 or 40.
> >>
> >> Assume
> >>
> >> - 6 bit primary opcode
> >> - 10 bit for two registers to compare, or for a register and a
> >> constant
> >> - 3 bits for comparison code
> >>
> >> you are left with either 13, 17 or 21 bits of offset for a 32,
> >> 36 or 40 bit instruction word. Subtract two bits if you have 64
> >> registers / a 64-bit constant. (RISC-V needs to have a 7-bit
> >> primary opcode because of their 16-bit instructions, so it has
> >> one bit less, and loses one bit due to having 16-bit instructions).
> >>
> >> It is rather hard to do anything useful with 16 bits with full 32
> >> registers. Does anybody have data how well RISC-V manages to
> >> reduce code size with their 16-bit instructions, and if there
> >> is performance degradation? Unfortunately, I have do not
> >> have access to a RISC-V machine to run my own analysis.
> >
> > I have a related unread paper in my in-pile which
> > refers to RISC-V compare-and-branch fusion.
> > I have not seen much RISC-V performance analysis as
> > there is little to compare with x64 or Arm.
> >
> > The Renewed Case for the Reduced Instruction Set Computer:
> > Avoiding ISA Bloat with Macro-Op Fusion for RISC-V 2016
> > https://arxiv.org/abs/1607.02318
> >
> >
> In my own testing (BJX2 has compare-and-branch as an optional feature),
> the relative speed difference between this and a 2-op CMPxx+BT/BF, tends
> to be small enough to mostly disappear in the noise.
>
>
> Though, it can be noted though that BJX2 only has 2R encodings:
> Bxx Rm, Rn, Lbl8
>
> Whereas, a fair number of comparisons involve a constant, in which case,
> say:
> CMPGT 123, R4
> BT .L0
> And:
> LDI 123, R5
> BGT R5, R4, .L0
> Are the same number of clock cycles.
>
> In order to do any better than this, one would also require
> compare-and-branch encodings which have an immediate field, say:
> BGT 123, R4, .L0
>
> But, this has the drawback of effectively requiring two immediate
> fields: one for the compared value, another for the branch displacement.
<
This was one of the driving factors in my adding complete immediates
and displacements to My 66000 ISA.
<
You can even do:
<
STD #1.23456789098765,[Rb+Ri<<3+1265874]
<
as a 4-word instruction.
<
But because it comes up so often:
<
STD #5,[SP+148]
<
as a 1 word instruction.
>
>
> Cost and timing would also seem to prefer the CMPxx+BT/BF scheme.
> Also, the use of a flag bit is useful for predicated instructions:
> if(x>255)
> {
> y=4*x+1;
> }else
> {
> y=8*x-3;
> }
> As, say:
> CMPGT 255, R4
> SHAD?T R4, 2, R5 | SHAD?F R4, 3, R5
> ADD?T R5, 1, R6 | SUB?F R5, 3, R6
<
CMP Rt,Rx,#255
PCGT Rt,{0011}
SLA Ry,Rx,#2
ADD Ry,Ry,#1
SLA Ry,Rx,#3
ADD Ry,Ry,#-3
<
Anything but a simple 1-wide in order machine will CoIssue the CMP and BC.
>
> And, unlike full condition-codes, this can be pulled off with ~ 2 bits
> of entropy rather than ~ 4 (though, one could potentially also use 4
> bits of entropy to encode 3 different predicate bits).
<
There is no ISA entropy wasted. There is PSQW entropy.
>
> ...

On 2/12/2022 3:26 PM, MitchAlsup wrote:
> On Saturday, February 12, 2022 at 3:59:29 PM UTC-6, BGB wrote:
>> On 2/12/2022 9:36 AM, EricP wrote:
>>> Thomas Koenig wrote:
>>>> Quadibloc <jsa...@ecn.ab.ca> schrieb:
>>>>> On Friday, February 11, 2022 at 11:28:53 AM UTC-7, MitchAlsup wrote:
>>>>>
>>>>>> If you can encode all the work of those 8 32-bit instructions in 7
>>>>>> 36-bit instructions, you are ahead of the game.
>>>>> That's true. But many people will be skeptical. After all, eight
>>>>> instructions do eight things, seven instructions do seven things.
>>>>
>>>> Compare and branch could profit a lot from more bits, 36 or 40.
>>>>
>>>> Assume
>>>>
>>>> - 6 bit primary opcode
>>>> - 10 bit for two registers to compare, or for a register and a
>>>> constant
>>>> - 3 bits for comparison code
>>>>
>>>> you are left with either 13, 17 or 21 bits of offset for a 32,
>>>> 36 or 40 bit instruction word. Subtract two bits if you have 64
>>>> registers / a 64-bit constant. (RISC-V needs to have a 7-bit
>>>> primary opcode because of their 16-bit instructions, so it has
>>>> one bit less, and loses one bit due to having 16-bit instructions).
>>>>
>>>> It is rather hard to do anything useful with 16 bits with full 32
>>>> registers. Does anybody have data how well RISC-V manages to
>>>> reduce code size with their 16-bit instructions, and if there
>>>> is performance degradation? Unfortunately, I have do not
>>>> have access to a RISC-V machine to run my own analysis.
>>>
>>> I have a related unread paper in my in-pile which
>>> refers to RISC-V compare-and-branch fusion.
>>> I have not seen much RISC-V performance analysis as
>>> there is little to compare with x64 or Arm.
>>>
>>> The Renewed Case for the Reduced Instruction Set Computer:
>>> Avoiding ISA Bloat with Macro-Op Fusion for RISC-V 2016
>>> https://arxiv.org/abs/1607.02318
>>>
>>>
>> In my own testing (BJX2 has compare-and-branch as an optional feature),
>> the relative speed difference between this and a 2-op CMPxx+BT/BF, tends
>> to be small enough to mostly disappear in the noise.
>>
>>
>> Though, it can be noted though that BJX2 only has 2R encodings:
>> Bxx Rm, Rn, Lbl8
>>
>> Whereas, a fair number of comparisons involve a constant, in which case,
>> say:
>> CMPGT 123, R4
>> BT .L0
>> And:
>> LDI 123, R5
>> BGT R5, R4, .L0
>> Are the same number of clock cycles.
>>
>> In order to do any better than this, one would also require
>> compare-and-branch encodings which have an immediate field, say:
>> BGT 123, R4, .L0
>>
>> But, this has the drawback of effectively requiring two immediate
>> fields: one for the compared value, another for the branch displacement.
> <
> This was one of the driving factors in my adding complete immediates
> and displacements to My 66000 ISA.
> <
> You can even do:
> <
> STD #1.23456789098765,[Rb+Ri<<3+1265874]
> <
> as a 4-word instruction.
> <
> But because it comes up so often:
> <
> STD #5,[SP+148]
> <
> as a 1 word instruction.

Can do a couple of bits better than that, depending on member, but in
two instructions. Only one bundle though, and only one cycle to issue
due to phasing. Your real advantage IMO is that you don't need a
register (var. belt position) to hod the value stored.
>>
>>
>> Cost and timing would also seem to prefer the CMPxx+BT/BF scheme.
>> Also, the use of a flag bit is useful for predicated instructions:
>> if(x>255)
>> {
>> y=4*x+1;
>> }else
>> {
>> y=8*x-3;
>> }
>> As, say:
>> CMPGT 255, R4
>> SHAD?T R4, 2, R5 | SHAD?F R4, 3, R5
>> ADD?T R5, 1, R6 | SUB?F R5, 3, R6
> <
> CMP Rt,Rx,#255
> PCGT Rt,{0011}
> SLA Ry,Rx,#2
> ADD Ry,Ry,#1
> SLA Ry,Rx,#3
> ADD Ry,Ry,#-3
> <
> Anything but a simple 1-wide in order machine will CoIssue the CMP and BC.

Which is why compare-and-branch is two instruction (in one bundle) on
Mill, effectively co-issuing. Once you abandon fixed instruction sizes
and have them bit-sized to the entropy minimum then there's no longer
any gain from packing/cracking schemes; just unnecessary monkey-puzzle.

>>
>> And, unlike full condition-codes, this can be pulled off with ~ 2 bits
>> of entropy rather than ~ 4 (though, one could potentially also use 4
>> bits of entropy to encode 3 different predicate bits).
> <
> There is no ISA entropy wasted. There is PSQW entropy.
>>
>> ...

Ivan Godard <ivan@millcomputing.com> schrieb:

> Which is why compare-and-branch is two instruction (in one bundle) on
> Mill, effectively co-issuing. Once you abandon fixed instruction sizes
> and have them bit-sized to the entropy minimum then there's no longer
> any gain from packing/cracking schemes; just unnecessary monkey-puzzle.

And if you do that (and have really hit something close to the
minimum, which will vary depending on applications) you no longer
have a realistic chance of extending your ISA, so you need to
recompile (or specialize, as I think you call it) from source or
from an intermediate representation.

No such thing as an ISA free of drawbacks :-)

On 2/13/2022 1:37 AM, Thomas Koenig wrote:
> Ivan Godard <ivan@millcomputing.com> schrieb:
>
>> Which is why compare-and-branch is two instruction (in one bundle) on
>> Mill, effectively co-issuing. Once you abandon fixed instruction sizes
>> and have them bit-sized to the entropy minimum then there's no longer
>> any gain from packing/cracking schemes; just unnecessary monkey-puzzle.
>
> And if you do that (and have really hit something close to the
> minimum, which will vary depending on applications) you no longer
> have a realistic chance of extending your ISA, so you need to
> recompile (or specialize, as I think you call it) from source or
> from an intermediate representation.
>
> No such thing as an ISA free of drawbacks :-)

Yes; that's a problem whenever there's a execution-level representation
of code that is below the distribution level. The distribution
representation must be translated to the execution level.

In Mill the translation happens once, at install time, via a transparent
invocation of the specializer (not a recompile, and the source code is
not needed). In a microcoded machine (or a packing/cracking scheme) the
translation takes place at execution time, every time. Either way, it
gets done, and either way permits ISA extension freely. They differ in
power, area, and time; the choice is an engineering design dimension.

I assert without proof that Mill-style software translation in fact
permits ISA extension that is *more* flexible and powerful than what can
be achieved by hardware approaches. YMMV.

Ivan Godard <ivan@millcomputing.com> schrieb:
> On 2/13/2022 1:37 AM, Thomas Koenig wrote:

>> And if you do that (and have really hit something close to the
>> minimum, which will vary depending on applications) you no longer
>> have a realistic chance of extending your ISA, so you need to
>> recompile (or specialize, as I think you call it) from source or
>> from an intermediate representation.
>>
>> No such thing as an ISA free of drawbacks :-)
>
> Yes; that's a problem whenever there's a execution-level representation
> of code that is below the distribution level. The distribution
> representation must be translated to the execution level.
>
> In Mill the translation happens once, at install time, via a transparent
> invocation of the specializer (not a recompile, and the source code is
> not needed). In a microcoded machine (or a packing/cracking scheme) the
> translation takes place at execution time, every time. Either way, it
> gets done, and either way permits ISA extension freely. They differ in
> power, area, and time; the choice is an engineering design dimension.
>
> I assert without proof that Mill-style software translation in fact
> permits ISA extension that is *more* flexible and powerful than what can
> be achieved by hardware approaches.

I think the

>YMMV.

is superfluous - if you basically get to rewrite your ISA for each
specific processor, same as TIMI for the AS/400 ff. (which also
recompiles).

If there is anything more flexible than that, I would like to know
what it should look like :-)

On Sunday, February 13, 2022 at 4:51:26 AM UTC-7, Thomas Koenig wrote:
> if you basically get to rewrite your ISA for each
> specific processor,

My understanding is that while the native code of different Mill processors
is different, the form of code that compilers generate which is publicly
specified is constant.

This is still a constraint - think of the IBM 360, where different models used
their own microcode language.

John Savard

On Friday, February 11, 2022 at 4:11:16 PM UTC-7, Thomas Koenig wrote:

> It is rather hard to do anything useful with 16 bits with full 32
> registers.

What I've done in my recent designs is to specify the two registers used in
an instruction with only 8 bits; five specify the destination register, and the
source register must belong to the same group of eight registers as the
destination register.

Since the idea is to allow more instructions to run in parallel by having
multiple interleaved threads of instructions that work with different registers,
this fits right in.

John Savard

On Sunday, February 13, 2022 at 8:57:24 AM UTC-6, Quadibloc wrote:
> On Friday, February 11, 2022 at 4:11:16 PM UTC-7, Thomas Koenig wrote:
>
> > It is rather hard to do anything useful with 16 bits with full 32
> > registers.
> What I've done in my recent designs is to specify the two registers used in
> an instruction with only 8 bits; five specify the destination register, and the
> source register must belong to the same group of eight registers as the
> destination register.
<
I think you may find this negatively impacts your code when running your
ABI.
<
For example, My 66000 ABI passes arguments to functions in R1-R9, returns
results in R1-R9, and preserves R16-R31 across function calls, with Rlow-R15
freely available as temp registers.
<
Let us postulate a subroutine that allocates a dynamically sized array which
arrives as a parameter, but ultimately wants to get subtracted from the stack
pointer R31 to allocate the array.
>
> Since the idea is to allow more instructions to run in parallel by having
> multiple interleaved threads of instructions that work with different registers,
> this fits right in.
>
> John Savard

Quadibloc wrote:
> On Friday, February 11, 2022 at 4:11:16 PM UTC-7, Thomas Koenig wrote:
>
>> It is rather hard to do anything useful with 16 bits with full 32
>> registers.
>
> What I've done in my recent designs is to specify the two registers used in
> an instruction with only 8 bits; five specify the destination register, and the
> source register must belong to the same group of eight registers as the
> destination register.
>
> Since the idea is to allow more instructions to run in parallel by having
> multiple interleaved threads of instructions that work with different registers,
> this fits right in.
>
> John Savard

The term "strands of execution" might be better than
overloading the term thread.

I don't see how these two concepts of register sets and strands connect.
The decoder internally maps the 2 register instruction into
the same 3 register uOp as a 3 register format would use.
The restriction of second register being in the same 2-bit set
only matters to the compiler register selector, not the uOp.
If the forwarding network can execute dependent instructions
back to back, then which strand an instruction is for doesn't matter.

For something like this to matter there would have to be an
asymmetry between accessing or forwarding between register sets.
That seems a pretty niche implementation target for an ISA.

> In Mill the translation happens once, at install time, via a transparent
> invocation of the specializer (not a recompile, and the source code is not
> needed).

Of course, for JIT compilers, "install time" is also run time, making it
important to have a fast(ish?) way to specialize for the target CPU.

It can also make it harder to do things like migrate a VM from one CPU
to another (or for things like big.LITTLE).

Stefan

On 2/13/2022 6:53 AM, Quadibloc wrote:
> On Sunday, February 13, 2022 at 4:51:26 AM UTC-7, Thomas Koenig wrote:
>> if you basically get to rewrite your ISA for each
>> specific processor,
>
> My understanding is that while the native code of different Mill processors
> is different, the form of code that compilers generate which is publicly
> specified is constant.
>
> This is still a constraint - think of the IBM 360, where different models used
> their own microcode language.

I think that is different. Think of the difference between an
interpreter and a compiler. In this analogy, each 360 model is a
different interpreter for the same "language", while the Mill Specifier
is like a cross compiler with the ability to target different processors
from the same source.

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