68000 code optimisations

[Toni Wilen]

Originally Posted by Thorham

What I want to know is why TAS shouldn't be used for memory. Doesn't seem like it could hurt. I've actually tried (chipmem) it and it didn't seem to cause any weird behavior.

http://eab.abime.net/showpost.php?p=745876&postcount=3

TAS seems to work fine if there is no competing DMA active.

TAS Dx is perfectly safe, it does not do any memory accesses.

[mark_k]

Originally Posted by Thorham

What I want to know is why TAS shouldn't be used for memory. Doesn't seem like it could hurt. I've actually tried (chipmem) it and it didn't seem to cause any weird behavior.

As I understand it, on 68000/010 (only) the special read-modify-write cycle used when TAS accesses memory can interfere with the custom chips' access to chip memory. Also some Zorro II fast RAM cards might not support the read-modify-write cycle.

You could try running a test program, something like this:

Loop:
   tas   d0
   tas   d0
   tas   d0
   tas   d0
   bra.b   Loop

On a 68000-based Amiga, set your Workbench screen to 16 colours high-res then run the test program. Maybe also experiment with reading/writing floppy a disk while the test program is running, and/or run a program which uses the blitter.

There's an old newsgroup posting which mentions some of the possible issues with TAS, see this.

[Ricardo]

Cool topic

[Photon]

Many caveats in HRM can be taken with a grain of salt, and the TAS warning like the other ones can be ignored - if you know where it's appropriate.

TAS, even to memory, is fine. But it has to be executed when no DMA (or memory refresh slots) want to fight its bus ownership. What happens is that the CPU does whatever it wants with the bus, and these other two users of the bus can't set its DMA or memory refresh address or data.

This can of course cause havoc including losing data in memory, and DMA writing to the wrong address including executing programs. You could avoid the former if you do your own memory refresh of desired ranges in memory you care about, such as where the running code and data and the hardware vectors are, and avoid the latter by disabling the copper and never executing TAS instructions while blitting or bitplane/sprite/audio DMA is active, but I think this limits its usefulness somewhat...

TAS Dn can of course be used anytime, anywhere, since it doesn't hog the bus.

[Galahad/FLT]

I simply never use it, because i'll know damn well, i'll forget about not using it to access memory and then be scratching my head wondering why the fuck my program doesn't work!!!

[mark_k]

Originally Posted by mark_k

You could try running a test program, something like this:

Loop:
   tas   d0
   tas   d0
   tas   d0
   tas   d0
   bra.b   Loop

Doh. Of course that will always work fine since TAS is on a data register! It should be something like this instead:

   suba.l a0,a0       ;Address 0 is in chip memory
Loop:
   tas    (a0)
   tas    (a0)
   tas    (a0)
   tas    (a0)
   bra.b  Loop

Or if you have a 68010 CPU you can make use of its loop mode:

   suba.l a0,a0       ;Address 0 is in chip memory
Loop1:
   moveq  #-1,d0
Loop2:
   tas    (a0)
   dbf    d0,Loop2
   bra.b  Loop1

(Of course writing to location 0, while mostly harmless is not really legal. But it should be fine for the purposes of this test on 68000/010. If you want to be more legal you could allocate some chip memory or have a chip data hunk and point A0 to that.)

[Photon]

As stated, if you don't perform the tests in a DMA- and memory refresh-controlled environment, memory rows will be lost until you are running random words instead of code.

If you don't take care of those two things AND turn the system off, you will get trashed memory, rogue coppers, and a crash.

If system is off and it's running in real fastram, the effects should be limited to rogue coppers, if disk DMA is off and blits have finished.

[Samurai_Crow]

There are softcores on the way for the NatAmi and possibly the FPGAArcade Replay board that will not support the instructions that are not legal on the Amiga. The encoding for TAS, CAS and such was kind of added on as an afterthought in the instruction set but the possibilities of adding more useful single-core opcodes to the Apollo N68070 are likely to yield better performance in the long run.

