Are you guys using EOR that much? Personally, I don't use it much but I could see it used frequently for particular uses. Adding EOR.size EA,Dn would need to be a word encoding to be worthwhile and word encodings do take up a lot of encoding space.

Would you mind posting the workloop for us as reference?

I agree, this would be a real improvement, given that most subroutines start with saving the register set on the stack.

Greetings,
Thomas

You need a SIMD unit with binary operations support, so your loop will be A LOT faster.

I understand that the current fusion design will enable the following 4 instructions in 2 cycles(N050) and 1 cycle in (N070) with superscalar.

move.l d0,d1
swap d1  ;usefull for 16:16 fixed point

move.l d2,d3
lsr.l #8,d3  ;usefull for 8:8 fixed point

How about these:

add.l d0,d1
swap d1

or.l d0,d1
swap d1

sub.l d0,d1
swap d1

muls.l d0,d1
swap d1

eor.l d0,d1
swap d1

neg.l d1
swap d1

2 reads and 1 write..

etc..

Here are two common merge pass in Chunky2Planar conversion routines. The merges can also be used when combining 2 buffers with shadetables

input:

d0=ABCD
d2=abcd

output:

d0=AaCc
d2=BbDd

  move.l d2,d3 ;swap 8 (d2,d4)
  lsr.l #8,d3
  eor.l d4,d3
  and.l d7,d3 ;d7=0x00ff00ff
  eor.l d3,d4
  lsl.l #8,d3
  eor.l d3,d2

input:

d0=AABB
d2=aabb

output:

d0=AAaa
d2=BBbb

  move.l d2,d4  ;swap 16 (d0Xd2)
  move.w d0,d4
  swap d4
  move.w d4,d0
  move.w d2,d4

Most amiga programs wich contain chunky graphics will use a variation of these merges.
So I suggest a new instruction

c2pmerge d0,d2,#n  (n=1,2,4,8,16)

The new N050 can interpretate 128bits per clock

That meens that it can look at 8 (16 bit) instructions and search for a pattern per clock..

The first c2pmerge is 7 Instructions(112 bit wide)
The second c2pmerge is 5 Instructions(80 bit wide)

Can they be fused?

However, if enough space is available, and EOR gets new addressing modes, I could speed up my program even further, because the fusion could be made with (perhaps) the next instruction in my program.

Megol . wrote:

Not overwriting registers is (again IIRC) handled by instruction fusion

Matt Hey wrote:

We have been discussing how valuable and needed 3 op instructions are in the 68k. ...but it's not that much of a priority because code fusion is so good and speeds up existing 68k code.

Ok. To me it sounds like fusion is a good replacement for 3 OP instructions.

Megol . wrote:

Lookup tables would be "free" in the N68 design as long as it hits cache. Complicating the cache access path for this special case would slow down general code execution.

Matt Hey wrote:

There would be no locking method but if you are not using too much data then the data will stay in the cache.

Ok. However, in my case, there are 2 parts of the program that I want to make use of the cache, but 1 of them (the 1st) will probably "mess up" the cache for the other one:
1) The outer loop, which loops through each byte in a file (which can be large).
2) The inner loop. For each byte in the outer loop, it uses the byte to fetch a longword from the correct position in the lookup table.

I guess the problem with the automatic cache in this case, is that the outer loop after a while will fill the cache, thus removing the "lookup table" from the cache.
It would be great if the CPU could manage to cache the data read in the outer loop without removing the "lookup table" from the cache.

Matt Hey wrote:

A series of TST.L (An) in a loop with An pointing to the start of each cache line (16 bytes) in the table will work to force data caching.

Good idea. I have to test this out.

Gunnar von Boehn wrote:

One question: You said you precalculate values for the CRC. How does this algorithm work? What are you precalculating in detail, how many instructions would it take to calculate this on the fly?

It is no option to calculate on the fly, because it requires a series of bitwise shifting and an Eor (in worst case scenario) for each bit shifted.
See documented example code below (uses a precalculated lookup table).
Calculating "on the fly" can be done by something similar as the "Calc_CRC_longword" subroutine below.

Start:
  Bsr.s Calc_CRC_table  ; Create the CRC lookup table

  ; Calculate CRC checksum of our string.
  Lea TestString(PC),a0 ; String to check
  Lea CRC_Table(PC),a1 ; CRC lookup table
  Moveq.l #-1,d0  ; Initialize result value
  Moveq.l #0,d2
.ByteLP Move.b (a0)+,d2
  Beq.s .End
      Eor.b d0,d2
  Lsr.l        #8,d0
      Move.l (a1,d2.w*4),d3
      Eor.l        d3,d0
  Bra.s .ByteLP
.End Not.l d0
  Rts

; Precalculates 256 LONGWORDs (for values 0-255), and stores them in memory.
Calc_CRC_table:
  Move.l #255,d6
  Moveq.l #0,d1
  Lea CRC_Table(PC),a1
