CS 61C (Fall 2007)

Lab Assignment 11

Goals

We intend this lab to expose you to effects of the MIPS pipeline on compiled code.

Reading

P&H section 6.1.

Setup

Work with a partner on these exercises.

Copy the file loops.c from the directory ~cs61c/files/lab/11 to a suitable location in your home directory. Here's the program.

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

int main ( ) {
	int a, b;
	int k1, k2, sum;
	char symbol[10];
	fgets (symbol, 10, stdin);
	a = atoi (symbol);
	fgets (symbol, 10, stdin);
	b = atoi (symbol);
	sum = 0;
	for (k1=0; k1<a; k1++) {
		for (k2=0; k2<b; k2++) {
			sum++;
		}
	}
	printf ("%d\n", sum);
	return 0;
}

Compile it twice, once with the default optimization level and once with optimization level 1, as follows. (Recall that the command-line option -O1—minus big-oh one—produces level-1 optimization.)

    mips-gcc -c loops.c -o loops.opt0.o
    mips-gcc -c loops.c -O1 -o loops.opt1.o

Then examine the assembly code:

    mips-objdump -S loops.opt0.o > loops.opt0.disasm
    mips-objdump -S loops.opt1.o > loops.opt1.disasm

Exercise 1 (2 points)

Focus first on the unoptimized code.

Identify the starting and ending addresses of the assembly language code that corresponds to the nested loop. Also identify locations of a, b, k1, k2, and sum relative to $s8.
The nop instructions occurring in the unoptimized code are no-ops. Not all the delay slots contain no-ops, however. Find the ones that don't, and explain why it's OK for the instructions in the delay slots always to be executed regardless of whether or not the branches are taken.

Exercise 2 (2 points)

Now examine the optimized code.

Again identify the starting and ending addresses of the assembly language code that corresponds to the nested loop, and identify which registers are used to store values of a, b, k1, k2, and sum.
Find the delay slots that contain instructions other than no-ops, and explain why it's OK for the instructions in the delay slots always to be executed regardless of whether or not the branches are taken.
Explain why neither of the instructions at addresses DC and E0 are candidates for filling the delay slot at address E8.
Replace the no-op at address D8 with a more useful instruction. (This will require changing the branch at address D4.)