[Thorham]

Thanks guys for explaining the TAS problem Could be useful when used with a data register. Shame that CAS/CAS2 always work on memory.

Originally Posted by Samurai_Crow

There are softcores on the way for the NatAmi and possibly the FPGAArcade Replay board that will not support the instructions that are not legal on the Amiga. The encoding for TAS, CAS and such was kind of added on as an afterthought in the instruction set but the possibilities of adding more useful single-core opcodes to the Apollo N68070 are likely to yield better performance in the long run.

That's not a very smart move, seeing how those instructions can actually work, especially TAS.

[pmc]

I agree with Thorham on that.

I thought the Natami was supposed to be compatible with classic Amigas?

Not supporting all the opcodes that the native Amiga CPUs use surely automatically makes it less than 100% compatible.

[Samurai_Crow]

The goal for the FPGAArcade Replay is compatibility at all costs.

The goal for the NatAmi is a bit different. We want performance at all costs with just enough compatibility to run WHDLoad and all of its slaves. If you look at our homepage you'll see that we want to leave out legacy drawbacks in order to make way for more performance.

Besides the legal threshold for the word "compatible" is 90% of software running on it. I think we can meet that threshold easily.

[matthey]

The Natami's Apollo fpga CPU currently supports TAS in hardware without the read-modify-write but it's recommended NOT to use it in case it could be used later for it's intended purpose. The following instructions will likely be trapped:

MOVEP, MOVES, PACK, UNPK

They should not be used as they will be slow and the encoding space could be reused at a later time. It would be wise to replace them in any patches. MOVEP is trapped on the 68060 as well. Instructions that will likely not be supported and may have their encoding space reused are:

CAS, CAS2, CMP2, CHK2, CALLM, RTM and BKPT

CAS and CAS2 are not reliable on the Amiga. CMP2 and CHK2 are trapped on the 68060. CALLM/RTM are only on the 68020 and not really useful. If anyone sees a glaring 68k compatibility problem with this then speak up. The Apollo core should be very forgiving of self-modifying code which will probably be better for 68k compatibility than supporting some rarely used instructions.

[Photon]

PRE-EDIT: gosh, why do I reply to the message in the inbox. Kept the below text cos I think it voices similar previously expressed opinions in more detail.

Originally Posted by Samurai_Crow

There are softcores on the way for the NatAmi and possibly the FPGAArcade Replay board that will not support the instructions that are not legal on the Amiga.

That's just silly!

In the same list of "illegal" instructions are: clr.w certain custom chip registers, yet you wouldn't remove the clr instruction, would you? Betcha a movep to BLTSIZ wouldn't be very healthy either!

Backwards compatibility is easy, forwards compatibility is harder. Now possibly made impossible by not supporting an instruction that has been in every 680x0 CPU! Please tell me they are reconsidering.

Imagine that, a single sentence in a book becoming law. I think this is how myths become religions.

Also: betcha I can make CAS work fine on accelerated Amigas. Trapping for patches is ...*oof* fine I guess... *grumble* *suspicious look*

[Thorham]

Originally Posted by matthey

MOVEP, MOVES, PACK, UNPK

They should not be used as they will be slow and the encoding space could be reused at a later time. It would be wise to replace them in any patches.

That's a nice way to reduce 680x0 compatibility, great design choice

Originally Posted by matthey

MOVEP is trapped on the 68060 as well. Instructions that will likely not be supported and may have their encoding space reused are:

CAS, CAS2, CMP2, CHK2, CALLM, RTM and BKPT

CAS and CAS2 are not reliable on the Amiga. CMP2 and CHK2 are trapped on the 68060. CALLM/RTM are only on the 68020 and not really useful.

Who cares about 'trapped on 68060'? Is the 68060 now the 680x0 law?

Originally Posted by matthey

