GP2X Arm Assembler Optimization

[finkel]

Hi everyone,

I need some documentation on how to optimize assembler code for pipeline execution on ARM11 processor.

I remember some general rules for some generic RISC CPU from my university days, like branch prediction, instruction interleaving, computational dependencies, etc, but I have only some vague ideas what I should be doing with ARM11.

I downloaded some technical references from the net, so at least I know that ARM11 has 8 pipeline stages, early-stage branch prediction, and so on, but some specific answers are hard to find.

For example, if I write something like this...

tst r0,#1
<other instructions>
beq 1f

... how many other (non-dependent) instructions should I put between tst and beq so that pipeline doesn't stall, and flushes minimal number of instructions in case of branch misprediction?

Similar question for something like this:

add r0,#1
<other instructions>
add r1,r0 ;@ write-read dependence of r1 on r0

Has anyone seen any online documentation dealing with this kind of stuff?

 

[___]

there are a couple of assembler pros on this board, however this forum is dedicated to the gp2x. The gp2x has an ARM920T which is ARM9 family, so I am not sure if this is what you need. Are you developing software for the gp2x, pandora, canoo or any other handhelds represented on this board? You might want to ask your questions in a dedicated forum otherwise. This community is pretty much retro enthusiasts and handheld hackers.

 

[Exophase]

I haven't personally coded for ARM11, but I can tell you what I know about the architecture and what the TRM says.

This may not be the exact same CPU, but the timing should be similar:

http://infocenter.arm.com/help/topic/com.arm.doc.ddi0333h/Cjaedced.html

First, this is what you have to know about branches. ARM11 has a pretty simple branch predictor using a small direct-mapped branch history buffer. If the branch misses in the BHB it'll go to a static predictor which predicts taken on backwards and not taken on forwards, and costs 4 cycles. If either prediction is wrong you're hit with 5-7 cycles - this is where setting the flags earlier can save you up to two cycles. So if you want to minimize the branch mispredict cost you should occupy at least two cycles in between the flag setting instruction and the branch.

The prefetch unit will buffer up to 7 instructions ahead of the rest of the pipeline. There's a "BTAC" (no idea why it can't predict indirect branches), but there's presumably still some cycle cost involved in program flow change in the prefetch unit. Since ARM11 fetches 64-bit, or two ARM instructions at a time, you're liable to almost always be ahead so the cost is hidden. Predicted immediate branches are actually folded off of the instruction stream entirely, and therefore usually take 0 cycles. Note that since the dynamic branch history is small, local only, and direct-mapped, it's not extremely effective. But when counting cycles for loops you can at least expect the looping instruction to take 0 cycles on all but the first and last iterations.

The only indirect branches that are predicted are returns of the form bx lr, if they match with the call stack (which is pushed on bl instructions). You pay 4 cycles for these, so you should avoid them.

Regarding your other latency concerns: most modern processors have extensive register forwarding and complete basic integer operations in one pipeline stage, so you don't usually have to worry about not being able to use the result of an ALU operation during the next cycle, which for ARM11 means the instruction immediately following. What you mainly need to look out for are latency after loads, latency before address generation, and latency of shifts.

Here's what I could gather:
- There's a load-use penalty of two cycles, so try to occupy two cycles after the load before you use it.
- There's an address generation interlock of one cycle (TRM calls this "early register"), so try to occupy one cycle between generating an address and loading from or storing to it.
- There's a shift generation interlock of one cycle (TRM also calls this early register), so try to occupy one cycle between generating an operand that'll be shifted and the operation that shifts it
- As usual with most ARM cores, shifts by a register amount cost an extra cycle
- The saturating instructions have an extra cycle of latency and the doubling ones have an "early register" cycle (because they use the shifter)
- A lot of the SIMD instructions have an extra cycle of latency, with usad8/usada8 having two
- The full multiplies take 2-3 issue cycles and have 4-5 result latency, the 16-bit multiplies take less.. you should carefully look at the table on 16.7 if you want to do DSP like operations
- You pay an extra cycle for negative offsets or shifts by anything outside of 2 for loads/stores. Keep this in mind for arrays of halfwords; sometimes you'll want to prefer arrays of words or if you can manage, arrays of bytes.
- Unaligned loads/stores cost an extra cycle, but are well worth it compared to having to manually align, so consider your algorithm design with this in mind (if your ARM11 even supports unaligned)
- ldrd/strd can issue as fast as ldr/str because there's a 64-bit path to L1 dcache, but there's an extra latency cycle anyway
- Likewise load multiple/store multiple can perform two register operations per cycle - you should always use these over single load/store where possible, and you should always try to keep the destination aligned. But there's a 4-cycle lock latency or something on the operands, so try to order it so the earlier registers loaded/stored are used first afterwards.
- For some reason, nop takes two cycles, so if you need a nop for some reason you might want to use an inert ALU operation instead...

 

