Re: Tonights Tradeoff - Carry and Overflow

On 10/12/2024 5:20 PM, Robert Finch wrote:

On 2024-10-12 4:14 p.m., BGB wrote:

On 10/12/2024 1:50 PM, MitchAlsup1 wrote:

On Sat, 12 Oct 2024 9:38:01 +0000, Robert Finch wrote:
>

On 2024-10-09 6:44 a.m., Robert Finch wrote:
Mulled over carry and overflow in arithmetic operations. Looked at
widening the datapath to 66-bits to hold carry and overflow bits.
Thinking it may increase the size of the design by over 3% just to
support carry and overflow. For now, an instruction, ADDGC, was added to
generate the carry bit as a result. A 256-bit add looks like:
>
; 256 bit add
; A = r1,r2,r3,r4
; B = r5,r6,r7,r8
; S = r9,r10,r11,r12
>
    add r9,r1,r5,r0
    addgc r13,r1,r5,r0
    add r10,r2,r6,r13
    addgc r13,r2,r6,r13
    add r11,r7,r3,r13
    addgc r13,r7,r3,r13
    add r12,r8,r4,r13

>
My 66000 version::
>
       CARRY   R8,{{IO}{IO}{IO}{O}}
       ADD     R4,R12,R16
       ADD     R5,R13,R17
       ADD     R6,R14,R18
       ADD     R7,R15,R19
            // R{8,7,6,5,4} contain the 257-bit result.
>
256-bit add giving 257-bit result.

>
BJX2 / XG2, assuming in-register (A/D=R4..R7, B=R20..R23):
   CLRT
   ADDC  R20, R4
   ADDC  R21, R5
   ADDC  R22, R6
   ADDC  R23, R7
>
Or, D=R16..R19
   MOV.X R4, R16
   MOV.X R6, R18
   CLRT
   ADDC  R20, R16
   ADDC  R21, R17
   ADDC  R22, R18
   ADDC  R23, R19
>
ADDC is itself mostly a holdover from SH.
>
Could almost make sense to make it have a 3R form though and move it to updating SR.S instead, since SR.T is likely better left exclusively to predication (vs mostly predication, and obscure edge-case ops like ADDC/ SUBC/ROTCL/...).
>
Could almost add an ADDC.X op which operates 128 bits at a time, say:
   CLRT
   ADDC.X R4, R20, R16
   ADDC.X R6, R22, R18
>
Except that it would be rarely used enough to make its existence debatable at best.
>
>

>
Not very elegant a solution, but it is simple. I think it requires
minimal hardware. Three input ADD is already present and ADDGC just
routes the carry bit to the output.

>

BJX2 / XG2 has destroys the value of the one source operand, I noted the extra code to preserve the one operand. Is that only for the ADDC instruction?
 

In this case, ADDC/SUBC were destructive 2R because:
   Originally, in SH4 and BJX1, they were destructive 2R;
   They were not common enough to justify spending 3R encodings on them;
   But, still common enough to justify not dropping them entirely.
So, for example:
   ADD is 3R;
   But, ADDC/SUBC (aka ADC/SBB), are only 2R.
Early on, I ended up adding both 2R and 3R versions of many instructions, but ended up later dropping a lot of the 32-bit 2R encodings after noting that they were entirely redundant. ADDC/SUBC lived on as 2R as they were never given 3R variants.
And, in turn, cases where one needs to implement large ALU types are infrequent, and usually for 256-bit integers or similar, one doesn't care that they were slow.
For 128-bit types, they ended up with designated ALU instructions, and if one has a 128-bit ADD.X/SUB.X and friends, this eliminated much of the use-case for ADDC (so, less incentive to give it a 3R type).
Where, ADD.X and friends reclaimed encoding space that had originally been used for "ADD Rm, Imm5u, Rn" and similar; but These were dropped after the "ADD Rm, Imm9u, Rn" and similar encodings were added.
Similar was originally also true of the Imm5u Load/Store encodings, but these ended up coming back later, as some later encoding edge cases required them to exist.
The original migration to Imm9u having been because Imm5u was not sufficient (In XG2, many of the Imm9u encodings became either Imm10u or Imm10s).
Ironically, while 9u or 10s is still smaller than the Imm12s that RISC-V uses, the relative difference was smaller:
The hit/miss difference is a lot smaller;
It had dealt more gracefully with the cases where the immediate had missed (RISC-V had lacked any sort of "graceful" fallback; and a typical best case of "LUI+ADDI+OP", kinda sucks...).
As can be noted, as-is, RISC-V also lacks any good way to deal with large integer arithmetic. But, then again, it is infrequent and usually not significant to performance.

What is the limit on the My66000 CARRY modifier for the number of carries? Assuming the sequence is interruptible there must be a few bits of state that need to be preserved.
I found incorporating modifiers have a tendency to turn my code into spaghetti. Maybe my grasp of implementation is not so great though.
 The add, addgc can execute at the same time. So, it is 4 clocks at the worst to add two 256-bit numbers. (The first / last instructions may execute at the same time as other instructions).
I wanted to avoid using instruction modifiers and special flags registers as much as possible. It is somewhat tricky to have a carry flag in flight. Q+ is not very code dense, but the add can be done. It is also possible to put the carry bit in a predicate register.