Loops

Previously you learned how to write a function with a fixed number of parameters to perform a calculation and return a result. Now, what if you want to operate on a variable number of parameters? (Also known as a variadic argument) Let's say we want to pass a variable number of numbers to this function and make the function return their sum.

In assembly, we can put parameters wherever we want, as long as the function will know where to look for them. In the case of variadic functions, it's usually best to put the variadic arguments on the stack. But how does the function know how how many variadic arguments there are?

We could terminate the argument list with a "magic number" such as 0 or 0xdeadbeef, but since we're going to add numbers together, that would mean the caller couldn't safely pass those numbers to the function (unless we made the caller jump through even more hoops to allow the magic number to be used as an argument). The other option is to give the function a fixed argument indicating the number of variadic arguments, which is far easier to implement.

--

The high-level version of our function looks like this:

func sum(of numbers: Int...) -> Int {
    var sum = 0
    for i in numbers {
        sum += i
    }

    return sum
}

Now, there's a lot of syntax sugar here, because Swift allows you to use variadic arguments with Array semantics. The above function doesn't require us to explicitly pass the number of arguments. This is closer to what is actually happening under the hood, where n is the number of variadic arguments:

func sum(of n: Int, numbers: Int...) -> Int {
    var sum = 0
    for i in 0..<n {
        sum += numbers[i]
    }

    return sum
}

But wait, there's more! Primitive for-loops (as opposed to for-in loops) are just fancy while-loops. The loop above is equivalent to this:

...
var i = 0
while i < n {
    sum += numbers[i]
    i += 1
}

That's all. Just kidding! It can be more efficient to use a decrementing loop control variable (LCV) when you're looping over the range of some number from 0 to some upper bound, so the compiler turns the above code into this:

var i = n
while i > 0 {
    i -= 1
    sum += numbers[i]
}

Instead of counting from 0 to n-1, we count from n-1 to 0. That's a little more complicated, so lets go over what's happening before we move on:

1. i is the LCV.
2. i starts at n and the loop executes until i == 0.
3. When we first enter the loop, i is decremented before we access the last argument (at index n-1), so we never try to access numbers[n], which would be out of bounds.
4. The argument is added to the sum.
5. The loop condition is checked again: if i == 0, the loop exits, else, go to step 3.

When i is 1, the loop executes for the last time: i is decremented to 0 and we finally access the first parameter. Then since i == 0, the loop stops executing.

###How do you write a while-loop in assembly?

Without going into too much detail, assembly only has the ability to skip over instructions, forwards or backwards (this is called "branching", aka "jumping"). Instructions are grouped together using Labels and can be executed again by "jumping" to the label. (This is actually how functions are called!) Swift doesn't have language support for labels like C does, so while the crude implementation of labels provided doesn't work exactly like it would in assembly, it is sufficient for basic flow control in this project, such as if-else branching* (work in progress) and loops. A more detailed look at if-else control flow can be found here.

As you may have gathered, the first step is to initialize the LCV. It is convention to use rc as the LCV, so we're going to move n, which is in ra because it's the first fixed parameter, into rc. The second step is to create a Label for our loop. Each label is uniquely identified by a string. When you want to jump to a label, provide the string it was created with. The second argument to a label is the code itself as a closure.

func sum() {
    mov(.rc, .ra)    // n in rc
    Label("sumLoop") {
        // code here executes first
    }
    // then code below once label exits
}

Label is just a Swift type, but I've tried to make it look as close to actual assembly as possible. As soon as the label is created, it's body executes, then the code after the label's declaration continues to execute. Now, how many registers do we need to use? Are we going to clobber any registers the caller might be using?

We need two registers. One to hold the return value, sum, and one to be the LCV. ra will hold the return value as it always does, and rc will be the LCV. We're also going to need a third register, but I'll get to that later. Let's use rb. Before we create the label, we need to initialize our sum to 0, just after we move n to rc. But before we do that, we need to save a copy of rb and rc so we don't clobber it in case the caller is using them for something else, like his own loop. We should also save the Flags since we're doing arithmetic. At the top of our function, we save everything, and at the end we restore everything:

func sum() {
    // Save flags and registers we might clobber
    Stack.push([.rf])      // Save old frame pointer
    mov(.rf, .rs)          // Set new frame pointer
    Stack.push([.rb, .rc]) // Save rb and rc
    Stack.pushf()          // Save flags
    
    ...
    
    // Restore flags and registers in reverse order
    Stack.popf()          // Restore flags
    Stack.pop([.rc, .rb]) // Restore rb and rc
    mov(.rs, .rf)         // Restore old frame pointer,
    Stack.pop([.rf])      // discard it from stack
    
    // Deallocate parameter(s) from stack
    // by decrementing the stack pointer
    sub(.rs, 1)           // Only one parameter to deallocate
}

It's important to push and pop in reverse order, or else everything gets all mixed up. Draw it out on a piece of paper if you don't understand why it's necessary to push things in one order and pop them off in reverse order.

Now, you're probably wondering what we're saving rf for. By convention, rf is the stack frame pointer. When we have a lot we need to save and restore or if we want to save stuff on the stack temporarily, it becomes complicated to access function parameters unless you have a fixed frame of reference to them. By setting rf to rs (the stack pointer), we have a fixed frame of reference to the parameters. But since we can't clobber rf we have to save it first. We can access now the first parameter at rf - 1, and the second at rf - 2, and so on.

After we have the frame pointer set up, we save registers we use and the flags. It doesn't matter which order you push these in as long as you do it all in reverse order at the end.

Alright, now we can start working on the logic of our function! Here's what we have so far:

func sum() {
    // Save flags and registers we might clobber
    Stack.push([.rf])      // Save old frame pointer
    mov(.rf, .rs)          // Set new frame pointer
    Stack.push([.rb, .rc]) // Save rb and rc
    Stack.pushf()          // Save flags
    
    mov(.rc, .ra)        // n in rc
    Label("sumLoop") {
        // {code}
    }
    
    // Restore flags and registers in reverse order
    Stack.popf()          // Restore flags
    Stack.pop([.rc, .rb]) // Restore rb and rc
    mov(.rs, .rf)         // Restore old frame pointer,
    Stack.pop([.rf])      // discard it from stack
    
    // Deallocate parameter(s) from stack
    // by decrementing the stack pointer
    sub(.rs, 1)           // Only one parameter to deallocate
}

Right before that Label declaration, we need to initialize sum (ra) to 0. Then we fill out the loop body and we're done. In the loop, we need to retrieve the current variadic argument and add it to ra. Unfortunately we can't directly operate on things on the stack, so we need to load that argument into rb first, then add it to ra.

func sum() {
    // Save flags and registers we might clobber
    ...
    
    mov(.rc, .ra)          // n in rc
    mova(0)                // Shortcut to move 0 into `ra`
    Label("sumLoop") {
        mov(.rb, .rf)      // Point rb to the
        sub(.rb, .rc)      // current variadic argument
        mov(.rb, .rb + 0)  // Stack variable @ rb into rb
        add()              // sum += rb
    }

    // Restore flags and registers in reverse order
    ...
}

Now we need to decrement the LCV inside the loop and jump back to "sumLoop" if rc != 0, because if we don't, the code inside that label will only execute once. It sounds complicated, but thankfully it's common enough that it has it's own instruction! The loop instruction takes a label name, decrements rc for you, and jumps back to that label if rc != 0. Here's the finished product:

func sum() {
    // Save flags and registers we might clobber
    Stack.push([.rf])      // Save old frame pointer
    mov(.rf, .rs)          // Set new frame pointer
    Stack.push([.rb, .rc]) // Save rb and rc
    Stack.pushf()          // Save flags
    
    mov(.rc, .ra)          // n in rc
    mova(0)                // Shortcut to move 0 into `ra`
    Label("sumLoop") {
        mov(.rb, .rf)      // Point rb to the
        sub(.rb, .rc)      // current variadic argument
        mov(.rb, .rb + 0)  // Stack variable @ rb into rb
        add()              // sum += rb
        loop("sumLoop")    // next iteration 
    }

    // Restore flags and registers in reverse order
    Stack.popf()          // Restore flags
    Stack.pop([.rc, .rb]) // Restore rb and rc
    mov(.rs, .rf)         // Restore old frame pointer,
    Stack.pop([.rf])      // discard it from stack
    
    // Deallocate parameter(s) from stack
    // by decrementing the stack pointer
    sub(.rs, 1)           // Only one parameter to deallocate
}