[finkel]

there are a couple of assembler pros on this board, however this forum is dedicated to the gp2x. The gp2x has an ARM920T which is ARM9 family, so I am not sure if this is what you need. Are you developing software for the gp2x, pandora, canoo or any other handhelds represented on this board? You might want to ask your questions in a dedicated forum otherwise. This community is pretty much retro enthusiasts and handheld hackers.

I'm extending UAE4ALL for Symbian with M68020 & AGA support, and since anything more than 4 bitplanes slows the emulator down to a crawl (up to 70% slowdown with 8 bitplanes), I've been replacing some computational extensive graphics routines with pure assembler. S60 phones (at least most of them) have ARM11 CPU, and that's why I'm looking some tips for that particular architecture.

I didn't know that gp32x has ARM9. I would have probably posted this in the pandora forum otherwise, since there are quite a few references to pandora in the emu source code. If some moderator can move this thread to appropriate forum for ARM11, that would be great.

 

[finkel]

http://infocenter.arm.com/help/topic/com.arm.doc.ddi0333h/Cjaedced.html

Great link, will definitely use it if I get stuck and out of ideas.

For the rest of the post... wow, that's exactly what I need, and much more. Thanks!

you don't usually have to worry about not being able to use the result of an ALU operation during the next cycle

That's great. Leaves me with more independent instructions for interleaving.

there's a 4-cycle lock latency or something on the operands, so try to order it so the earlier registers loaded/stored are used first afterwards

That's an interesting point. I've noticed during debugging that ldm/stm go through registers sorted by hardware, so it doesn't matter in what order they are actually written in the source code. It does make sense, since hardware implementation probably shifts 1 to open some 3-state gates from/to the bus.

The only problem is that neither assembler reference, nor documentation within the link you gave state in which order registers are loaded/stored. Does hardware shift though registers from r0 to r15, or in reverse?

Judging by stack implementation, it seems to me that for increase-after it goes forward (r0->r15), and for decrease-before it goes in reverse (r15->r0). Is that correct?

 

[Exophase]

ldm/stm always loads/stores registers in the same order, from low numbered to high numbered. The two letter suffix for the operation only determines how the address is adjusted before and after the operation (for writeback).

Unfortunately there isn't actually a handheld on these boards that uses ARM11. Pandora uses Cortex-A8, which is newer and more complex to write assembly for. I imagine that some form of caching can work for Amiga emulation, ie where VRAM data is converted to packed instead of planar representation so you don't have to continually perform bitplane interleaving at runtime. That is, if uae4all isn't already doing something like this. Could you point me in the direction of the functions you're trying to optimize?

 

[finkel]

... so you don't have to continually perform bitplane interleaving at runtime. That is, if uae4all isn't already doing something like this. Could you point me in the direction of the functions you're trying to optimize?

I don't think that bitplane interleaving can be avoided, and I don't plan to rewrite the whole graphics engine. That would be too much work for the time I have available outside of my real-life job.

For starters, I've rewritten pfield_doline_n6(). It was simplest to work with, with clean, straightforward code, no branches, etc, and AmigaSYS4AGA boots in 64 colors, so it was also quick to test.

In unoptimized form, pure assembler code gave me some 10-15% overall speed increase. Unfortunately, it doesn't make much difference when you're getting +2 over already measly 14 fps, but I'm learning plenty of new stuff about ARM processors, so that kind of compensates.

I have that version optimized now, to the best of my understanding of ARM11 timings at least, but I haven't had the time to test it out yet. And since I was working under assumption that register ordering is different for db and ia suffixes, I'll have to make some reordering of instructions, but that's a piece of cake.

I'm expecting something like 20% final speed improvement with that function alone.

8-bitplane version of the function is next on the list, with one big difference from the 6-bitplane one -- I could fit almost everything in registers with 6 bitplanes. 8-bitplane version will have to access memory more often. After that one, I'm pretty much in the dark.

I am now trying to find some way to profile (and, if possible, optimize) all the functions in the emulator. IDE is Carbide C++ 2.3, it's supposed to be using GCCE 3, so I've been playing around with GCCE profiling options, but I keep getting "unresolved reference __gcov_init" errors. I will try it again after updating IDE 2.6 and GCCE to 4.

