Most of the functions are intended to be inlined and only those more than about 10 instructions are worth putting into their own separate function - this in-lining is something the C compiler can do that isn't possible with assembly language. In every case these functions produce measurably smaller overall code by being inlined either because the function invocation itself takes more to form than the total work done and/or because it allows the callee to become a leaf and thus completely changes the way registers and stack can be assigned and used.
I spent a lot of time swearing at the compiler. Probably if i hadn't been up so late the night before I would merely have been puzzled by it. I played quite a bit with barrier() but ended up with something that is basically identical to the assembly version I came up with, but a good bit bulkier because the compiler doesn't try to use the small registers (0-7) for the whole function. It also does some redundant testing, but I think this is about as good as i'm going to get and it does pick up a couple of optimisations. I go into detail below.
I tried implementing the barrier of the the previous post whereby it tests 4 states per inner iteration but I decided to stay with the byte version due to the code-size increase. I also decided that because a workgroup barrier has to be workgroup wide, there's no need to ever allow the developer to assign memory for it and i've included the barrier memory as part of the runtime setup code (or it can be created by a linker script) which guarantees it will always be in the same location across all cores in the workgroup even if they are running different binaries. This can go somewhere fixed - either before or after the executive (aka kernel aka bios) or after the stack at the end of memory.
One of the 'interesting' loops was where the remote cores are notified of the barrier continuation. In e-lib it uses an array of pointers to implement this which leads to a trivial inner loop at the cost of extra memory reads. I decided to use the workgroup information to update the barrier directly which means it needs a bit more calculation which increases code-size but the loops are still quite small. This is the final implementation which I created by converting the assembly version literally into C after giving up trying to fight with the compiler for a better one.
volatile unsigned char *root = ez_global_core(barrier, 0, 0);
// Notify from farthest away
int r = ez_config->group_rows-1;
int ce = ez_config->group_cols-1;
do {
int c = ce;
do {
root[((r<<6) | c) << 20] = 0;
} while (--c >= 0);
} while (--r >= 0);
Looking at the listing output (oh boy, finding that option to as really brought back memories, it's -Wa,-a to gcc) one observes that the loop setup takes about half the code with the loop implementation taking up the other. The inner loop is only 6 instructions long.
// build with -O2 -msmall16 6 0000 0305 mov r0,#40 7 0002 C420 ldr r1,[r0,#1] 8 0004 4C010040 ldr r16,[r0,#2] 9 0008 CC210040 ldr r17,[r0,#3] 10 000c 0B800220 mov ip,_barrier 11 0010 9606 lsl r0,r1,#20 12 0012 7F900A24 orr ip,ip,r0 13 0016 9B03FF48 add r16,r16,#-1 14 001a 9B27FF48 add r17,r17,#-1 15 001e 0360 mov r3,#0 16 .L5: 17 0020 DF400608 lsl r2,r16,#6 18 0024 EF040208 mov r0,r17 19 .L3: 20 0028 7A21 orr r1,r0,r2 21 002a 9626 lsl r1,r1,#20 22 002c 9303 add r0,r0,#-1 23 002e 99700004 strb r3,[ip,r1] 24 0032 3320 sub r1,r0,#0 25 0034 70FA bgte .L3 26 0036 9B03FF48 add r16,r16,#-1 27 003a 3B000008 sub r0,r16,#0 28 003e 70F1 bgte .L5
This is almost identical to the assembly I came up with beforehand as the emboldened sections which indicate the non-redundant instructions show.
(untested code follows)
6 0000 0360 mov r3,#0 ; for fragment 7 0002 0325 mov r1,#ez_config 8 0004 C444 ldr r2,[r1,#ezc_group_id] 9 0006 E484 ldrd r4,[r1,#ezc_group_rows/2] 10 0008 0B000200 mov r0,%low(_barrier) 11 000c 964A lsl r2,r2,#20 ; groupid << 20 12 000e 7A48 orr r2,r2,r0 ; root = get_global_address(barrier, 0, 0) 13 0010 B390 sub r4,r4,#1 ; r = rows - 1 14 1: 15 0012 3B360000 sub r1,r5,#1 ; c = cols - 1 16 0016 D6D0 lsl r6,r4,#6 ; rshift = r << 6 17 2: 18 0018 FAF8 orr r7,r6,r1 ; o = (r << 6) | c 19 001a 96FE lsl r7,r7,#20 ; o <<= 20 20 001c 916B strb r3,[r2,r7] ; root[o] = 0 21 001e B324 sub r1,r1,#1 ; while (--c >= 0) 22 0020 70FC bgte 2b 23 0022 B390 sub r4,r4,#1 ; while (--r >= 0) 24 0024 70F7 bgte 1b
The register usage is because I extracted it from a bigger fragment - I may have broken it too but since it's only 4 accountable instructions different to the C compiler it should be ok apart from typos.
Being able to use the lower 8 registers really makes a big difference to code size as you'd imagine. Despite only being 4 instructions shorter this is 38 bytes compared to 64. Due to the ABI it does come at the cost of having to save/restore 4 registers which is 16 bytes of instructions and some time but it doesn't take much code before that is made up.
The other point of note is the direct use of the condition codes after the loop index adjustment. This saves one instruction per loop here plus the scratch register which would otherwise be required (line 24 and 27 of the first listing). This is really something I would expect the compiler to pick up. Perhaps less expected is the double-word load which saves one instruction, and the other instruction is saved by changing the redundant register move on line 18 in listing one into a substraction on line 15 in listing two which means the one on line 14 in listing one can be discarded.
The full barrier implementation needs to use a volatile read of a byte array and I found the compiler (and oddly, the arm compiler as well although only in the signed char case) does some weird and unnecessary data size extension when you read from a volatile char array which adds two pointless instructions for every byte load.
So with that the total implementation in C hits 144 bytes vs 88 for the assembly - which is fair enough I guess but there is room for improvement and only small things can make quite a difference when you're dealing with such small functions.
The e_barrier() code in e-lib compiled with the same options (-O2 -msmall16) hits 236, but much of that is because of the need to perform some multiplies. It's actually much worse than that because e_barrier_init() which is also a necessary part of the implementation compiles to 346 bytes ... :-/. I'm pretty sure the e_barrier_init()/e_barrier() pair has a race condition as well which can't be solved without another ... barrier.
If e_group_config is modified to include group_size and core_index values this drops them down to 132 and 224 bytes respectively which in terms of on-core code is still 2.5x the C one above (and 4.0x the asm). Strangely enough the notify loop uses implicit condition code tests on it's loop counter! But it added a separate counter register to implement this so that is probably why it isn't available on 'normal' calculations. Actually an externally initialised version of this implementation could be made very small; but then the data-size will dominate.
If only that hardware barrier worked properly in this case.
I did some further experiments while writing this and although it's kind of academic because of it needing 5x the runtime memory I fiddled with an implementation that uses an array of pointers assuming they have been initialised by the runtime / loader. I can get it down to 70 bytes for the barrier() call.
No comments:
Post a Comment