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 :)

Solution 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.

Solution 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

Comments

[Andrew T]

First off, I'd like to say thanks very much for your help Jake! I will avoid using if statements inside a loop in the future. There are a few questions about your assembly code that I am confused with though. I am new to assembly, so I don't necessarily understand some of the commands. How does movhi r0, #-1 check for overflow exactly? I have seen cases where "bx lr" is used following a function, what is the purpose of bxhi lr/bxlo lr/bxeq lr? And lastly, does the "b loop" mean that the loop will continue to iterate until r2=0? Again, thanks for your help :)

[Andrew T]

I will try and do what you've suggested, thanks for your help jmihalicza :)

[Jake 'Alquimista' LEE]

the cmp instruction sets the cpsr. and the following instructions can be executed conditionally depending on the cpsr. you might find my C code somewhat strange, because it's pretty much a 1:1 translation how I would write the function ins hand assembly.

[Jake 'Alquimista' LEE]

cmp, movhi, bxhi instructions build together a sequence "if (n > 47) return 0xffffffff". movhi r0, #-1 is equivalent to movhi r0, #0xfffffff, or mvnhi r0, #0. the actual check occurs with cmp, and both movhi and bxhi are executed conditionally depending on the cpsr.

[Jake 'Alquimista' LEE]

bx lr terminates the function UNCONDITIONALLY. bxhi terminates the function if the condition "HIgher" is met, blxo = bx if LOwer, bxeq = bx if EQual, etc....

[Jake 'Alquimista' LEE]

Your assembly is in Thumb2 mode, mine in ARM mode. While there are no reasons not to write Thumb2 codes, ARM mode is simply more convenient and efficient for hand written assembly. Thumb2 is more for the compiler generating compact binaries.

[Jake 'Alquimista' LEE]

Anyway, the loop again is the 1:1 equivalence of the C version. The compiler might give you a warning for not having a loop terminate condition. There is but a function terminating condition that will be guaranteedly met. The same in assembly. subs is a sub instruction with the suffix 's'. 's' fort setting the cpsr depending on the result of the operation. bxeq terminates the function upon r2 reaching zero.

[Andrew T]

I think I understand it now! Thanks again Jake, you've helped me a lot! :)