ARM Cortex M0+: How to use "Branch if Carry" instructions in C-code?

user_6215916 0
Viewed 448

I have some C code that processes data bit-by-bit. Simplified example:

// input data, assume this is initialized
uint32_t data[len];

for (uint32_t idx=0; idx<len; idx++)
{
    uint32_t tmp = data[idx];
    
    // iterate over all bits
    for (uint8_t pos=0; pos<32; pos++)
    {
        if (tmp & 0b1)
        {
            // some code
        }
    
        tmp = tmp >> 1;
    }
}

In my application len is relatively large, so I'd like to optimize the inner loop as highly as possible. The // some code section is small and already heavily optimized.

I'm using an ARM Cortex M0+ MCU which has an instruction to branch if the carry bit is set (see cortex-m0+ manual, page 45). Conviniently shifting bits places the LSB (or MSB) into the carry flag, so in theory it can branch without the comparison like this:

// input data, assume this is initialized
uint32_t data[len];

for (uint32_t idx=0; idx<len; idx++)
{
    uint32_t tmp = data[idx];

    // iterate over all bits
    for (uint8_t pos=0; pos<32; pos++)
    {
        tmp = tmp >> 1;

        if ( CARRY_SET )
        {
            // some code
        }
    }
}

What is the best way to archive this with C code and/or inline Assembler? Ideally I'd like to keep the // come code in C for simplicity and better readability.

Edit 1: I've tested this code on GCC 5.4 GCC 6.3 with -O1, -O2 and -03. For every setting it generates the following assembly code (note the dedicated tst instruction I try to get rig of):

        if (data & 0b1)             
00000218   movs r3, #1       
0000021A   tst  r3, r6       
0000021C   beq  #4

Edit 2: minimal reproducable example. I'm writing the code in Atmel Studio 7 (because it's intended for a MCU) and inspect the values int the build-in debugger. If you use a different enviroment, you may need to add som IO code:

int main(void)
{
    uint32_t tmp = 0x12345678;
    volatile uint8_t bits = 0;  // volatile needed in this example to prevent compiler from optimizing away all code.

    // iterate over all bits
    for (uint8_t pos=0; pos<32; pos++)
    {
        if (tmp & 1)
        {
            bits++;    // the real code isn't popcount.  Some compilers may transform this example loop into a different popcount algorithm if bits wasn't volatile.
        }
        tmp = tmp >> 1;
    }

    // read bits here with debugger
    while(1);
}
compiler-optimization arm micro-optimization assembly c
2 Answers

I did not find an "easy" solution, so I had to write my short algorithm in assembler. This is what the demo code looks like:

// assume these values as initialized
uint32_t data[len];     // input data bit stream
uint32_t out;           // algorithm input + output
uint32_t in;            // algorithm input (value never written in asm)

for (uint32_t idx=0; idx<len; idx++)
{
    uint32_t tmp = data[idx];
    
    // iterate over all bits
    for (uint8_t pos=0; pos<32; pos++)
    {
        // use optimized code only on supported devices
        #if defined(__CORTEX_M) && (__CORTEX_M <= 4)
        asm volatile  // doesn't need to be volatile if you use the result
        (
            "LSR    %[tmp], %[tmp], #1" "\n\t"  // shift data by one. LSB is now in carry
            "BCC    END_%="             "\n\t"  // branch if carry clear (LSB was not set)
            
            /* your code here */        "\n\t"
        
            "END_%=:"                   "\n\t"  // label only, doesn't generate any instructions
        
            : [tmp]"+l"(tmp), [out]"+l"(out)    // out; l = register 0..7 = general purpose registers
            : [in]"l"(in)                       // in;
            : "cc"                              // clobbers: "cc" = CPU status flags have changed
                               // Add any other registers you use as temporaries, or use dummy output operands to let the compiler pick registers.
        );
        #else
        if (tmp & 0b1)
        {
            // some code
        }
        tmp = tmp >> 1;
        #endif
    }
}

For your application, add your assembly code at the marked location, and feed in data from the C function with the registers. Keep in mind that in Thumb mode, many instructions can only use 8 of the 16 general purpose registers, so you can't pass more values than that.

