Fastest way to copy sign value among 68k data registers. (Branchless conditional negation of an inte-CodePudding

I'm looking for an optimized way to change the sign of a value contained in a Data Register using the sign from a value in another Data Register.

Source register will contain either 1 or -1 and destination be always positive therefore all is needed is multiplication. Here's some pseudo code of what I'd do:

MOVE.B #-1,D0
MOVE.W #173,D1
MULS.W D0,D1

After that simple math D1 would carry the sign from D0 and become either -173 or 173. Which is the desired result but MULS takes up to 70 cycles and I'm hoping to save some by finding a trick to somehow only "copy" the sign .

Last word: trick should be branchless as branching is what I'm trying to prevent by copying the sign in the first place.

Thanks in advance for any information or advice.

CodePudding user response：

You could branchlessly select between x and -x, using a bit-hack.

But you can do better: 2's complement negation can be expressed as -x == ~x 1, and both the NOT and increment can be expressed in terms of XOR and SUB with -1. But the same operations with a 0 are no-ops, leaving the value unchanged.

(This trick is often used for 2's complement absolute value, where the 0 or -1 is obtained from arithmetic right shift, x >> 31, to copy the sign bit to all bits of a register. i.e. applying your conditional-sign-flip operation to the same number that gave us the sign bit. https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs)

Of course, you need a WORD sized -1, not just BYTE, since you need to cover all bits of value you're negating (or not); as Erik points out, this means move.w #-1, d0 or ext.w if you can't promote your byte value to a word at the origin.

;; d0 = word  1 or -1
   asr.w     #1, d0
;; d0 = word  0 or -1

   eor.w     d0, d1           ;  ~d1 
   sub.w     d0, d1           ;  ~d1 - 1  (or unchanged for d0=0)

; d1 = d1 or -d1  according to d0

If you want to negate based on the sign of some other number, generate a 0 / -1 directly instead of ever creating a 1 / -1.
(i.e. an integer copysign, a bit like multiplying by signum(y) if ISO C had a signum function, but without zeroing on y=0.)

Normally you'd use x >> 15 with an arithmetic right shift, but M68K immediate shifts only allow a count from 1..8. (And are slow for large counts on CPUs without a barrel shifter). So you'd actually want get 16 copies of the sign bit by sign-extending to 32-bit and then swapping halves to put it in place:

;; manufacture a 0 / -1 word according to d0.w < 0
   ext.l   d0       ; high 16 bits = 0 / -1
   swap    d0       ; those are now the low bits

; optionally: ext.l  d0   ; to make a 32-bit 0 / -1

For a 32-bit source, you might tst.l d0,d0 / smi d0 (Set if MInus) to produce a byte-sized 0 / -1, then sign-extend that. (Although only 68020 can do that in one extb.l instruction; 68000 would need ext.w ext.l)

Or if you have a MC68020 or later CPU, you can use a sign-extending bit-field extract of just the sign bit. bfexts d0 {15:1}, d0. It's a 4-byte instruction, so same code-size as ext.l swap, but it extends to 32-bit and could work on a 32-bit source register without additional instructions. And even for 16-bit integers, it's a single instruction instead of 2, so it may be good, especially if it's executing from cache? Or not since it seems to be slower.

https://www.nxp.com/docs/en/data-sheet/MC68020UM.pdf includes instruction timings for a 68020, as "best case" (overlap with execution of previous instruction, and hot in cache), "cached case" (just cache, no overlap), and "worst case" (neither)

bfexts Dn : 5 cycles (best) / 8 (cached) / 8 (worst)
EXT Dn : 1 (best) / 4 (cached) / 4 (worst)
SWAP Rx,Ry : 1 (best) / 4 (cached) / 4 (worst)

So maybe bfexts isn't a good choice for 16-bit inputs, when ext/swap would do the job.

ASR Dn: 3 (best) / 6 (cached) / 6 (worst). Interestingly, immediate-count logical shifts are faster than this, but arithmetic shifts are the same. (68020 apparently has a barrel shifter; performance doesn't depend on the count. 68000 may not, IDK.)
EOR Dn,Dn: 0 (best) / 2 (cached) / 3 (worst)
SUB EA,Dn: 0 (best) / 2 (cached) / 3 (worst). Fetch EA time for a Dn source is 0 cycles.

Overlap (creating the best case) depends on how slow the previous instruction was, I think, especially memory access rather than core cycles; the manual I linked has some details, but they also make a big point that you can't just add up best or worst cases except as lower/upper bounds; you need to benchmark to find typical run times. IDK how data-dependencies affect this.

These are 68020 timings, since we had a choice there of bfexts vs. ext/swap. On 68000, ext/swap is almost certainly better than any alternative.