Creating Nested If-Statements in ARM Assembly

Question

I am interested in converting a Fibonacci sequence code in C++ into ARM assembly language. The code in C++ is as follows:

#include <iostream> 
using namespace std; 
int main()
{
    int range, first = 0 , second = 1, fibonacci; 
    cout << "Enter range for the Fibonacci Sequence" << endl; 
    cin >> range; 

    for (int i = 0; i < range; i++)
    {
        if (i <=1) 
            {
                fibonacci = i; 
            }
        else 
            {
                fibonacci = first and second; 
                first = second; 
                second = fibonacci; 
            }
    }
cout << fibonacci << endl; 

return 0; 
}

My attempt at converting this to assembly is as follows:

    ldr r0, =0x00000000 ;loads 0 in r0
    ldr r1, =0x00000001 ;loads 1 into r1
    ldr r2, =0x00000002 ;loads 2 into r2, this will be the equivalent of 'n' in C++ code, 
                         but I will force the value of 'n' when writing this code 
    ldr r3, =0x00000000 ;r3 will be used as a counter in the loop 

    ;r4 will be used as 'fibonacci'

loop:
    cmp r3, #2 ;Compares r3 with a value of 0
    it lt 
    movlt r4, r3 ;If r3 is less than #0, r4 will equal r3. This means r4 will only ever be
                  0 or 1. 

    it eq ;If r3 is equal to 2, run through these instructions
    addeq r4, r0, r1
    moveq r0,r1
    mov r1, r4
    adds r3, r3, #1 ;Increases the counter by one 

    it gt ;Similarly, if r3 is greater than 2, run though these instructions
    addgt r4, r0, r1
    movgt r0, r1
    mov r1, r4
    adds r3, r3, #1

I'm not entirely sure if that is how you do if statements in Assembly, but that will be a secondary concern for me at this point. What I am more interested in, is how I can incorporate an if statement in order to test for the initial condition where the 'counter' is compared to the 'range'. If counter < range, then it should go into the main body of the code where the fibonacci statement will be iterated. It will then continue to loop until counter = range.

I am not sure how to do the following:

cmp r3, r2 
;If r3 < r2
    {
        <code>
    }

;else, stop

Also, in order for this to loop correctly, am I able to add:

cmp r3, r2
bne loop

So that the loop iterates until r3 = r2?

Thanks in advance :)

Answer 1

It's not wise to put if-statements inside a loop. Get rid of it.

An optimized(kinda) standalone Fibonacci function should be like this:

unsigned int fib(unsigned int n)
{
  unsigned int first = 0;
  unsigned int second = 1;
  unsigned int temp;

  if (n > 47) return 0xffffffff; // overflow check
  if (n < 2) return n;

  n -= 1;

  while (1)
  {
    n -= 1;
    if (n == 0) return second;
    temp = first + second;
    first = second;
    second = temp
  }
}

Much like factorial, optimizing Fibonacci sequence is somewhat nonsense in real world computing, because they exceed the 32-bit barrier really soon: It's 12 with factorial and 47 with Fibonacci.

If you really need them, you are served the best with very short lookup tables.

If you need this function fully implemented for larger values: https://www.nayuki.io/page/fast-fibonacci-algorithms

Last but not least, here is the function above in assembly:

cmp r0, #47     // r0 is n
movhi   r0, #-1     // overflow check
bxhi    lr
cmp r0, #2
bxlo    lr

sub r2, r0, #1  // r2 is the counter now
mov r1, #0      // r1 is first
mov r0, #1      // r0 is second

loop:
subs    r2, r2, #1  // n -= 1   
add r12, r0, r1 // temp = first + second
mov r1, r0      // first = second
bxeq    lr      // return second when condition is met
mov r0, r12     // second = temp
b   loop

Please note that the last bxeq lr can be placed immediately after subs which might seem more logical, but with the multiple issuing capability of the Cortex series in mind, it's better in this order.

It might be not exactly the answer you were looking for, but keep this in mind: A single if statement inside a loop can seriously cripple the performance - a nested one even more.

And there are almost always ways avoiding these. You just have to look for them.

Answer 2

Conditionals compile to conditional jumps in almost all assembly language:

if (condition)
  ..iftrue..
else
  ..iffalse..

becomes

   eval condition
   conditional_jump_if_true truelabel
   ..iffalse..
   unconditional_jump endlabel
truelabel:
   ..iftrue..
endlabel:

or the other way around (exchange false and true).

ARM supports conditional execution to eliminate these jumps when compiling the innermost conditionals: http://www.davespace.co.uk/arm/introduction-to-arm/conditional.html

IT... is a Thumb-2 instruction: http://en.wikipedia.org/wiki/ARM_architecture#Thumb-2 to support unified assemblies. See http://www.keil.com/support/man/docs/armasm/armasm_BABJGFDD.htm for more details.

Your code for looping (cmp and bne) is fine.

In general, try to rewrite your code using gotos instead of cycles, and else parts. else can remain only at the deepest nesting level. Then you can convert this semi-assembly code to assembly much more easily.

HTH