Skip to main content

Section 2.4 Execution Traces

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

Remark 2.4.1. State.

The structure of the state is a part of the semantics of the language. In the MIPS machine code language, the state is given by the contents of the registers and the memory. When discussing higher-level programming languages later, we introduce the concept of a variable which will make our states more “structured”

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

0x00400000: addiu $v0 $0 1
0x00400004: bgez  $0 2
0x00400008: mul   $v0 $v0 $a0
0x0040000c: addiu $a0 $a0 -1
0x00400010: bgtz  $a0 -3
0x00400014: jr    $ra

We write down an execution trace as a table. Each row is the snapshot of the state before 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).

$pc $v0 $a0
0x00400000 ? 3
0x00400004 1 3
0x00400010 1 3
0x00400008 1 3
0x0040000c 3 3
0x00400010 3 2
0x00400008 3 2
0x0040000c 6 2
0x00400010 6 1
0x00400008 6 1
0x0040000c 6 1
0x00400010 6 0
0x00400014 6 0

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 MIPS instructions we are going to use.

At the beginning, the program counter contains address 0x00400000. The instruction at this address is addiu $v0 $0 1. This instruction adds the constant 1 to the contents of register $0 and puts the result into register $v0. (Of course, it also increases the program counter by 4.) Therefore, the next instruction to execute is located at address 0x00400004. This instruction, bgez $0 2, branches 2+1 instructions ahead if the content of register $0 equals 0, which it always does. In fact, this instruction is an unconditional jump that sets the program counter 3 instructions ahead and so on and so forth. We'll stop the execution trace for this example when reaching the jr $ra instruction that would return to the caller of this function. (More on functions later in Section 2.8).