GP32 Shifting Bits

[pea]

Hi all,

How does the GP32 handle bit-shifting, and how well does GCC do at optimising for them?

Shifts are supposed to be fast, right? But in some cases while benchmarking blitting routines, we came across instances where multiplication was faster.

Questions:
1) How expensive (CPU cycles) is a shift? (e.g. a>>1)
2) Is a large shift done in one step? (e.g. is a>>2 the same expense as a>>12)
3) If (2) is 'no', are certain shifts optimised? (e.g. is GP32 cpu optimised for >>8 or >>16 for example)
4) If (3) is 'yes' Does the compiler optimise long shifts? (e.g. a>>12 becomes a>>8 followed by a>>4)

Cheers!

 

[mr.mirko]

hi pea,

you can answer all this questions yourself,
do you know the -S compiler switch ?
It can produce human readable assembler output, and now
its possible to see, how the gcc compiler optimized your source code.

Lets compile this code :

short shift_it(short a,short B) {
  return (a>>b);
}

Now lets compile it:
arm-elf-gcc test.c -S -o test.S

Now lets have a look what gcc have done:

        .file   "test.c"
        .text
        .align  2
        .global shift_it
        .type   shift_it, %function
shift_it:
        @ args = 0, pretend = 0, frame = 4
        @ frame_needed = 1, uses_anonymous_args = 0
        mov     ip, sp
        stmfd   sp!, {fp, ip, lr, pc}
        sub     fp, ip, #-4294967292
        sub     sp, sp, #4
        mov     r3, r0
        mov     r2, r1
        sub     r1, fp, #-4294967282
        strh    r3, [r1, #0]    @ movhi
        sub     r3, fp, #-4294967280
        strh    r2, [r3, #0]    @ movhi
        sub     r1, fp, #-4294967282
        ldrsh   r2, [r1, #0]
        sub     r1, fp, #-4294967280
        ldrsh   r3, [r1, #0]
        mov     r3, r2, asr r3
        mov     r3, r3, asl #16
        mov     r3, r3, asr #16
        mov     r0, r3
        ldmfd   sp, {r3, fp, sp, pc}
        .size   shift_it, .-shift_it
        .ident  "GCC: (GNU) 3.4.3"

 

[loki666]

i dont have a clue for this... if you want some, you should check s3c400 ref and arm asm ref manuals.
i think you could find it on mr.spiv home page

loki

 

[synkro]

Shifts are fast, especially for unsigned var. This is all I know about shift...

Use of shorts/signed bytes on ARM
ARM processors implementing an ARM Architecture earlier than version 4 do not have the ability to load or store halfwords (shorts) or signed bytes (signed char) directly to or from memory. These operations are implemented using load/store byte operations and shifts, and may take up to four instructions. On Architecture 4 and later, these operations only take a single instruction.

If the divisor in a division operation is a power of two, the compiler uses a shift to perform the division. Therefore you should always arrange, where possible, for scaling factors to be powers of two (for example, 128 rather than 100).

Notice that while both divisions avoid calling the division function, unsigned division takes fewer instructions than signed. In many cases the shift instruction can be combined with following instructions. Signed division needs additional instructions because it rounds towards zero, while a shift rounds towards minus infinity.

 

[Robster]

Woah, mr.mirko - that's really bad code!

With

arm-elf-gcc test.c -S -O3 -o test.S

I get

	.file	"test.c"
	.text
	.align	2
	.global	shift_it
	.type	shift_it, %function
shift_it:
	@ args = 0, pretend = 0, frame = 0
	@ frame_needed = 0, uses_anonymous_args = 0
	@ link register save eliminated.
	mov	r3, r0, asl #16
	mov	r2, r1, asl #16
	mov	r0, r3, asr #16
	mov	r1, r2, asr #16
	mov	r0, r0, asr r1
	@ lr needed for prologue
	mov	pc, lr
	.size	shift_it, .-shift_it
	.ident	"GCC: (GNU) 3.4.3"

ie. 5 instructions. Of course, it's due to removing the frame pointer and storing values in registers where possible, which is what gcc does at -O3.

Back to pea's original question, shifting is VERY fast on ARM. Nearly every instruction has a shift value on it, and this causes the result of the instruction to be shifted before being stored in its destination. The shift can either be a fixed amount (0-31 bits) or a register.

So the actual bit of the listing that does the real work is the "mov r0, r0, asr r1" instruction. That just stores r0 on itself, but it does the shift before the store. The 4 instructions above it (with 16-bit shifts) are just to make sure the 32-bit registers actually only have 16 bit values in them because they are "short" type.

When you're coding, you should probably do things in this order of preference:
1) Shift by a fixed value
2) Shift by a variable value
3) Multiply

The ARM9 has a hardware multiplier which is pretty quick. Unfortunately division is handled by a library routine and is dog slow, so avoid it if possible!

Oh, and gcc is very good at combining shifts etc so they'll be as fast as possible. Just remember -O3

 

[mr.spiv]

mov r3, r0, asl #16
mov r2, r1, asl #16
mov r0, r3, asr #16
mov r1, r2, asr #16
mov r0, r0, asr r1

Note how nicely GCC interleaved those instructions. Even if the ARM parallel shifter is fast there is a catch there. The use of parallel shifter adds 1 cycle interlock for the destination register (sorry, I don't know how to express this in correct English).

	mov	r3, r0, asl #16
	mov	r0, r3, asr #16

The above code would have 1 cycle penalty because the result calculated using parallel shifter is used in the next instruction as a source register..

 

[pea]

Thanks all.

I looked at Mr.Mirkos code and thought OMG, what sort of drugs is his compiler on. Then I read Robs post and all was saved

Is all that a>>16<<16 needed? I guess it is, since the registers could have anything in them from previous operations. I always thought to use the smallest data type possible, but I guess it is usually fastest to use unsigned long?

What is with the
sub fp, ip, #-4294967292
I guess this has to do with the fact that the parameters are signed?

EDIT:

The above code would have 1 cycle penalty because the result calculated using parallel shifter is used in the next instruction as a source register..

So the above code has the penalty, but the original code doesn't because it doesn't access the same register two instructions in a row?

 

[mr.spiv]

So the above code has the penalty, but the original code doesn't because it doesn't access the same register two instructions in a row?

​

Yep.. as I said that GCC did well interleaving instructions thus avoiding the lurking penalty cycles <_<

 

[Creature XL]

Mr Spiv, I will never doubt your knowledge, but please gimme me a link to harden you statement. As far as I know the barrel shifter doesnt take any extra time. But i will surely look this up. If you give me a link first ( or page in any ARM9 docukent I save some researche time.

salut,
creature

mov r3, r0, asl #16
mov r2, r1, asl #16
mov r0, r3, asr #16
mov r1, r2, asr #16
mov r0, r0, asr r1

Note how nicely GCC interleaved those instructions. Even if the ARM parallel shifter is fast there is a catch there. The use of parallel shifter adds 1 cycle interlock for the destination register (sorry, I don't know how to express this in correct English).

	mov	r3, r0, asl #16
	mov	r0, r3, asr #16

The above code would have 1 cycle penalty because the result calculated using parallel shifter is used in the next instruction as a source register..

​

 

[mr.spiv]

Mr Spiv, I will never doubt your knowledge, but please gimme me a link to harden you statement. As far as I know the barrel shifter doesnt take any extra time. But i will surely look this up. If you give me a link first ( or page in any ARM9 docukent I save some researche time.

Arrr.. ok I looked it up now from the manual (ARM920T (rev1) Technical Reference Manual) and lets fix one statement. The interlock takes only place IF the shift amount is controlled by a register not an immediate! :blink: So the example I gave wouldn't have 1 cycle penaly unless the shift amount were given in a register like
mov r3, r0, asl r4..
Dang.. thanks for doubting as it made me to doublecheck.. Shouldn't do anything before having the mandatory coffee dose