In this lab you will compile a series of programs written in the C programming language, examine the assembly language they generate, and run it in the miniMIPS simuator. Start by entering the following program into the miniMIPS C-compiler.
int x, y;
int gcd() {
while (x != y)
if (x < y)
y = y - x;
else
x = x - y;
}
int main() {
x = 72;
y = 120;
gcd();
return x;
}
Press [Compile], and then, if there are no syntax errors, a window will appear with the generated assembly language. Examine the assembly code and contrast it with the code you developed in last week's lab. Next, cut and paste this code into the miniMIPS simulator. Set a breakpoint at the "halt" label (insert a * in front of the line "halt:"), and run it. Examine the results in $2.
Getting used to mistakes
Try modifying the given code in the compiler window (you will need to go back a page in your browser window with the generated assembly code). You should also insert a syntax error (i.e. remove a ";") to see how the miniMIPS C-compiler responds.
Checkoff 1. Notice that the compiler uses the la (load address) pseudoinstruction twice in the main() function. Explain what these la are being used for by the compiler. What actual instructions are generated by the assembler? Is this usage consistent with the instruction's name (i.e. is it used to load an address into a register)?
Lab
The C preprocessor
Prior to compilation, all C code is first processed by a pre-processor, called cpp. All cpp directives are prefixed by a "#" (pronounce "pound-sign" or "sharp-sign"). The pre-processor is used for defining constants, macros, and including files. Essentially, cpp inserts or replaces blocks of text where referenced.
In the example shown below a constant "N" is defined and referenced in the program. One can consider that everywhere that the symbol "N" appears in the program, where it is not part of a variable name, is substituted with the given constant value, "8" in this case. A cpp macro called "SWAP" is also defined as a shorthand for a three C statements. By convention capital letters are used for cpp constants and macro arguments. These arguments are substituted with the actual text supplied when the macro is invoked.
Within the macro a temporary variable "t" is defined. Notice that the declaration of "t" includes the "register" type modifier, which tells the compiler to store the variable being declared in a CPU register (if possible), to optimize access.
Now compile the following C program and copy the generated assembly code into the simulator
#define N 8
#define SWAP(X,Y) {register int t = X; X = Y; Y = t;}
int x = 2;
int y = 5;
int a[N] = { 6, 5, 8, 4, 2, 7, 1, 3 };
main() {
SWAP(x,y);
SWAP(a[1],a[2]);
}
Notice how labels are generated for the variables, "x", "y", and "a", and the function "main()". However, there is no label generated for the macro "SWAP". Examine the generated code to see if you can find the code fragments associated with the two SWAP instances.
Checkoff 2. Write a C pre-processor macro named POW2(X) that returns 2 raised to the power of the positive integer argument X. Use the following "main()" function to test it.
main() {
int x, y, z;
x = POW2(0);
y = POW2(10);
z = POW2(7) - POW2(3);
}
Recall that the C pre-processor marcos essentially perform text substitution. Thus, they should finally resolve to valid C statements. (Hint: Try using the C left-shift operator.)
Finding the minimum value in an array
In this example we examine several of the most frequently used C-statements and the assembly code generated by them. The function "min()" takes two arguments. The first, is the address of an "array" and the second is the "size" of the array in words. The function scans the array searching for the smallest value and returns its index. Compile the C-program shown below and load it into the miniMIPS simulator.
#define N 8
int a[N] = { 6, 5, 8, 4, 2, 7, 1, 3 };
int min(int array[], int size) {
int i;
int minIndex = 0;
int minValue = array[0];
for (i = 1; i < size; i++)
if (array[i] < minValue) {
minValue = array[i];
minIndex = i;
}
return minIndex;
}
main() {
return min(a,N);
}
Scan through the generated assembly code to examine the code generated for the "for-loop" and the "if" statements. Also notice how the "array" and "size" arguments to min() are passed in the registers $4 and $5, and min()'s return value is placed in $2. This is an example of the procedure linking convention discussed in class.
Checkoff 3. Write a new C function int sum(int array[], int size) that returns the sum of all the values in the given array. Compile it, run it, and verify that it works. Then write down the C code for your sum() implementation.
Selection Sort
Selection sort is a classic sorting algorithm. It operates iteratively by enforcing the invariant that the element in position i must be smaller than all elements in positions i+n after i iterations. For example, after the first iteration, the element in the first position is less than all later elements. Another way to state this is that the algorithm puts the smallest element first, then it puts the smallest of the remaining elements second, then it puts the smallest of the remaining element third, etc. The outcome is a sorted array.
The implementation shown below, specifies the position of the next minimum element using a pointer variable 'p', which is initialized to the address of 'a'. In subsequent iterations, p is set to point to subsequent elements of 'a' using the ++ operator.
#define N 8
#define SWAP(X,Y) {register int t = X; X = Y; Y = t;}
int a[N] = { 6, 5, 8, 4, 2, 7, 1, 3 };
int min(int array[], int size) {
int i;
int minIndex = 0;
int minValue = array[0];
for (i = 1; i < size; i++)
if (array[i] < minValue) {
minValue = array[i];
minIndex = i;
}
return minIndex;
}
main() {
int i, j;
int *p = a;
for (i = 0; i < N-1; i++) {
j = min(p,N-i);
SWAP(a[i],a[i+j]);
p++;
}
}
Set a breakpoint at the "halt:" label, and then run the program. You can verify that the array "a" is sorted using a memory dump. Simply enter any address or label (in this case enter "a") into the textbox to the right of the "Memory Dump" button and then press [Memory Dump]. This should popup a dialog showing the contents of memory locations following the specified address.
Note that the "array" argument to "min()" is an address of a memory location. This illustrates an important use of pointers seen in many programming languages. Arguments can either be a pointer to a variable in memory, which then can be accessed and modified by the called function (call-by-reference), or a argument can be a copy of the contents of a variable, which can be used by the calling function, but changes to it are invisible to the calling function (call-by-value). In C arrays and composite data structures are passed using call-by-reference, while built-in data types (char, short, int, float, and double) are passed using call-by-value. However, it is possible to specfiy call-by-reference for a built-in type using the "address-of" operator (e.x. foo(&x);) and declaring the corresponding function argument as a pointer type (e.x. int foo(int *x) { ... }).
Checkoff 4. How many iterations (i.e. executions of the for-loop body in "min()") does selection sort require to sort a list of 12 elements? Find the MIPS instruction that implements 'p++' and write it down in your report.
Quick Sort
An alternative to selection sort is the faster "quick sort" algorithm. Rather than searching for the smallest remaining value in each pass, quick sort chooses a "pivot" value and partitions the array values according to those that are above and below the pivot value. It then "quick sorts" the two partitions. It continues in this fashion until the partition is only one value, in which case there is nothing to do, so it returns. The version of "quick sort" shown below operates in place. This means that after partitioning, lower values are located at array entries with smaller indices than the pivot value and higher values are at higher indices. Compile and load into the simulator the code shown below.
#define N 8
#define SWAP(X,Y) {register int t = X; X = Y; Y = t;}
int a[N] = { 6, 5, 8, 4, 2, 7, 1, 3 };
void quicksort(int array[], int low, int high) {
int pivot,i,j,k;
if (low < high) {
k = (low+high)>>1;
SWAP(array[low],array[k]);
pivot = array[low];
i = low+1;
j = high;
while (i <= j) {
while ((i <= high) && (array[i] <= pivot))
i++;
while ((j >= low) && (array[j] > pivot))
j--;
if (i < j)
SWAP(array[i],array[j]);
}
SWAP(array[low],array[j]);
quicksort(array, low, j-1);
quicksort(array, j+1, high);
}
}
main() {
quicksort(a,0,N-1);
}
Step through the first call to quicksort. Notice how, after the second SWAP() macro finishes executing, the array contents are partitioned.
Checkoff 5. How many times, and with what arguments, is the function quicksort() called in the program given?
Checkoff
Write down the answers to the 5 checkoffs and turn them in to the TA.
Note: Next week there will be a Quiz during the normal lab meeting time.