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 main computers. Log on to one of those machines 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 an integer variable called insn_count and a printf format string that says "%d 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 addl $4,insn_count at the beginning of that block (but after any label).
6. Add code to the very end of the program, just before push $0/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 main machines, or some x86 Linux machine that runs GCC version 4.3.3; 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 addl 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 .p2align, .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.
• It's possible that the number of instructions will exceed the capacity of a 4-byte integer. How will you handle that case? One way is to use an 8-byte counter consisting of two 4-byte integers: one that counts every time and another that counts only when the first one rolls over to 0 again. If the two 4-byte integers are laid out in little endian, i.e., if the one that counts every time comes first in memory, then this 8-byte counter is the same as a long long int in C and can be printed using printf's %lld format.

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?

Example

#include <stdio.h>
#include <stdlib.h>

int main () {
	int	i, a, b;

	a = 1;
	b = 1;
	for (i=0; i<14; i++) {
		a = a + b;
		b = b + a;
	}
	printf ("%d\n", a);
	exit (0);
}

	.file	"sample.c"
	.version	"01.01"
gcc2_compiled.:
.section	.rodata
.LC0:
	.string	"%d\n"
.text
	.align 4
.globl main
	.type	 main,@function
main:
	pushl %ebp
	movl %esp,%ebp
	subl $24,%esp
	movl $1,-8(%ebp)
	movl $1,-12(%ebp)
	movl $0,-4(%ebp)
	.p2align 4,,7
.L3:
	cmpl $13,-4(%ebp)
	jle .L6
	jmp .L4
	.p2align 4,,7
.L6:
	movl -12(%ebp),%eax
	addl %eax,-8(%ebp)
	movl -8(%ebp),%eax
	addl %eax,-12(%ebp)
.L5:
	incl -4(%ebp)
	jmp .L3
	.p2align 4,,7
.L4:
	addl $-8,%esp
	movl -8(%ebp),%eax
	pushl %eax
	pushl $.LC0
	call printf
	addl $16,%esp
	addl $-12,%esp
	pushl $0
	call exit
	addl $16,%esp
	.p2align 4,,7
.L2:
	leave
	ret
.Lfe1:
	.size	 main,.Lfe1-main
	.ident	"GCC: (GNU) 2.95.4 20011002"

	.file	"sample.c"
	.version	"01.01"

# this section has some definitions needed for counting instructions

# declare an integer called 'insn_count'.  it is automatically initialied to 0
# by the assembler
	.comm	insn_count,4,4
# a constant string used for the 'printf' call that will print out
# the number of instructions executed

.count_string:
	.string	"%d instructions executed\n"

gcc2_compiled.:
.section	.rodata
.LC0:
	.string	"%d\n"

.text
	.align 4
.globl main
	.type	 main,@function

# basic block #1
main:
	addl $6,insn_count # six instructions in this block
	pushl %ebp
	movl %esp,%ebp
	subl $24,%esp
	movl $1,-8(%ebp)
	movl $1,-12(%ebp)
	movl $0,-4(%ebp)
	.p2align 4,,7
# basic block #2
.L3:
	addl $2,insn_count # two instructions in this block
	cmpl $13,-4(%ebp)
	jle .L6

# basic block #3
	addl $1,insn_count # one instruction in this block
	jmp .L4
	.p2align 4,,7
# basic block #4

.L6:
	addl $4,insn_count # four instructions in this block
	movl -12(%ebp),%eax
	addl %eax,-8(%ebp)
	movl -8(%ebp),%eax
	addl %eax,-12(%ebp)
# basic block #5
.L5:
	addl $2,insn_count # two instructions in this block
	incl -4(%ebp)
	jmp .L3
	.p2align 4,,7
# basic block #6
.L4:
	addl $9,insn_count # nine instructions up to 'call exit' in this block
	addl $-8,%esp
	movl -8(%ebp),%eax
	pushl %eax
	pushl $.LC0
	call printf
	addl $16,%esp
	addl $-12,%esp

# code to print out the instruction count

	movl insn_count,%eax
	pushl %eax
	pushl $.count_string
	call printf
	addl $16,%esp

	pushl $0
	call exit
	addl $16,%esp
	.p2align 4,,7
.L2:
	leave
	ret
.Lfe1:
	.size	 main,.Lfe1-main
	.ident	"GCC: (GNU) 2.95.4 20011002"

Due Date