If anyone sees a glaring 68k compatibility problem with this then speak up. The Apollo core should be very forgiving of self-modifying code which will probably be better for 68k compatibility than supporting some rarely used instructions.

Rarely used or not, 680x0 is 680x0, and by going down this road, the Natami 680x0 core won't be very 680x0, now will it?

Perhaps FPGAArcade is a better choice for classic users, seeing how Natami removes what ever it wants so that it can reuse the encoding space. All those extra instructions aren't any good anyway. Software that would work perfectly fine on 680x0, won't work now. Natami is looking less attractive by the second.

[matthey]

Originally Posted by Photon

Backwards compatibility is easy, forwards compatibility is harder. Now possibly made impossible by not supporting an instruction that has been in every 680x0 CPU! Please tell me they are reconsidering.

Some 68k instructions are baggage. They are poorly encoded (slows decoder for all instructions) or poorly implemented and don't work well in a superscaler environment. Not many programmers used them because they were too slow. The 68060 designers could see that it wasn't practical to support them in hardware. They trapped the less common ones for backward compatibility but this made them even slower. Reusing the encoding space is not the preferred choice but there isn't a lot of encoding space left without using A-line or F-line for integer instructions but doing that has it's down sides also. We are paying attention to which instructions were used on the Amiga and that's why MOVEP, TAS and most of the BCD instructions will most surely be supported. We are open to reconsidering removals if you can show us examples where CAS, CAS2, CMP2 and CHK2 are used in a legitimate way on the Amiga while being faster than using other instructions and being common enough that patching the executable to remove them would be a major problem. Note that these removals do not affect 68000 compatibility which, interestingly enough for this thread, should be excellent.

Originally Posted by Photon

Also: betcha I can make CAS work fine on accelerated Amigas. Trapping for patches is ...*oof* fine I guess... *grumble* *suspicious look*

I bet you can too but I bet you can't find an advantage to using it on the Amiga because of it's slow timing (on the 68040 and 68060 at least). How many instructions can the 68060 execute in:

CAS 19 cycles
TAS 17 cycles (in memory)

You can do the same faster with replacement code. If it was faster in any case on the Amiga then someone would have used it but it's not and that's why it's gone unused. CAS is useless without a working read-modify-write cycle that's slow on a modern processor.

[matthey]

Originally Posted by matthey

MOVEP, MOVES, PACK, UNPK

They should not be used as they will be slow and the encoding space could be reused at a later time. It would be wise to replace them in any patches.

Originally Posted by Thorham

That's a nice way to reduce 680x0 compatibility, great design choice

The trapping emulation code will be in fast flash memory and any use of these instructions shouldn't need to be fast. I doubt you would notice that they are trapped at all.

Originally Posted by Thorham

Who cares about 'trapped on 68060'? Is the 68060 now the 680x0 law?

The 68060 made mostly good choices in the direction it chose in order to be fast. Unused instructions sitting around in hardware are slowing down the decoder and taking up space for faster and more useful instructions. Would you rather have a 68040 or 68060? The 68040 supported almost everything 68k integer. If you are happy with that or a 68020/68030 then that's fine. Some of us would rather have more speed instead.

Originally Posted by Thorham

Rarely used or not, 680x0 is 680x0, and by going down this road, the Natami 680x0 core won't be very 680x0, now will it?

Perhaps FPGAArcade is a better choice for classic users, seeing how Natami removes what ever it wants so that it can reuse the encoding space. All those extra instructions aren't any good anyway. Software that would work perfectly fine on 680x0, won't work now. Natami is looking less attractive by the second.

The name was changed to Apollo. Maybe we aren't 68k anymore. The ColdFire wasn't 68k and less than 50% of 68k software runs unmodified on it's most recent version. I think the Apollo will be able to run >99.9% of 68k code. I guess it's up to the user to decide though. Some Purists will choose an Amiga 1000 with 68000 as even the 68020/68030 are blasphemy. Motorola changed MOVEM behavior and made MOVE SR,<ea> supervisor mode causing 68000 code to crash on the 68020+. Yep, everything after the 68000 isn't really 68k compatible as the true path does not allow for any incompatibility. I should feel bad for enjoying my 68060 so much I guess .