Inline assembly is very easy to get wrong in subtle ways that appear to work but can break after inlining into different surrounding code. (For example, forgetting to declare a clobber.) https://gcc.gnu.org/wiki/DontUseInlineAsm unless you need to (including for performance), but if so make sure you check the docs (https://stackoverflow.com/tags/inline-assembly/info).

Note that technically the correct shift instruction is LSRS (with an s suffix to set flags). However on GCC 6.3 + GAS writing lsrs in the asm code will cause an error assembling in thumb mode, but if you write lsr it assembles successfully into an lsrs instruction. (In ARM mode, which Cortex-M doesn't support, lsr and lsrs both assemble to separate instructions as expected.)

Although I can not share my application code, I can tell you how much speedup this change had:

-O1 -O2 -O3
original 812us 780us 780us
w/ asm 748us 686us 716us
w/ asm + some loop unrolling 732us 606us 648us

So with my the ASM code and -O2 instead of -O1 I get a speedup of 15% and with additional loop unrolling I got a speedup of 25%.

Placing the function in RAM with __attribute__ ((section(".ramfunc"))) yields another 1% improvement. (Make sure to test this on your device, some MCUs have awful flash cache miss penalties.)

See old_timer's answer below for more general purpose optimizations.

user_62159160

If you have specific code you want then...you just write it. Start with the compiled code and hand optimize as desired. The compiler cannot read your mind.

gcc 5.x.x is where gnu peaked as far as code output, it has gone down hill since. but that does not mean that version is always better than the newer versions. godbolt or just having various ones installed on your computer can help if you are trying to get the compiler to do the work for you.

unsigned int fun ( unsigned int tmp )
{
    unsigned int bits;
    bits=0;
    for (unsigned char pos=0; pos<32; pos++)
    {
        if (tmp & 1)
        {
            bits++;
        }
        tmp = tmp >> 1;
    }
    return(bits);
}

with bits as a 32 bit

Disassembly of section .text:

00000000 <fun>:
   0:   0002        movs    r2, r0
   2:   b510        push    {r4, lr}
   4:   2320        movs    r3, #32
   6:   2000        movs    r0, #0
   8:   2401        movs    r4, #1
   a:   0021        movs    r1, r4
   c:   3b01        subs    r3, #1
   e:   4011        ands    r1, r2
  10:   b2db        uxtb    r3, r3
  12:   1840        adds    r0, r0, r1
  14:   0852        lsrs    r2, r2, #1
  16:   2b00        cmp r3, #0
  18:   d1f7        bne.n   a <fun+0xa>
  1a:   bd10        pop {r4, pc}

r4 is set one time outside the loop

with bits as an 8 bit value

Disassembly of section .text:

00000000 <fun>:
   0:   0002        movs    r2, r0
   2:   2320        movs    r3, #32
   4:   2000        movs    r0, #0
   6:   2101        movs    r1, #1
   8:   4211        tst r1, r2
   a:   d001        beq.n   10 <fun+0x10>
   c:   3001        adds    r0, #1
   e:   b2c0        uxtb    r0, r0
  10:   3b01        subs    r3, #1
  12:   b2db        uxtb    r3, r3
  14:   0852        lsrs    r2, r2, #1
  16:   2b00        cmp r3, #0
  18:   d1f6        bne.n   8 <fun+0x8>
  1a:   4770        bx  lr

r1 is set to 1 outside the loop. this one is less efficient as it has to do the utxb every loop.

naturally you would never want to use a char for a loop variable like that (nor for that counter), you want a register sized variable unless you need one larger than register sized and the you have to just incur the cost.

unsigned int fun ( unsigned int tmp )
{
    unsigned int bits;
    bits=0;
    for (unsigned int pos=0; pos<32; pos++)
    {
        if (tmp & 1)
        {
            bits++;
        }
        tmp = tmp >> 1;
    }
    return(bits);
}

00000000 <fun>:
   0:   0003        movs    r3, r0
   2:   b510        push    {r4, lr}
   4:   2220        movs    r2, #32
   6:   2000        movs    r0, #0
   8:   2401        movs    r4, #1
   a:   0021        movs    r1, r4
   c:   3a01        subs    r2, #1
   e:   4019        ands    r1, r3
  10:   1840        adds    r0, r0, r1
  12:   085b        lsrs    r3, r3, #1
  14:   2a00        cmp r2, #0
  16:   d1f8        bne.n   a <fun+0xa>
  18:   bd10        pop {r4, pc}

that is a bit better

unsigned int fun ( unsigned int tmp )
{
    unsigned int bits;
    bits=0;
    for (unsigned int pos=0x80000000; pos; pos>>=1)
    {
        if (tmp & pos)
        {
            bits++;
        }
    }
    return(bits);
}

worse interestingly

unsigned int fun ( unsigned int tmp )
{
    unsigned int bits;
    bits=0;
    for (unsigned int pos=0x1; pos; pos<<=1)
    {
        if (tmp & pos)
        {
            bits++;
        }
    }
    return(bits);
}

not any better with this compiler.

When maybe you were looking for something like this

push {r4,lr}
mov r1,#0
mov r2,#1
mov r3,#32
top:
movs r4,r0
ands r4,r2
adds r1,r4
lsrs r0,r0,#1
subs r3,#1
bne top
mov r0,r1
pop {r4,pc}

For bit counting, but bit counting leads to some of this optimization (no need for a branch)

unsigned int fun ( unsigned int tmp, unsigned int bits )
{
    for (unsigned int pos=0; pos<32; pos++)
    {
        if (tmp & 1)
        {
            bits<<=2;
        }
        tmp >>= 1;
    }
    return(bits);
}

00000000 <fun>:
   0:   0003        movs    r3, r0
   2:   2220        movs    r2, #32
   4:   0008        movs    r0, r1
   6:   2101        movs    r1, #1
   8:   4219        tst r1, r3
   a:   d000        beq.n   e <fun+0xe>
   c:   0080        lsls    r0, r0, #2
   e:   3a01        subs    r2, #1
  10:   085b        lsrs    r3, r3, #1
  12:   2a00        cmp r2, #0
  14:   d1f8        bne.n   8 <fun+0x8>
  16:   4770        bx  lr

mov r1,#1 is still outside the loop. The compiler was told to do an and and it is doing an and and maybe there is no coded optimization around the corner case of and 1 with a shift right later.

unsigned int fun ( unsigned int tmp, unsigned int bits )
{
    for (unsigned int pos=0; pos<32; pos++)
    {
        tmp >>= 1;
        if (tmp & 1)
        {
            bits<<=2;
        }
    }
    return(bits);
}

This is obviously NOT functionally the same, but the compiler still uses an and (tst) here.

Would need to go look at the gcc sources to see when if ever it produces a bcc or bcs, not every instruction in an instruction set is used by a compiler, the authors have their favorite ways of doing things and the first job of the compiler is a functional equivalent. The optimizer likewise has to be functionally equivalent first, then maybe more efficient second.

OMG, okay, so I never use godbolt, and I did not see the right combinations (cortex-m), but I tried clang for armv6m and...well...they unrolled the loop for speed. with -O3

clang with -O2

Disassembly of section .text:

00000000 <fun>:
   0:   2220        movs    r2, #32
   2:   e003        b.n c <fun+0xc>
   4:   1e52        subs    r2, r2, #1
   6:   0840        lsrs    r0, r0, #1
   8:   2a00        cmp r2, #0
   a:   d003        beq.n   14 <fun+0x14>
   c:   07c3        lsls    r3, r0, #31
   e:   d0f9        beq.n   4 <fun+0x4>
  10:   0089        lsls    r1, r1, #2
  12:   e7f7        b.n 4 <fun+0x4>
  14:   4608        mov r0, r1
  16:   4770        bx  lr

and that is a whole other approach, you incur a lot of branches and the side effects of that (the cortex-m0+ pipe is tiny though). This could perform worse not just because of pipe stuff but because of fetching, you would need a three deep branch predictor cache, but you incur extra fetching. This is assumed to be an MCU running out of flash, and flash tends to be slow, depends heavily on the chip vendor and how fast you are running the mcu, etc. More instructions may be much faster than less instructions with more branches.

With these high performance architectures (arm, risc) you need to also take into account alignment, take the same machine code adjust it up or down one or two or three half words and it can perform tens of a percent slower (or faster) simply due to fetching. Running this code from ram instead of flash should help in general, but it depends on the chip vendor (arm is not a chip vendor) and how you are clocking things.

user_160070
Related