4

I am trying to implement a function which multiplies 32-bit operand with 256-bit operand in ARM assembly on ARM Cortex-a8. The problem is I am running out of registers and I have no idea how I can reduce the number of used registers here. Here is my function:

typedef struct UN_256fe{

uint32_t uint32[8];

}UN_256fe;

typedef struct UN_288bite{

uint32_t uint32[9];

}UN_288bite;
void multiply32x256(uint32_t A, UN_256fe* B, UN_288bite* res){

asm (

        "umull          r3, r4, %9, %10;\n\t"
        "mov            %0, r3;         \n\t"/*res->uint32[0] = r3*/
        "umull          r3, r5, %9, %11;\n\t"
        "adds           r6, r3, r4;     \n\t"/*res->uint32[1] = r3 + r4*/
        "mov            %1, r6;         \n\t"
        "umull          r3, r4, %9, %12;\n\t"
        "adcs           r6, r5, r3;     \n\t"
        "mov            %2, r6;         \n\t"/*res->uint32[2] = r6*/
        "umull          r3, r5, %9, %13;\n\t"
        "adcs           r6, r3, r4;     \n\t"
        "mov            %3, r6;         \n\t"/*res->uint32[3] = r6*/
        "umull          r3, r4, %9, %14;\n\t"
        "adcs           r6, r3, r5;     \n\t"
        "mov            %4, r6;         \n\t"/*res->uint32[4] = r6*/
        "umull          r3, r5, %9, %15;\n\t"
        "adcs           r6, r3, r4;     \n\t"
        "mov            %5, r6;         \n\t"/*res->uint32[5] = r6*/
        "umull          r3, r4, %9, %16;\n\t"
        "adcs           r6, r3, r5;     \n\t"
        "mov            %6, r6;         \n\t"/*res->uint32[6] = r6*/
        "umull          r3, r5, %9, %17;\n\t"
        "adcs           r6, r3, r4;     \n\t"
        "mov            %7, r6;         \n\t"/*res->uint32[7] = r6*/
        "adc            r6, r5, #0 ;    \n\t"
        "mov            %8, r6;         \n\t"/*res->uint32[8] = r6*/

        : "=r"(res->uint32[8]), "=r"(res->uint32[7]), "=r"(res->uint32[6]), "=r"(res->uint32[5]), "=r"(res->uint32[4]),
           "=r"(res->uint32[3]), "=r"(res->uint32[2]), "=r"(res->uint32[1]), "=r"(res->uint32[0])
         : "r"(A), "r"(B->uint32[7]), "r"(B->uint32[6]), "r"(B->uint32[5]),
           "r"(B->uint32[4]), "r"(B->uint32[3]), "r"(B->uint32[2]), "r"(B->uint32[1]), "r"(B->uint32[0]), "r"(temp)
         : "r3", "r4", "r5", "r6", "cc", "memory");

}

EDIT-1: I updated my clobber list based on the first comment, but I still get the same error

3
  • Your asm statement has a bigger problem. You need to add all the registers you specified explicitly in the asm statement to the clobber list (which also needs to include "cc"). Those clobbers plus all the registers needed to hold the input and output operands (which also need to marked as early clobber) mean you're using way more registers than ARM has. You've only made the problem worse over your last attempt.
    – Ross Ridge
    Dec 14, 2015 at 2:54
  • @RossRidge Is there any way that I can use another notation instead of "r" before my inputs and get the correct results? I mean something like "g" or "m"?
    – A23149577
    Dec 14, 2015 at 3:03
  • You really need a loop [with iteration count 8] than what you're doing. Reconsider: How would you do it if your input vector had 20,000 elements in it? You'd need reg for scalar A value, reg for B ptr, reg for res ptr, reg for iteration count, and whatever other regs you need to do umull et. al [probably another 4-6] on each loop iteration, so total is ~10. As it is, you run out of regs with a vector size of 2-3, let alone 8. To get your vector algorithm straight, how about coding a C fnc that does this [also serves as reference for you asm fnc]. Dec 14, 2015 at 4:01

1 Answer 1

0

A simple solution is to break this up and don't use 'clobber'. Declare the variables as 'tmp1', etc. Try not to use any mov statements; let the compiler do this if it has to. The compiler will use an algorithm to figure out the best 'flow' of information. If you use 'clobber', it can not reuse registers. They way it is now, you make it load all the memory first before the assembler executes. This is bad as you want memory/CPU ALU to pipeline.

