CPE 1040 - Introduction to Computer Engineering

Assignment: Tracing an ARM Assembly Program (Part 2)

1. Summary

This assignment comes in two parts, assigned separately:

1. Part 1 asks you to interpret (in human language) a short ARM assembly program that was originally compiled from a C program. Both programs are provided in the repository, but you can see them next to each other in the online Compiler Explorer, with code correspondences highlighted in different colors. Note: The C program and the corresponding assembly program are modified from Part 1. See the more extensive note in the requirements below.
2. Part 2 asks you to trace the same program. To trace a program means to mock-execute each line/instuction and follow the manipulation of the data.

2. Requirements

1. The processor is a state-full machine. When tracing an assembly program you are essentially keeping track of the processor's state. The state of the processor can be approximated by the following set of memories:

   1. The 16 registers:

      1. They are labeled R0 to R15

      2. Most of the a generic, meaining they can be used at the discretion of the programmer

      3. Some of them have conventional special purposes, and so have extra names, and those names are used in assembly programs. They are:

         Generic name	Spacial name	Special purpose
         R11	FP	Frame pointer
         R12	IP	Intra-procedural call
         R13	SP	Stack pointer
         R14	LR	Link register
         R15	PC	Program counter
         n/a	CPSR	Current program status register (aka ASPR)

      4. The CSPR (aka ASPR, for Application Program Status Register) contains 4 important 1-bit flags:

         Flag mnemonic	Flag name	Enabled (value = 1) if the result of the last instruction is
         N	Negative	A negative number
         Z	Zero	A zero value
         C	Carry	A value that requires a 33rd bit to be fully represented
         V	Overflow	A value that cannot be represented in 32 bit two’s complement

      5. The NZCV flags are important for conditional execution. By rule, only the comparison instructions always change those flags. Any other instruction can be forced to change the flags by appending an S to its name (e.g. MOV becomes MOVS). See the instruction set summary.

   2. The contents of the instruction cache (assume it is equivalent to the program you are tracing)

   3. The contents of the data cache

   4. The contents of the call stack

2. In part 1, you interpreted (aka decoded) the instructions of an ARM assembly program.

3. Now, in part 2, you need to actually trace a program. NOTE: The program in Part 2 is slightly different from the one in Part 1. Specifically, the int value is not local to main, but global to the program. When value is local to main, it exists temporarily in the stack frame of main, and it is lost when the frame is popped at the end of execution. When value is global, it is saved in a memory region different from the stack, and it is not lost at the end of execution of main. In practical terms, this means that there will be now extra assembly instructions, generated by the compilation of the C program, that load value from its memory storage, and then write it back, now modified, before the end of the program.

4. A simplified representation of the processor state, sufficient for this exercise, is provided in this sketch. You need to make your own copies to edit them. Save as PNG when adding to your repository for submission.

5. You need to show the processor state (including registers, the stack, and the data memory) at 3 different instants of the program. These are:

   1. After line 15 but before line 16 of negate_program.S.
   2. After line 7 but before line 8 of negate_program.S.
   3. After line 26 but before line 27 of negate_program.S.

3. Guidelines

1. Ignore the IR (instruction register), MAR (memory address register), and MDR (memory data register) registers in the bottom left.
2. Assume that, at the start of the program, value is stored at location 0x00000000 of the data memory (the rightmost memory region in the sketch). Please, use hexadecimal when representing addresses and values in memory. For example, 6₁₀ = 0x00000006 and -6₁₀ = 0xfffffffa. Remember that one hexadecimal digit corresponds to 4 bits (aka one nibble, or half-byte).
3. The ARM Cortex-M0 is a 32-bit architecture, which means that both the registers and the memory locations in the sketch are all 4 bytes long. You will see that the stack pointer is being moved by multiples of 4. A 4-byte memory location with an address that divides by 4 is called a word.
4. Assume that the stack grows from address 0x00001077 down toward lower addresses (notice the arrow next to the stack region in the sketch). The stack grows by subtracting from the stack pointer (sp), and, conversely, shrinks by adding to the stack pointer. The stack pointer is a register holding an address. The stack pointer always points to the top of the stack (that is, the word with the lowest address in the stack).
5. It is optional to fill in the addresses of the stack, but it might be helpful. You will need to
6. Remember, the program starts with the main function, so the first instruction to be executed is on line 12 of negate_program.S.
7. You need to keep track of the NZCV flags (see above). You will need the following:
   1. Summary of the ARM Cortex-M0 instruction set, which lists the flags each instruction modifies. This also gives you links to the instruction documentation. Note that, in the documentation, instructions are clustered into groups that belong together.
   2. Description of the flags, which lists the conditions which they correspond to, when combinations of them are set or not set. In the processor, this is done directly in hardware. When you are doing the tracing, you have to decide if an instruction is going to set a flag or not. Read the documentation for the instruction to find out.
   3. The flags cannot be forced to 0 (there is a way, but it is deliberately complicated), but only set or unset by subsequent instructions.
8. When the C program has global data, in the assembly program this data is given an address label (the exact address is determined at link or run time). Here is a portion of the assembly program which shows how value is transfered between data memory and registers (see comments, after the semicolons ;, for explanation):

   value:
           .word   6           ; the 'value' variable is a word, holding the immediate value of 6 (decimal)
           
           ...
   
   main:
           ...
           ldr     r3, .L6     ; load .L6 (see below) into r3
           ldr     r3, [r3]    ; dereference r3 ([r3] is a dereferencing) to get the immedate value, and store back into r3
           cmp     r3, #0      ; use the value in r3 to compare to 0 (if statement)
           
           ...
           
           movs    r2, r0      ; store the result of negate into r2
           ldr     r3, .L6     ; load the address of the original variable
           str     r2, [r3]    ; store the contents (value) of r2 at the location pointed by r3 (dereferencing)
           
           ...
           
   .L6:
           .word   value      ; the address of the 'value' variable, represented by the label .L6

9. Notice that the generated assembly is redundant. Some operations are repeated. Don't worry about it. The assembly is correct, though it can be optimized, and made more efficient.

Resources

C

1. C reference
2. C tutorial
3. C interactive tutorial
4. Open book How to Think Like a Computer Scientist: C Version

ARM assembly

1. ARM Cortex-M0 Instruction Set Summary
2. Azeria Labs Introduction to ARM Assembly Basics
3. Dave Space Introduction to ARM
4. ARM Cortex-M0 instruction set summary
5. ARM conditional execution

Github

1. Github Tutorial for Beginners (webpage).
2. Github Basics for Mac and Windows (video).
3. git & Github Crash Course for Beginners (video).
4. Introduction to Github for Beginners (video).
5. About git (webpage).
6. git documentation (webpage, book, videos, reference manual).
7. Github markdown cheat sheet.