.Loop Movem.l d1/d6/a1,-(sp)
  Bsr.s Calc_CRC_longword
  Movem.l (sp)+,d1/d6/a1
  Move.l d0,(a1)+
  Addq.l #1,d1
  Dbf d6,.Loop
  Rts

; Precalculates 1 LONGWORD.
; For every 8 bits in the source BYTE, the loop does this:
;  1) Shifts source BYTE 1 bit right
;  2) Shifts result LONGWORD 1 bit right
;  3) If ONLY 1 of the 2 outshifted bits is 1,
;    EOR the result (d0) with the QUOTIENT.
;
; INPUT PARAMETER:
;    d1=Source BYTE (the byte to precalculate a code for).
;    You can change this between 0 and 255.
;      Test values (Source leads to this result in d0):
;    0 = $00000000
;    1 = $77073096
;    2 = $ee0e612c
;    3 = $990951ba
;    4 = $076dc419
;
Calc_CRC_longword:
  Move.l #$EDB88320,d5 ; QUOTIENT
  Moveq.l #0,d0 ; Result LONGWORD. Don't change this.

  Moveq #7,d7
.Loop Lsr.b        #1,d1
  Scs.b d2
  Lsr.l        #1,d0
  Scs.b d3
  Eor.b d2,d3
  Extb.l d3
  And.l d5,d3
  Eor.l        d3,d0
  Dbf          d7,.Loop
  Rts

CRC_table: ds.l 256

TestString: dc.b "AB",0  ; NULL-terminated string.
;Testresults: "A"=D3D99E8B, "AB"=30694C07

Lookup table's cache lines will not be evicted, since the whole LUT needs only 1KB of space (consider, however, to proper align it at 16 or 32 bytes bounds, depending on the CPU).

If your outer loop works with a file, usually it'll use a little buffer (128 bytes is a common value) to read (or write) data from it, so it will stay entirely on a few cache lines.

The same applies if the o.s. does file block cache (AmigaOS does not, if I remember correctly), since blocks are usually small (512 bytes for AmigaOS, 1KB for old Unixes, 4KB for modern o.s. filesystems).

Ok lets look at your code and lets analyse it.
1) So first let look at it optimistic.

The MOVE and the EOR can not be fused as the combination does not use the same DST.
 
 
  But a SuperScalar CPU could forward to result to the second ALU.
  Here is the number of cycles the workloop will take.
  By slightly changing the code you can remove one instruction and get down from 7 to 6 instructions for the inner loop.
 
 

                                         68050            68070
  ByteLP:
    Move.b  (a0)+,d2                       1                1
    Beq.s  End                             2                1 
    Eor.b  d0,d2                           3                2 
    Lsr.l  #8,d0                           4                2        
    Move.l (a1,d2.w*4),d3                  5                3
    Eor.l  d3,d0                           6                3 *Forwarding
    Bra.s  ByteLP                          7                3
  

    bra.b Start
  ByteLP:
    Eor.b  d0,d2                           1                1
    Lsr.l  #8,d0                           2                1
    Move.l (a1,d2.w*4),d3                  3                2 
    Eor.l  d3,d0                           4                2 *Forwarding
  Start:          
    Move.b  (a0)+,d2                       5                3 
    Bne.s  Loop                            6                3
  

In this special case having a EOR ea,Dn would be beneficial as you could then write it like this:

    bra.b Start
  ByteLP:
    Eor.b  d0,d2                           1                1
    Lsr.l  #8,d0                           2                1
    EOR.l (a1,d2.w*4),d0                   3                2 
  Start:          
    Move.b  (a0)+,d2                       4                2 
    Bne.s  Loop                            5                2
  

This would get the workloop down from 3 cycles to 2 cycles for the 070.  This would be rather swift then.

2) Now lest look at the code realistic
 

    bra.b Start
  ByteLP:
    Eor.b  d0,d2                           1                1
    Lsr.l  #8,d0                           2                1
    -- ALU to EA flow usage penalty of 1/2 cycles!!
    Move.l (a1,d2.w*4),d3                  3,4              2,3,4 
   
    Eor.l  d3,d0                           5                2,3,4 *Forwarding
  Start:          
    Move.b  (a0)+,d2                       6                5 
    Bne.s  Loop                            7                5
  

The table lookup using Index will loose performance on 68050, 68060 and 68070. You could try to rework the code to get the D2 update and the D2 usage further apart from each other.

      ByteLP:
        Mvz.b  (a0)+,d2
        Beq.s  End
        Eor.l  d0,d2 
        Lsr.l  #8,d0
        Move.l (a1,d2.l*4),d3
        Eor.l  d3,d0
        Bra.s  ByteLP
      

       ByteLP:
         Mvz.b  (a0)+,d2
         Beq.s  End
         Eor.l  d0,d2 
         Lsr.l  #8,d0
         Move.l (a1,d2.l*4),d3
         Eor.l  d3,d0
         Bra.s  ByteLP
       

Where would be the benefit of this change?

Matt Hey wrote:

It looks like an immediate can be extended for free in a code fusion but can a register be extended for free also?             moveq #7,d0 ;free extb.l         eor.l d0,d1