void multiply32x256(uint32_t A, UN_256fe* B, UN_288bite* res) 
{

  uint32_t mulhi1, mullo1;
  uint32_t mulhi2, mullo2;
  uint32_t tmp;

  asm("umull          %0, %1, %2, %3;\n\t"
       : "=r" (mullo1), "=r" (mulhi1)
       : "r"(A), "r"(B->uint32[7])
  );
  res->uint32[8] = mullo1; /* was 'mov %0, r3; */
  volatile asm("umull          %0, %1, %3, %4;\n\t"
      "adds           %2, %5, %6;     \n\t"/*res->uint32[1] = r3 + r4*/
     : "=r" (mullo2), "=r" (mulhi2), "=r" (tmp)
     : "r"(A), "r"(B->uint32[6]), "r" (mullo1), "r"(mulhi1)
     : "cc"
    );
  res->uint32[7] = tmp; /* was 'mov %1, r6; */
  /* ... etc */
}

The whole purpose of the 'gcc inline assembler' is not to code assembler directly in a 'C' file. It is to use the register allocation logic of the compiler AND do something that can not be easily done in 'C'. The use of carry logic in your case.

By not making it one huge 'asm' clause, the compiler can schedule the loads from memory as it needs new registers. It will also pipeline your 'UMULL' ALU activity with the load/store unit.

You should only use clobber if an instruction implicitly clobbers a specific register. You may also use something like,

register int *p1 asm ("r0");

and use that as an output. However, I don't know of any ARM instructions like this besides those that might alter the stack and your code doesn't use these and the carry of course.

GCC knows that memory changes if it is listed as an input/output, so you don't need a memory clobber. In fact it is detrimental as the memory clobber is a compiler memory barrier and this will cause memory to be written when the compiler might be able to schedule that for latter.


The moral is use gcc inline assembler to work with the compiler. If you code in assembler and you have huge routines, the register use can become complex and confusing. Typical assembler coders will keep only one thing in a register per routine, but that is not always the best use of registers. The compiler will shuffle the data around in a fairly smart way that is difficult to beat (and not very satisfying to hand code IMO) when the code size gets larger.

You might want to look at the GMP library which has lots of ways to efficiently tackle some of the same issues it looks like your code has.

7
  • First of all thank you for your brief answer. I have a question, If I want to get the best performance out of this function, isn't it better to implement all the code in inline assembly? I know I might run out of registers like here, but I was thinking of putting my pointers (*B and *res) inside two registers and get access to each uint32_t array by using ldr instruction. I am not sure if it is possible, but the performance is really important for me
    – A23149577
    Dec 14, 2015 at 17:58
  • Yes, you can use the ldr in your code; and I was thinking about this as a bench mark. The compiler has hueristics and smarts to interleave the ALU and load/store (ldr/str) instructions. It may even do ldm/stm and/or ldrd/strd depending on memory order and what registers are available and the class of CPU (you will hard code this for an A8 where not doing the load/store will allow the compiler to choose). By all means you can do one big routine and use the ldr because you have run out of ARM registers. However, I think you will discover a lot if you split and look at the output. Dec 14, 2015 at 18:05
  • 2
    You might be surprised that your algorithm is memory bound/dominant and not CPU bound/dominant. For certain your current large routine is not letting these operation pipeline or happen in parallel (people also say memory stall). I do believe that you can beat the compiler after seeing it's output. It is rare for me to beat it (on larger sized routines) if I don't see what sort of things it might do before hand. Currently you have 9/25 ~= 36% of instructions as mov statements and haven't accounted for what the compiler does to load/store things. Dec 14, 2015 at 18:17
  • Thank you so much again I will implement it as you said and compare the performance with my C implementation and put the result here
    – A23149577
    Dec 14, 2015 at 18:20
  • 1
    This has some limitations when you use the carry. You can not have branches (which might set the carry) in-between the asm statements. So, a 'C' purest might be repulsed (but it is already asm). In any case it gives a better starting base (with compiler register allocation and memory scheduling) that you can work with. Or maybe you are happy with the several 'asm' block variant. Just mark them as 'volatile' to let the compiler know that their order is important and add a comment not to use 'if/while/etc' in the following 'asm' sections as we want to preserve the carry between them. Dec 14, 2015 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.