An Introduction to Imperative Programming

Let us explore the ingredients of an assembly code file by means of the example in Listing 2.3.2. The figure shows six instruction words that are located somewhere in the memory of the computer. The left column shows the instruction words as hexadecimal 32-bit numbers. The second and third column show the textual representation of the respective instruction word.

24020001 addiu $2 $0  1
04010002 bgez  $0 2
70441002 mul   $2 $2 $4
2484ffff addiu $4 $4 -1
1c80fffd bgtz  $4 -3
03e00008 jr    $31

The second column represents the so-called mnemonic which is a short textual description of the opcode, i.e. the operation the instruction stands for such as mul for multiplication or addiu for “add a register to an immediate and ignore overflows”. The last column gives the operands of instruction. Registers are prefixed by the $ sign, e.g. $2 refers to register 2. Numbers without dollar signs represent immediates. So, addiu $2 $0 1 adds the value 1 to the contents of register 0 and stores the result in register 2. Effectively, this instruction places the value 1 into register 2 because register 0 always reads as zero. The instructions bgtz and bgez are control flow instructions that alter the value of the program counter. bgtz $4 -3 for example tests, if the value in register 4 is greater than zero (=gtz). If this is the case, the program counter is advanced by -3 instructions relative to the next instruction. (so, if the branch instruction is located at address 0x04000008, the pc will be set to 0x04000000.) If this is not the case, the program counter advances normally to the next instruction and the branch has no other effect. When adding a value to an address (like adding -3 to the pc in this example), this value is called an offset. Branches that take offsets are called relative branches whereas branches that take addresses as operands are called absolute branches. jr is an absolute branch: it sets the program counter to the contents of its operand register. A branch instruction that branches on a condition like in this example, is called a conditional branch. Sometimes one also dedicates the term branch specifically to conditional branches and calls unconditional branches jumps. The instruction bgez $0 2 acts as an unconditional branch here. bgez checks if the operand register is greater or equal than zero (=gez). Since the operand register here is register 0 which is always zero, the condition is always fulfilled and the instruction will branch every time it is executed making it an unconditional branch instruction, effectively.

Computing offsets for relative branches is tedious and error-prone. Even worse, if one inserts new code between the branch and its target, the offset has to be recalculated. One of the prime tasks of an assembler is therefore to provide labels. Every entity in an assembler file that will be put somewhere in memory (such as instructions but also static data, Section 2.5 Every instruction (in general every address in a segment) can be marked with a label that stands for the address of the entity. One can refer to these labels at various places (such as in the operand list of relative branch instructions) and the assembler automatically computes the appropriate offsets for us. Listing 2.3.4 shows the assembly file from which the assembler produced the binary code shown in Listing 2.3.2.

    .text
    .globl factorial
factorial:
    li    $v0 1       # load 1 into register $v0
    b     check       # jump to label check
loop:
    mul   $v0 $v0 $a0 # multiply $v0 with $a0 and put 
                      # result into $v0
    addiu $a0 $a0 -1  # Subtract 1 from $a0 
check:
    bgtz  $a0 loop    # branch to loop, if $a0 > 0       
    jr    $ra         # return to caller

Labels are defined by giving a name followed by a colon. factorial, loop, check are all labels. All other occurrences of these labels refer to them. The address the label stands for is the address at which the instruction that follows the label will be placed in memory when the program is loaded.

Another difference from the assembly code in Listing 2.3.2 to Listing 2.3.4 is that it is customary to use short names for registers. Instead of referring to register 4 as $4 we write $a0 here. This short name comes from the so-called calling convention, a set of rules the we use to assign specific roles to registers when calling function which we will discuss in Section 2.8.

Furthermore, Listing 2.3.4 shows some examples for assembler directives. .text is a directive that indicates that everything that follows is code. It activates the assembly code function which allows us to write mnemonic and register names instead of hand-coding instructions. .text also tells the linker later on that everything that follows has to be placed into the code (sometimes called text) segment. We will discuss segments later in Section 2.6. .globl factorial makes the label factorial visible from other translation units (see Figure 2.3.1. Labels that are not declared global are local to a translation unit and cannot be referred to from other translation units. This prevents that situation that programmers accidentally use the same label name in different files that would clash if the label's name was global. Note also the use of pseudo instructions as discussed in Remark 2.3.3.

Finally, let us give a main program that calls our factorial function. By convention, program execution starts at instruction with the label main. Our main program shall compute that factorial of 10, display the output on the console, and terminate the program.

    .text
    .globl main
main:
    li   $a0 10    # load 10 into register $a0
    jal  factorial # call function factorial
    move $a0 $v0   # result is in $v0; move to $a0
    li   $v0 1     # load syscall number 1 into $v0
    syscall        # call system to output
    li   $v0 10    # load syscall number 10 into $v0
    syscall        # call system to end program

Our main program calls the operating system to perform input and output operations. Here, we do go into details about operating systems. For our purposes, it is sufficient to accept that there is some system that we can interact with using the syscall instruction. We specify what exactly we want the operating system to do by putting a certain number into the $v0 register. Here, 1 means print the number stored in $a0 as a decimal number on the console and 10 means terminate the program.

There is one other new instruction in Listing 2.3.5: jal. jal stands for “jump and link”. A jal instruction has an immediate that it interprets as an absolute address ⁴ before setting the program counter to that address, it stores the address of the instruction that follows the jal into register 31. This is the address the function that jal calls will want to return to. This is why register 31 is also called $ra (= return address).