An Introduction to Imperative Programming

To develop an intuition for what happens during the execution of a program, it is helpful to write down an execution trace of the program. An execution trace lists the instructions in the order they are executed and shows the effect of each instruction. In imperative programming languages (like our assembly language here), the execution of a program consists of multiple (potentially infinitely many) steps. In every step one instruction is being executed. The effect of an instruction is either a change of the state of the machine (changing the contents of a register or a memory cell) or an external effect which is an interaction with the environment (printing to the console, reading from a file, etc.).

Let us reconsider the factorial program from the introduction and let us assume the first instruction is located at address 0x00000000. This is the typical address at which the operating system loads our RISC-V programs. So the first couple of bytes in memory starting from this address contain our program which is indicated by this disassembly:

0x00000000: addi x11, x0 , 1
0x00000004: jal  x0,  12
0x00000008: mul  x11, x11, x10
0x0000000c: addi x10, x10, -1
0x00000010: blt  x0,  x10, -8
0x00000014: addi x10, x11, 0
0x00000018: jalr x0,  x1,  0

We write down an execution trace as a table. Each row is the snapshot of the state after executing an instruction. Each column shows one part of the state that is of interest. Note that the address of the instruction that is to be executed next is also part of the state. The following table shows the execution trace for our example program with a start state in which register $a0 contains the value 3 (of course it contains a bit string of 32 bits whose unsigned and signed interpretation is 3).

To determine the row in the trace, we need to know what effect the instruction at the current position has. To this end, Appendix A summarizes the effects of the RISC-V instructions we are going to use.

At the beginning, the program counter contains address 0x00000000. The instruction at this address is addi a1 x0 1. This instruction adds the constant 1 to the contents of register x0 and puts the result into register a1. (Of course, it also increases the program counter by 4.) Therefore, the next instruction to execute is located at address 0x00000004. This instruction, jal x0 12, branches 3 instructions ahead, and so on and so forth. We'll stop the execution trace for this example when reaching the ret instruction (which is a pseudo for jalr x0 x1 0) that would return to the caller of this function. (More on functions later in Section 2.8).