Re: "Mini" tags to reduce the number of op codes

Terje Mathisen wrote:

MitchAlsup1 wrote:

Anton Ertl wrote:
>

I have a similar problem for the carry and overflow bits in
< http://www.complang.tuwien.ac.at/anton/tmp/carry.pdf >, and chose to
let those bits not survive across calls; if there was a cheap solution
for the problem, it would eliminate this drawback of my idea.

>
My 66000 ISA can encode the mpn_add_n() inner loop in 5-instructions
whereas RISC-V encodes the inner loop in 11 instructions.
>
Source code:
>
void mpn_add_n( uint64_t sum, uint64_t a, unit64_t b, int n )
{
 Â Â Â  uint64_t c = 0;
 Â Â Â  for( int i = 0; i < n; i++ )
 Â Â Â  {
 Â Â Â Â Â Â Â Â  {c, sum[i]} = a[i] + b[i] + c;
 Â Â Â  }
 Â Â Â  return
}
>
Assembly code::
>
 Â Â Â  .global mpn_add_n
mpn_add_n:
 Â Â Â  MOV   R5,#0     // c
 Â Â Â  MOV   R6,#0     // i
>
 Â Â Â  VEC   R7,{}
 Â Â Â  LDD   R8,[R2,Ri<<3]
 Â Â Â  LDD   R9,[R3,Ri<<3]
 Â Â Â  CARRY R5,{{IO}}
 Â Â Â  ADD   R10,R8,R9
 Â Â Â  STD   R10,[R1,Ri<<3]
 Â Â Â  LOOP  LT,R6,#1,R4
 Â Â Â  RET
>
So, adding a few "bells and whistles" to RISC-V does give you a
performance gain (1.38×); using a well designed ISA gives you a
performance gain of 2.00× !! {{moral: don't stop too early}}
>
Note that all the register bookkeeping has disappeared !! because
of the indexed memory reference form.
>
As I count executing instructions, VEC does not execute, nor does
CARRY--CARRY causes the subsequent ADD to take C input as carry and
the carry produced by ADD goes back in C. Loop performs the ADD-CMP-
BC sequence in a single instruction and in a single clock.

    ; RSI->a[n], RDX->b[n], RDI->sum[n], RCX=-n
   xor rax,rax ;; Clear carry
next:
   mov rax,[rsi+rcx*8]
   adc rax,[rdx+rcx*8]
   mov [rdi+rcx*8],rax
   inc rcx
    jnz next
 The code above is 5 instructions, or 6 if we avoid the load-op, doing two loads and one store, so it should only be limited by the latency of the ADC, i.e. one or two cycles.
 In the non-OoO (i.e Pentium) days, I would have inverted the loop in order to hide the latencies as much as possible, resulting in an inner loop something like this:
   next:
   adc eax,ebx
   mov ebx,[edx+ecx*4]    ; First cycle
    mov [edi+ecx*4],eax
   mov eax,[esi+ecx*4]    ; Second cycle
    inc ecx
    jnz next        ; Third cycle
 

In the same bad old days, the standard way to speed it up would have used unrolling, but until we got more registers, it would have stopped itself very quickly. With AVX2 we could use 4 64-bit slots in a 32-byte register, but then we would have needed to handle the carry propagation manually, and that would take longer than a series of ADC/ADX instructions.
next4:
   mov eax,[esi]
   adc eax,[esi+edx]
   mov [esi+edi],eax
   mov eax,[esi+4]
   adc eax,[esi+edx+4]
   mov [esi+edi+4],eax
   mov eax,[esi+8]
   adc eax,[esi+edx+8]
   mov [esi+edi+8],eax
   mov eax,[esi+12]
   adc eax,[esi+edx+12]
   mov [esi+edi+12],eax
   lea esi,[esi+16]
   dec ecx
    jnz next4
Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"