Game: optimised machine code

[segher]

Let's play a game! The goal of the game is to write
optimised machine code for some function. "Optimised"
here can mean anything: fastest code, shortest code,
fewest registers used, or simply pretty code; or you can
go for the prestigious "Most Evil Code" award! Oh the
excitement!

Here is a first question: write code to compute

Code: Select all

d = a ? b : c;

and, if that is too simple,

Code: Select all

d = (a1 == a2) ? b : c;

Variants with e.g. b=0 or c=0 are of course interesting
as well.

[ers35]

Sounds like fun. Here is one to get us started:

ternary.tar

[segher]

Hi ers35,

I don't know what is inside that tarball, but I doubt it's
huge; could you please just post it as text? And write
something about it, what makes it nice code :-)

[segher]

So the code in the tarball is essentially

Code: Select all

entsp 0
bf a,nope
mov d,b
retsp 0
nope:
mov d,c
retsp 0

entsp 0 is a noop, let's pretend it isn't there at all.
On the a=0 path you get 3 insns; otherwise, also 3.
But you wrote this as a subroutine. When you don't,
you need an extra "bu" as written, giving 2 and 3 cycles
for the two paths, and 4 insns (all short insns) total.

This isn't the best possible yet (even compilers do better :-P )

[richard]

Here's my entry for the "interesting" category. The code computes a ? b : c. On entry a, b, c are expected to be in r0, r1, r2 respectively. The result of the expression is stored in r0.

Code: Select all

getr r3, XS1_RES_TYPE_CHANEND
getr r4, XS1_RES_TYPE_CHANEND
setd res[r3], r3
setd res[r4], r4
out res[r3], r1
out res[r4], r2
ldap r11, event
setv res[r3], r11
setv res[r4], r11
eef r0, res[r3]
eet r0, res[r4]
waiteu
event:
get r11, ed
in r0, res[r11]
outct res[r11], XS1_CT_END
chkct res[r11], XS1_CT_END
eeu res[r3]
eeu res[r4]
setsr 1
clrsr 1
freer res[r3]
freer res[r4]

Edit: Added explaination

► Show Spoiler

The code allocates two chanends, each connected to itself (i.e. outputs on either chanend will be received on the same chanend). b is output on the one chanend (lets call it chan_b) and c is output on the other chanend (call it chan_c). The code drains the chanends by eventing on the chanends until there is no more data to consume.

Initially the code enables events on chan_b if a is false and on chan_c is a is true, i.e. it enables events on exactly one chanend, (a ? chan_c : chan_b). After draining this first chanend, events are enabled on both chanends and the remaining chanend, i.e. (a ? chan_b : chan_c), is drained. Finally both chanends are freed. At this point r0 holds the value that was received on the last chanend to event. The last chanend to event was (a ? chan_b : chan_c) and so the value in r0 is (a ? b : c)

[segher]

Oh my. That is interesting indeed :-)
You're aiming for the misdirection award?

Is the control token dance necessary, btw? What would
break without it? Or is it just extra spice :-)

[richard]

Oh my. That is interesting indeed :-)
You're aiming for the misdirection award?

Is the control token dance necessary, btw? What would
break without it? Or is it just extra spice :-)

You get a trap if you try to free a chanend that is in the middle of a packet which is the reason for the CT_ENDs. I could have chosen not to free the chanends, but then the code could only be executed at most 16 times before running out of resources.

[segher]

Right; but you have drained the chanends already as far
as I can see? One out, one in each.

[richard]

Right; but you have drained the chanends already as far
as I can see? One out, one in each.

It doesn't matter. The first output establishes a route through the interconnect and this route is held open until a CT_END or CT_PAUSE control token is sent. Freeing a chanend without closing down the route would leave the interconnect in a bad state, so the hardware raises an ET_ILLEGAL_RESOURCE exception if you try. It doesn't matter if the destination on the same tile or on another tile - you get an exception in both cases.

[segher]

Ah yes, of course. Thank you for clarifying it Richard, I'm
a bit thick sometimes :-)

So, any takers for the short/fast award? Shall I give hints
how short/fast is (at least!) possible to achieve?