Read these instructions carefully. The objective of this assignment is for you to become comfortable working with assembly language programs. For this assignment, you will count the number of machine language instructions executed by a C program for two different levels of compiler optimization. You will do this compiling the C program into assembly language, then placing instrumentation code into the assembly language program. The instrumentation code keeps a running total of the number of instructions executed so far, then prints out that number at the end of the program.

How to do this assignment

1. Obtain the prog.c C program by clicking on the link in this sentence.
2. Compile the C program to assembly language on the linux computer in the CSE department. Log on to linux and place the C program into your directory. Compile the program to assembly lanuage with the following command line:

   gcc -S -o prog-O0.S -O0 prog.c
   

   The -O0 option tells the compiler to compile with optimization level zero, i.e., no optimizations. The -S option tells the compiler to compile to assembly language instead of to an executable program, and to place the assembly language in a file called prog-O0.S.
3. Edit the assembly language program and divide it into basic blocks. Rather than count each individual instruction, you will count groups of instructions, called basic blocks, together. A basic block is a sequence of instructions that are executed together. A basic block begins either after a label or after a jump instruction, and end either at a label or a jump instruction. Place a comment before each basic block and white space around it so that the division of the program into basic blocks is clear. Comments in an assembly language program begin with '#' and continue until the end of the line.
4. Place definitions in the assembly language program for a 64-bit integer variable called insn_count and a printf format string that says "%lld instructions executed".
5. Count the number of instructions in each basic block. At the beginning of each basic block, insert an instruction that adds that number to insn_count. For instance, if there are four instructions in a basic block, then you would insert the instruction addq $4,insn_count(%rip) at the beginning of that block (but after any label).
6. Add code to the very end of the program, just before call exit, to print out insn_count using printf and the format string defined earlier.
7. Assemble and run the instrumented program with the following commands:

   gcc -o prog-O0 prog-O0.S
   ./prog-O0
   

8. Repeat steps 2 through 7, using instead the following command line to compile the program:

   gcc -S -o prog-O3.S -O3 prog.c
   

   The -O3 option tells the compiler to compile with optimization level three, i.e., aggressive optimizations.

Additional Information

• You must use the linux or linux2 machine, or some x86-64 Linux machine that runs GCC version 4.8.5; if you do not, your instruction count will be incorrect with respect to our reference machine.
• There are two kinds of jump instructions: conditional branches, e.g. je, jl, jle, jne, and unconditional jumps, i.e. jmp. Each of these kinds of jumps can end a basic block. Don't worry about call or ret instructions; although they are technically considered jumps, we'll just pretend for now that they are just like any other instruction.
• Don't insert an addq instruction right before a conditional branch, since this may alter the behavior of the branch.
• Do not count instructions that begin with a period such as .cfi_def_cfa_register, .type, .globl, etc. These are not actually instructions, but assembler pseudo-ops that don't result in machine language operations.
• This assignment is conceptually simple once you understand the concept of adding instrumentation code. However, the assembly code will be somewhat long and the process of instrumenting it will be tedious; make sure you give yourself plenty of time for this assignment, and go over each basic block to make sure you have counted everything just right.
• Your insn_count variable is a 64-bit integer. How do you print that out with printf?

Requirements

1. Your instrumented and commented prog-O0.S.
2. Your instrumented and commented prog-O3.S.
3. A paragraph describing your observations of what happened when you ran the programs. How many instructions did prog-O0 execute? How many instructions did prog-O3 execute?

Due Date