Sorry this does not work.
The requirement for fusing is that the destinations of BOTH instructions are the same. This means only one destination has to be updated by both instructions.
Your example will update two registers - Therefore it can't be fused.

Cheers

My simple attempt to optimize it a bit by making the move and eor potentially fusionable.

  move.b (a0)+,d2
  beq.s .end
.nextbyte
  eor.b d0, d2
  lsr.l #8, d0
  move.l (a1,d2.w*4), d3
  eor.l d0, d3          ; d3 replaces d0
  move.b (a0)+, d2
  beq.s .end2

  eor.b d3, d2
  lsr.l #8, d3
  move.l (a1, d2.w*4), d0
  eor.l d3, d0          ; d0 is now the crc again
  move.b (a0)+, d2
  bne.s .nextbyte
.end
  mov d0, d3           
.end2
  ; here d3 is the crc value...

            ByteLP:
              Mvz.b  (a0)+,d2
              Beq.s  End
              Eor.l  d0,d2 
              Lsr.l  #8,d0
              Move.l (a1,d2.l*4),d3
              Eor.l  d3,d0
              Bra.s  ByteLP
            

       Lea TestString(PC),a0 ; String to check
       Lea CRC_Table(PC),a1 ; CRC lookup table
       Moveq.l #0,d2
       Moveq.l #-1,d0  ; Initialize result value
     .ByteLP Move.b (a0)+,d2
       Beq.s .End
       Eor.b d0,d2
       Lsr.l #8,d0
       Move.l (a1,d2.l*4),d3 ;this is better than (a1,d2.w*4)
       Eor.l  d3,d0
       Bra.s .ByteLP
     .End Not.l d0
       Rts
       

Exceptions are of couse memory indirect modes...

This means the timing on the 68050 looks like this: 

Move.l D0,d3                     -- 1 cycle
Move.l (a1),d3                   -- 1 cycle
Move.l (a1)+,d3                  -- 1 cycle
Move.l (a1,d2.l),d3              -- 1 cycle
Move.l (a1,d2.w*8),d3            -- 1 cycle
Move.l (12345678,a1,d2.w*8),d3   -- 1 cycle

What is a problem is:

Eor.l  d0,d2               -- Register write to D2 in ALU 
Move.l (a1,d2.l*4),d3      -- Register usage of D2 in EA Unit

The two ALUs (EA-Unit and main ALU) are below each other in the pipeline. You need to have 3 instructions between an instruction which updates a Data-register in the ALU and an Instruction which needs this Data-Register in the EA-Unit.

BTW this is conceptional and of how the ideal 68K CORE works.
The 68060 behaves the same this is quite well explained in the 060 mamual.

   

Matt Hey wrote:

I should be more careful. I should have put...   moveq #7,d0 ;free extb.l   eor.l d1,d0

Yes this is fuseable!

MVS is currently handled by the 68050 like a fused MOVE and EXT instruction. This means the extension is done in the ALU.
Which means MVS can NOT be fused atm with another instruction.

MOVEQ is extented earlier in the pipeline as the immediate value is already available during dedcoding - the decoder does the extending in the very frist pipeline stage already.

Cheers

      Eor.l  d0,d2               -- Register write to D2 in ALU 
      Move.l (a1,d2.l*4),d3      -- Register usage of D2 in EA Unit
      

    Jostein already does a better job of instruction scheduling than all 68k compilers I've seen 8-/.

    The 68060 change/use stall is only 2 cycles in some cases. Is this because it's superscaler or by register result forwarding? Possible on N68070 at least?
   
    "The OEP does not experience any sequence-related pipeline stalls. The most common example of this type of stall is a change/use register stall. This type of stall results from a register being modified by an instruction and a subsequent instruction generating an address using the previously modified register. The second instruction must stall in the OEP until the register is actually updated by the previous instruction. For example:
 
    muls.l #<data>,d0
    move.l (a0,d0.l*4),d1
 
    In this sequence, the second instruction is held for 2 clock cycles stalling for the first instruction to complete the update of the d0 register. If consecutive instructions load a register and then use that register as the base for an address calculation (An), a 2-clock-cycle wait may be incurred. This represents the maximum change/use penalty for a base register. The maximum change/use penalty for an index register (Xi) is 3 clock cycles (for Xi.l*2, Xi.l*8, and Xi.w). The change/use penalty for an index register if Xi.l*1 or Xi.l*4 is 2 clock cycles. Certain instructions have been optimized to ensure no change/use stall occurs on subsequent instructions. The destination register of the following instructions is available for subsequent instructions:
 
    lea
    mov.l &imm,Rn
    movq
    clr.l Dn,
    any op (An)+
    any op -(An)
 
    as a base register for address calculation with no stall, or as an index register for address calculation with no stall, if Xi.l*{1,4}. If the index register used is Xi.l*2, Xi.l*8, or Xi.w, then the previously described 3 cycle stall occurs."
 

The manual is complecated written.
What they are saying that they do not need to use the lower ALU for executing those instructions.

This is basically what I said differently before also.