[pmc]

I won't say anything about what I do or don't think are the rights and wrongs of Natami compatibility or about who I do or don't agree with in the preceding discussion.

The reason I won't is that I can see that my (our) nice cosy 68000 optimisations thread, that up until now has been very useful, will very quickly descend into an off topic Natami compatibility thread.

As it happens I think a thread about Natami CPU compatibility would be very interesting, but please, really do go and make it another thread.

[TheDarkCoder]

Originally Posted by Photon

The instructions take the cycles they take, and there's no instruction reorder optimizations on 68000 apart from the prefetch after the write to BLTSIZ and the hard-to-know odd-cycle alignment wait of instructions that take 6/10/14 etc cycles.

may you explain to me these two optimizations?

[Thorham]

Originally Posted by pmc

The reason I won't is that I can see that my (our) nice cosy 68000 optimisations thread, that up until now has been very useful, will very quickly descend into an off topic Natami compatibility thread.

You're absolutely right

Here's one. It clamps d0 to 255 at an overflow. Use after a vlaue has been added to d0:

	subx.b	d1,d1
	or.b	d1,d0

[Photon]

Originally Posted by pmc

(this) will very quickly descend into an off topic Natami compatibility thread.

As it happens I think a thread about Natami CPU compatibility would be very interesting, but please, really do go and make it another thread.

I agree. It would be a friendly gesture and perhaps prepare a few programmers to adjust.

