From: ThatWouldBeTelling@thevillage.com
Thomas Koenig wrote:
> EricP schrieb:
>> Thomas Koenig wrote:
>>> Stefan Monnier schrieb:
>>>>>> Well, Mitch claims average 35 bits per instructions, that means about
>>>>>> 90% utilization of decoders, so not bad.
>>>>> His minimum instruction size is 32 bits, but I was going for 16 bits.
>>>> BTW, my understanding of Mitch's design is that this is related to
>>>> instruction complexity: if you support 16bit instructions, it means you
>>>> support instructions which presumably don't do very much work because
>>>> it's hard to express a lot of "work to do" in 16bit.
>>> A bit of statistics on that.
>>>
>>> Using a primitive Perl script to catch occurences, on a recent
>>> My 66000 cmopiler, of the shape
>>>
>>> [op] Ra,Ra,Rb
>>> [op] Ra,Rb,Ra
>>> [op] Ra,#n,Ra
>>> [op] Ra,Ra,#n
>>> [op] Ra,Rb
>>>
>>> where |n| < 32, which could be a reasonable approximation of a
>>> compressed instruction set, yields 14.9% (Perl), 16.6% (gnuplot)
>>> and 23.9% (GSL) of such instructions. Potential space savings
>>> would be a bit less than half that.
>>>
>>> Better compression schemes are certainly possible, but I think the
>>> disadvantages of having more complex encodings outweigh any
>>> potential savings in instruction size.
>> The % associations you measured above might just be coincidence.
>>
>> I have assumed for a compiler to choose between two instruction formats,
>> a 2-register Rsd1 = Rsd1 OP Rs2, and a 3-register Rd1 = Rs2 OP Rs3,
>> that the register allocator would check if either operand was alive after
>> the OP, and if not then that source register can be reused as the dest.
>> For some ISA that may allow a shorter instruction format to be used.
>
> Compilers will try to re-use registers as much as possible, in
> other words, to avoid dead registers. If the compiler determines
> that, for the pseudo registers V1, V2 and V3,
>
> V1 = V2 - V3;
>
> V2 is no longer live after that statement, it will assign
> the same hard register to V1 and V2 (unless there are other
> considerations such as function return values) which will then
> either be translated into
>
> add r1,r1,-r2
>
> for a three-register instruction, or, for example, into
>
> subq %rsi, %rax
>
> Hmm... thinking of the statistics above, maybe I should have
> included the minus signs.
>
>> Your stats above assume the compiler is performing this optimization
>> but since My 66000 does not have short format instructions the compiler
>> would have no reason to do so. Or the compiler might be doing this
>> optimization anyways for other ISA such as x86/x64 which do have
>> shorter formats.
>>
>> So the % numbers you measured might just be coincidence and could be low.
>> An ISA with both short 2- and long 3- register formats like RV where there
>> is an incentive to do this optimization might provide stats confirmation.
>
> RISC-V compressed mode also uses three-bit register numbers for
> popular registers, all of which complicates decoding and causes
> other problems which Mitch has explained previously.
>
> So yes, a My 66000-like instruction set with compression might be
> possible, but would almost certainly not be realized.
I wasn't suggesting My 66000 should be using compressed instructions.
Just that the the stats you got from its obj code might not apply
because extra optimization work is required to coerce values to be
in the right registers so it can take advantage of size compression.
The packing algorithm I described above should work for my ISA because I
have the same number of registers, 16, in all instruction size variations.
The packing algorithm for RV or similar is more complicated because
it uses different register set sizes, RV is 31 or 7 with a zero reg.
After identifying which variables die in each operation,
the register allocator has to "arrange" that the dying variable lands
in one of those 7 registers so that the dying op can reuse the register.
This also interacts with the ABI in passing register arguments.
E.g. maybe it gets better compression if the stack pointer is
one of those 7 registers. Also remember the RV ABI needs I think
1 or 2 registers for building a 32-bit RIP-relative branch address.
Compact instructions may also have smaller immediate fields.
An optimizer might try to arrange stack variable offset locations
so that the more frequent ones use the small offsets.
A bit of poking about finds a number of research papers on compact ISA's.
This one explores their improved algorithm on LLVM.
Fig. 2 shows the % share of compact instructions before and after
their compression-aware algorithms. Just eye-balling the graph I'd
say 50% of RV instructions used compressed format.
Register Allocation for Compressed ISAs in LLVM 2023
https://dl.acm.org/doi/pdf/10.1145/3578360.3580261
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
