CS 5513 Fall 2007, Homework 2

Consider the following program in x86 assembly language: (Note: This version of the program corrects the version that was posted previously.)

foo:
	pushl	%ebx
	xorl	%ecx, %ecx
	movl	$1, %edx
	movl	8(%esp), %ebx
foo010:
	movl	%edx, %eax
	addl	$1, %edx
	andl	%ebx, %eax
	addl	%eax, %ecx
	cmpl	$20, %edx
	jle	foo010
	movl	%ecx, %eax
	popl	%ebx
	ret

format_string:
	.string	"%d\n"

.globl main
main:
	pushl	%ebp
	movl	%esp, %ebp
	pushl	%esi
	xorl	%esi, %esi
	pushl	%ebx
	movl	$1, %ebx
	subl	$16, %esp
	andl	$-16, %esp
	subl	$16, %esp
main010:
	movl	%ebx, (%esp)
	call	foo
	addl	$1, %ebx
	addl	%eax, %esi
	cmpl	$100000000, %ebx
	jle	main010
	movl	%esi, 4(%esp)
	movl	$format_string, (%esp)
	call	printf
	leal	-8(%ebp), %esp
	xorl	%eax, %eax
	popl	%ebx
	popl	%esi
	popl	%ebp
	ret

1. Log in to an x86 Linux workstation in the 3rd floor SB lab. Edit the assembly language program. For each line of the program, add at least one comment (beginning with the '#' character) describing what that line does. Whenever possible, the comment should describe how that line helps implement the program, not just what the instruction does. Beyond just commenting on the functionality of each instruction, your comments should make it clear how the program works, i.e. what the algorithm is and what the purpose of each register is in the algorithm. When you don't know what a statement is doing, speculate what you think it might be doing.
2. Assemble the program and run it. How long does it take to run? Note: To assemble the program, save it to a file with extension .s, e.g. foo.s, and compile it with gcc as you would a C program, e.g. gcc -o foo foo.s. To time it, use time and report the "user" time. Since others may be using the same machine, run the program several times and report the fastest time.
3. The foo function has a loop in it in which a variable takes on values from 1 through 20 and each of those values is used in a computation, then the loop stops when the variable reaches 21. Re-write the function so that there are two loops: one that goes from 1 through 10 and another that goes from 11 through 20. Assemble the program again. Time the program again. Write a paragraph summarizing your observations. How do you explain the observed change in performance?
   
   Note: For the rest of the problems, refer to the original program, not your modified program.
   
   
4. When the original program is executed, how many machine language instructions will be executed? (Don't try to count any instructions executed by the implementation of printf) Explain the procedure you used to come up with your result.
5. Assume branch instructions (e.g. jle, call, ret, etc.) take two cycles to execute, register-memory instructions take three cycles, and all other instructions take one cycle. How many cycles will the program take? What is the IPC (instructions-per-cycle) in this case?

Hand your assignment in on paper at the beginning of class on September 18. Your work should be produced using a word processor or editor Please separate your answers to the problems, e.g., don't answer the second and fourth questions in the same space.

Note: I haven't given you enough information in class to do this assignment, and you won't find enough information in the book. You will have to find some of the information on your own. The World Wide Web is a great place to start looking for this information. Don't start with a top-down approach, i.e., don't try to learn all of x86 assembly language and then start this assignment. Rather, take a bottom-up approach. Using a search engine, find out just enough information to do the assignment.