CAS was mentioned. The thing is, compatibility has never been about performance but in the case of Amiga, not have to rely on Amiga programmers who have perhaps moved on (in any sense) to update software to not have it become obsolete. It might have already been used in 4K ztravaganza ztrordinairez, or I might do one just to spite you! (Well, not really feeling like it but there's the size aspect of optimization as well.)

There's always been a limit to how many % of software a given ever so compatible Amiga or Amiga successor platform can support, but it's been due to other things than yanking out instructions and more about instruction behavior, caching, speed, and OS code. A compiler can make the programmer forget about the instruction set altogether, but this forum IS basically about the instruction set. And the chipsets.

I'm not poking my finger in a potential success story like Natami and trapping and patching is one way (grumble) for compatibility, but as pointed out for real Amiga users to not use instructions demonstrably working on an Amiga is... not really relevant to optimization which is this topic.

I think specifics of Natami supports points to its nearing conclusion, which is exciting! - and I'll help move any posts you wish regarding it or other nextgen Amiga clones to the NextGen forum.

[Photon]

Originally Posted by TheDarkCoder

may you explain to me these two optimizations?

Well, the prefetch feature of the 68000 is no secret. My theory was, this will cause an internal stage and another internal stage XOR a word memory access (total 2x 4 cycles) to be executed before a blit starts. The theory hasn't been tested for much more than DIVSing perspective while drawing lines 23 years ago, basically cos I couldn't find anything else that was more useful that wasn't a normal sub-12 cycle instruction. Sometimes the lines would be shorter than the DIVS cycle time of course, but it was rare. The point was that it was started immediately thus calculated internally in parallel finishing faster.

The other one is aligning table lookups (usually 14c) or a taken branch (10c) and similar with the alternating 4-cycle CMA/DMA memory access. In the vblank period, when no DMA is active it's "as written", just sum up the cycles. But while actually displaying something some of them would just be out of luck and have their CMA execute the NEXT 4-cycle slot the bitplane DMA wasn't hogging access.

Normally this is too much work really (really!) since you can't really go "oh, I'll halve the number of colors on screen and I'll be able to fit one or two CMA's between bitplane accesses" cos you'd have ruined the original idea (by making it look shit) and also would have gained much more already, by removing a bitplane's DMA, both for blitter and CPU.

So I haven't tried this unless I got some routine right by accident so I expect someone is going to debunk it instantly (and thunderously!)

But it's basically the last straw to grip when a frameful of effect is a sequence of perfectly and godlikely optimized instructions (according to yourself of course). Considering you'd likely have to sync with raster at the start of something, you'd probably lose more by that sync than you gained! But there might be a situation. Not one that wouldn't be completely 'surpassed' by precalc or infinite bobs or whatever, of course. Hah.

[meynaf]

A few coding tricks, not specific to 68000 but still ok there i think :

; sgn - returns d1=0 if d0=0, d1=1 if d0>0, or d1=-1 if d0<0
 add.l d0,d0
 subx.l d1,d1
 negx.l d0
 addx.l d1,d1

; quick-test to check if one byte of d0 is 00
 move.l d0,d1
 not.l d0
 sub.l #$01010101,d1
 and.l #$80808080,d0
 and.l d0,d1
 bne null_byte_found

; check if a=b, (d0=a, d1=b, range 0000-7FFF), but true in all cases if b=$ffff
 eor.w d1,d0
 bgt not_equal

; instead of :
 scs d0
 ext.w d0  ; or extb.l d0
 ext.l d0  ;
; write :
 subx.l d0,d0

; to see if a value is between $FFFF8000 and $7FFF, better put it in An reg :
 cmpa.w a0,a0  ; cmp with a0.w extended to .l, and a0.l

[Photon]

Trying to optimize often leads to a few lines of strange new code that does it faster or shorter but looks irrelevant to the task Even though this looks more like good code for implementing variable typing in a higher level language, I liked it.

[pmc]

Originally Posted by Photon

Trying to optimize often leads to a few lines of strange new code that does it faster or shorter but looks irrelevant to the task

So true. Leading to the weird experience of looking at some of your very own code and thinking: huh? what the hell was I doing that for?

Followed by a few minutes of groping through hazy memories and realising: oh, yeah, that's why.

It's another reason why I personally find it difficult to nigh on impossible to figure out other people's demo code. They did so many weird little things and optimisations that only they understood the reason for that I've got no chance.

Much easier to code your own effects from scratch than figure out how some other coder did it their way.

[phx]

That's why most programming languages allow comments.

[meynaf]

Originally Posted by phx

That's why most programming languages allow comments.

I second that. Whenever i use a "trick" in asm, i add comments for each line.

But, of course, when you re-source a program, comments are gone

[Lonewolf10]

Some great tips here

Anyone else think this thread is worthy of being made "sticky"?


Regards,
Lonewolf10

[TheDarkCoder]

I second that. But I would suggest to move the thread in the ASM section

[meynaf]

Perhaps there is a little bit too much OT here to do that, huh ?

[pmc]

Instead of this:

                    cmpi.l              #num,Dn

this:

                    moveq.l             #num,Dn
                    cmp.l               Dn,Dn

where (to suit the moveq.l) num is in the range -128 to +127

[Photon]

Yes, and one I use a lot is masking or subtracting stuff "to another register". When you do gfx stuff you often go

moveq #15,d1
and.w d0,d1

which retains the value in d0 should you need to mirror it or something.

Thread moved to asm forum and made sticky 8)

[StingRay]

Originally Posted by pmc

Instead of this:

                    cmpi.l              #num,Dn

this:

                    moveq.l             #num,Dn
                    cmp.l               Dn,Dn

where (to suit the moveq.l) num is in the range -127 to +127

moveq range is -128 to +127.

[pmc]

Doh! Stung again!

Original post now edited.

[TheDarkCoder]

@pmc: you probably meant to keep the small immediate value in a register different to the one against which you do the cmp:

moveq.l #num,Dx
cmp.l Dx,Dn

[pmc]

Yes. That was supposed to be implied but, as you say, it reads rather ambiguously. It's much more clear written your way.

[pmc]

Here's on optimisation I worked out ages ago using shifting and adding instead of multiplying.