Here are some parts of the code, excluding the repeating sequences of ands and xors, which make for some 80% of the loop, and can't be optimized any further. If you have any general ideas on what else I could try, that would be welcome.

A couple of possibly dumb question first:
- Does value of link register have to be restored on function exit? I'm using it just like any other register for processing, so it gets corrupted. I could fix that with loading lr first, then "mov pc,lr" at the exit, but if it doesn't have to be restored, why bother.
- I'm assuming that 3-instruction generation of unsupported 32-bit constants (like 0x55555555) is faster than ldr-ing them directly from memory. Correct? Any other ideas on loading unsupported constants would be great as well.
- Can stack become 2-byte aligned? I'm assuming that it can't, since registers are always stored as full words, but initial allocation of stack space is still bugging me. I don't see any reason why it couldn't be initially allocated at halfword boundary, and that would require some more checks to get it to 8-byte alignment (and saving of some ldm/stm cycles in the loop).

Also, ignore (very) possible stack corruptions and wrong variable offsets, and any general bugs I've introduced after optimizing something that was actually working before optimization. Couple of debugging sessions will fix all of that.

It's a shame text formatting is not preserved when posting, so code becomes rather unreadable, but comments explain all the major points of (attempted) optimizations.

-----------------------------
PFIELD_DOLINE_N6:
;@ (
;@ r0=uae_u32 *pixels,
;@ r1=int wordcount,
;@ r2=uae_u8 *line_data[lineno],
;@ r3=uae_u32 max_words
;@ )
stmdb sp!,{r4-r8,r10-r12,lr}

;@ Stack is forced to 8-byte alignement for less load/store
;@ cycles in the loop.
msr cpsr_f,#0 ;@ Clear all flags
tst sp,#4 ;@ Not 8-byte aligned?

;@ Reserve stack space for bitplane pointers.
sub sp,sp,#24

;@ 8-byte forced alignment.
;@ Flag Q in CPSR status field is used as indicator of
;@ forced alignement, since it won't be changed during
;@ execution of the loop.
subne sp,sp,#4 ;@ Align
msrne cpsr_f,#0x08 ;@ Set flag Q

;@ PUSH &pixels & wordcount, free r0 & r1 for use
stmdb sp!,{r0,r1}

;@ NOTE: ry have been selected for bx so that data doesn't have to be
;@ reshuffled before the "stmia rn,{rx...}" instruction at the
;@ end of the loop
;@
;@ bx <=> ry:
;@ b0 <=> r0
;@ b1 <=> r2
;@ b2 <=> r4
;@ b3 <=> r6
;@ b4 <=> r1
;@ b5 <=> r3
;@ b6 <=> r5
;@ b7 <=> r7

;@ Bitplane pointers are kept on the stack. They are PEEK-ed
;@ from the stack at the end of each iteration.

;@ Get bitplane pointers in temporary registers
;@ (registers unused before the computation of bx),
;@ so that bx can be LDR-ed directly into appropriate ry
;@ registers inside the loop.
add r0,r2,r3 ;@ b2 <=> DATA_POINTER (5)
add r0,r2,r3,lsl #2
add r8,r2,r3,lsl #2 ;@ b3 <=> DATA_POINTER (4)
add r10,r2,r3 ;@ b4 <=> DATA_POINTER (3)
add r10,r2,r3,lsl #1
add r11,r2,r3,lsl #1 ;@ b5 <=> DATA_POINTER (2)
add r12,r2,r3 ;@ b6 <=> DATA_POINTER (1)
mov lr,r2 ;@ b7 <=> DATA_POINTER (0)

;@ Adjust initial pointers by -4, so that loop can use
;@ pre-indexed mode with register update.
sub r0,r0,#4
sub r8,r8,#4
sub r10,r10,#4
sub r11,r11,#4
sub r12,r12,#4
sub lr,lr,#4