Maybe obvious or well known to others, or maybe not but well... might be useful to someone

As an example, the eight binary digits in a byte represent the decimal numbers:

128 64 32 16 8 4 2 1

So, multiplying a number by shifting is pretty easy: shift left once to multiply a number by 2 for example.

                    lsl.w               #1,d0

or shift left by three to multiply a number by 8 etc. etc.

But what about multiplying to other numbers?

I've found that it's possible to do a couple of shifts and an add to multiply to other numbers.

For example, if I wanted to multiply a number by 40 - in the binary digits above, there's no 40 but there are a 32 and an 8.

And, as luck would have it, 32 + 8 = 40

So, if I shift a number left by five (multiply by 32) and take the same number and shift it left by three (multiply by 8) and then add the two results

                    move.w              d0,d1
                    lsl.w               #3,d0
                    lsl.w               #5,d1
                    add.w               d1,d0

I get the original number in d0 multiplied by 40 but without having to use a comparatively slow mulu.w

It can also work with more than two additions - if I wanted to multiply a number by 56:

                    move.w              d0,d1
                    move.w              d0,d2
                    lsl.w               #3,d0
                    lsl.w               #4,d1
                    lsl.w               #5,d2
                    add.w               d2,d1
                    add.w               d1,d0

This works for other numbers too - try it and see what works. Obviously there'll be a cut off somewhere where all the shifting and adding will mount up and it might be quicker or no different to use a mulu.w instead.

Also, you do have to watch out for shifting digits "off the end" of the size the registers in use can hold.

[StingRay]

On 68000, instead of doing shifts/adds, you could also use a multiplication table. Disadvantage is that you might need a spare address register (depending on where in memory your table is) and that the table needs some memory of course. Advantage is that it is faster than lots of shifts+adds.

So f.e. if you want to multiply a number in d0 by 56 you'd do this:

lea multab(pc),a0
add.w d0,d0
move.w (a0,d0.w),d0
...

[pmc]

Oh yes, definitely - pre multiplying your values and just dragging them out of a table by index is better than doing calculations in the code but you know, it's nice to have options

[StingRay]

Of course it is. Sometimes you don't even have the memory required for the table f.e. I just mentioned it for the sake of completeness.

[Codetapper]

If you want to multiply by "nice" numbers like 40 on a 68000 and not use a multiplication table, you should do the following to avoid a second slow lsl operation rather than pmc's method:

        lsl.w   #3,d0   ;d0 = Number * 8
        move.w  d0,d1   ;d1 = Number * 8
        add.w   d1,d1   ;d1 = Number * 16
        add.w   d1,d1   ;d1 = Number * 32
        add.w   d1,d0   ;d0 = Number * 40

If shifting left by 2 or less, it's quicker to do 2 add's than a shift (on 68000 only!) If you wanted to multiply by 48 for example, it's actually quicker than to multiply by 40:

        lsl.w   #4,d0   ;d0 = Number * 16
        move.w  d0,d1   ;d1 = Number * 16
        add.w   d1,d1   ;d1 = Number * 32
        add.w   d1,d0   ;d0 = Number * 48

To multiply by 56:

        lsl.w   #3,d0   ;d0 = Number * 8
        move.w  d0,d1   ;d1 = Number * 8
        add.w   d1,d1   ;d1 = Number * 16
        move.w  d1,d2   ;d2 = Number * 16
        add.w   d2,d2   ;d2 = Number * 32
        add.w   d2,d1   ;d1 = Number * 48
        add.w   d1,d0   ;d0 = Number * 56

The other alternative is to use the fact that 56 is 64 - 8:

        lsl.w   #3,d0   ;d0 = Number * 8
        move.w  d0,d1   ;d1 = Number * 8
        lsl.w   #3,d0   ;d0 = Number * 64
        sub.w   d1,d0   ;d0 = Number * 56

Shifts of 3 or more are faster with a shift operation than 3 add's.