LINE_N6_LOOP: ;@ do { // initial wordcount should always be > 0
;@ Get bx and advance bitmap pointers to the next word.
;@ Then store new values of bitmap pointers over their
;@ old values on the stack.

;@ b7(r7) = GETLONG ((uae_u32 *)real_bplpt[0]); real_bplpt[0] += 4;
;@ b6(r5) = GETLONG ((uae_u32 *)real_bplpt[1]); real_bplpt[1] += 4;
;@ b5(r3) = GETLONG ((uae_u32 *)real_bplpt[2]); real_bplpt[2] += 4;
;@ b4(r1) = GETLONG ((uae_u32 *)real_bplpt[3]); real_bplpt[3] += 4;
;@ b3(r6) = GETLONG ((uae_u32 *)real_bplpt[4]); real_bplpt[4] += 4;
;@ b2(r4) = GETLONG ((uae_u32 *)real_bplpt[5]); real_bplpt[5] += 4;
ldr r7,[lr,#4]!
ldr r5,[r12,#4]!
ldr r3,[r11,#4]!
ldr r1,[r10,#4]!
ldr r6,[r8,#4]!
ldr r4,[r0,#4]!

;@ Don't PUSH, just POKE new bitplane pointers over their old values
stmia sp,{r0,r8,r10-r12,lr}

;@ 1st bitmask (0x55555555)
mov r0,#0x0055 ;@ r0, the first register stored
;@ (first for which interregister lock is removed)
orr r0,r0,r0,lsl #8
orr r0,r0,r0,lsl #16

;@ MERGE (b2(r4), b3(r6), 0x55555555, 1);
eor r8,r4,r6,lsr #1 ;@ tmp = (a ^ (b >> shift))
and r8,r0,r8 ;@ tmp = mask & tmp
eor r4,r4,r8 ;@ a ^= tmp
eor r6,r6,r8,lsl #1 ;@ b ^= (tmp << shift)

...

;@ 2nd bitmask (0x33333333 = 0x55555555 >>^ 2)
mov lr,lr,ror #2

;@ MERGE_0(b0(r0), b2(r4), 0x33333333, 2);
and r0,lr,r4,lsr #2 ;@ a = tmp = mask & (b>>shift);
eor r4,r4,r0,lsl #2 ;@ b ^= (tmp << shift)

...

;@ 3rd bitmask (0x0f0f0f0f)
mov lr,#0x000f
orr lr,lr,lr,lsl #8
orr lr,lr,lr,lsl #16

;@ MERGE (b0(r0), b4(r1), 0x0f0f0f0f, 4);
eor r12,r0,r1,lsr #4 ;@ tmp = (a ^ (b >> shift))
and r12,lr,r12 ;@ tmp = mask & tmp
eor r0,r0,r12 ;@ a ^= tmp
eor r1,r1,r12,lsl #4 ;@ b ^= (tmp << shift)

...

;@ 4th bitmask (0x00ff00ff)
mov lr,#0x00ff
orr lr,lr,lr,lsl #16

;@ MERGE (b0(r0), b1(r2), 0x00ff00ff, 8);
eor r8,r0,r2,lsr #8 ;@ tmp = (a ^ (b >> shift))
and r8,lr,r8 ;@ tmp = mask & tmp
eor r0,r0,r8 ;@ a ^= tmp
eor r2,r2,r8,lsl #8 ;@ b ^= (tmp << shift)

...

;@ 5th bitmask (0x0000ffff)
mvn lr,#0
lsr lr,#16

;@ Get &pixels from the stack
ldr r12,[sp,#8*4+4]

;@ MERGE (b0(r0), b2(r4), 0x0000ffff, 16);
eor r8,r0,r1,lsr #16 ;@ tmp = (a ^ (b >> shift))
and r8,lr,r8 ;@ tmp = mask & tmp
eor r0,r0,r8 ;@ a ^= tmp
eor r4,r4,r8,lsl #16 ;@ b ^= (tmp << shift)
...

;@ DO_SWLONG(pixels, b0);
;@ DO_SWLONG(pixels + 4, b2);
rev r0,r0 ;@ Reverse byte order...
rev r4,r4

;@ Get wordcount from the stack
ldr r10,[sp,#8*4]

...

subs r10,r8,#1 ;@ wordcount--
mov r8,r12 ;@ copy of &pixels to avoid r12 lock below

;@ Store bx all at once
stmia r12,{r0-r7}

;@ pixels += 8;
addne r8,r8,#8*4
strne r10,[sp,#8*4] ;@ Store wordcount
strne r8,[sp,#8*4+4] ;@ Store &pixels

;@ Don't POP, just PEEK bitplane pointers for next iteration
ldmneia sp,{r0,r8,r10-r12,lr}

bne LINE_N6_LOOP ;@ } while (wordcount > 0)

;@ Free reserved stack space.
;@ Forced 8-byte alignement of stack is indicated by Q bit set.
;@ SP is also manually adjusted, because of possible forced alignement.
mrs r0,cpsr
lsls r0,r0,#5 ;@ Shift Q bit into C flag
addcc sp,sp,#24+9*4 ;@ Reserved space was 24 bytes
addcs sp,sp,#28+9*4 ;@ Reserved space was 28 bytes
msrcs cpsr_f,#0 ;@ Clear all flags

ldmia sp,{r4-r8,r10-r12,pc}

;@ DoLine_pData:
;@ .align 4
;@ .long DoLine_Data

;@ ---

;@ .data
;@ .align 4
;@ DoLine_Data:
;@ ;@ Bitmasks
;@ .long 0x55555555
;@ .long 0x33333333
;@ .long 0x0f0f0f0f
;@ .long 0x00ff00ff
;@ .long 0x0000ffff
-----------------------------

 

[Exophase]

I don't think that bitplane interleaving can be avoided, and I don't plan to rewrite the whole graphics engine. That would be too much work for the time I have available outside of my real-life job.

Yeah, I see what you mean. It's popular on console emulators to perform planar to packed caching for sprites and tiles, but Amiga doesn't have tiles. Nonetheless, I would expect that a common mode of operation is for the playfield to only scroll a little bit each frame and for the blitter to fill in just the new edges. So it might still be beneficial to cache the playfield scanlines in packed format. If a lot of blits do happen you could try caching the sources too, basically adding another level of cache. You'd have to track the changes the CPU makes as well, of course; one would hope the CPU doesn't touch this memory much, but really it can't nearly as high as Denise reads to draw to the screen. Like you say, this would all consist of major changes.

For starters, I've rewritten pfield_doline_n6(). It was simplest to work with, with clean, straightforward code, no branches, etc, and AmigaSYS4AGA boots in 64 colors, so it was also quick to test.

In unoptimized form, pure assembler code gave me some 10-15% overall speed increase. Unfortunately, it doesn't make much difference when you're getting +2 over already measly 14 fps, but I'm learning plenty of new stuff about ARM processors, so that kind of compensates.

Sounds good. I looked at the function and nothing immediately jumps out at me for higher level advice.

A couple of possibly dumb question first:
- Does value of link register have to be restored on function exit? I'm using it just like any other register for processing, so it gets corrupted. I could fix that with loading lr first, then "mov pc,lr" at the exit, but if it doesn't have to be restored, why bother.

You can use lr as a temporary, but since it holds the function return address you need it to exit the function. It's common for functions to save it at the prologue and then restore it to pc directly with the closing ldmia.

- I'm assuming that 3-instruction generation of unsupported 32-bit constants (like 0x55555555) is faster than ldr-ing them directly from memory. Correct? Any other ideas on loading unsupported constants would be great as well.

You can use movt and movw on ARMv6. A single ldr will be faster if it hits cache and you don't use it immediately. Since you're entering big loops you should load it into a register beforehand wherever possible, so it's probably moot.

- Can stack become 2-byte aligned? I'm assuming that it can't, since registers are always stored as full words, but initial allocation of stack space is still bugging me. I don't see any reason why it couldn't be initially allocated at halfword boundary, and that would require some more checks to get it to 8-byte alignment (and saving of some ldm/stm cycles in the loop).

The compiler won't let the stack become (32-bit) unaligned, it can only happen if you personally break it. I don't know about 64-bit alignment though, my guess would be it's doing that too. You should read about it in the EABI documentation; I'm assuming the platform you're targeting uses EABI.

 

[finkel]

Nonetheless, I would expect that a common mode of operation is for the playfield to only scroll a little bit each frame and for the blitter to fill in just the new edges. So it might still be beneficial to cache the playfield scanlines in packed format.

Yeah, I was also considering something along the lines of caching the whole display, possibly due to some experience in (more like, attempts at ) writing some games back in the days of the ol' Amiga 500. Off-screen tiling was the simplest form of scrolling, along with changing bitplane pointers in some hardware registers. I guess you're coming from similar background.

Unfortunately, there are loads of stuff going on between each frame, bits and pieces of background animation, blobs and such, so it doesn't look worth the effort. It's easier to just skip some frames, which was already implemented in the emulator before I came along.

Apart from skipping, what emulator actually does is processing each vertical line separately. If line has not been changed from the previous frame, it won't be redrawn in the current one. Very clever stuff, and more importantly -- fast. A500 games run at 25-30fps @369MHz CPU. I actually saw how it works after accidentally causing some bugs.

OK, I believe I have more than enough information to continue from here. Thank you again for all the help and truly superb advices. Much appreciated.