Assignment 9, due Oct 31

Solutions

Part of the homework for CS:2630, Fall 2019
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. Background: Look at machine problem 4 and the posted solution to Homework 8, problem 1. The first posted solution to problem 1 contains this code to exchange two elements of the array data:

                char * temp = data[low];
                data[low] = data[high];
                data[high] = temp;
    

    a) Write SMAL Hawk code equivalent to the above. Assume R8 contains the address of the array data, R9 contains the index low, and R10 contains the index high, and assume that R3 to R7 are available to use as needed. (0.5 points)

            MOVESL  R3,R9,2
            ADD     R3,R3,R8        ; -- address of data[low] in R3
            LOADS   R4,R3           ; char * temp = data[low] -- in R4
    
            MOVESL  R5,R10,2
            ADD     R5,R5,R8        ; -- address of data[high] in R5
            LOADS   R6,R5           ; -- data[high] in R6
            STORES  R6,R3           ; data[low] = data[high]
    
            STORES  R4,R5           ; data[high] = temp
    

    There are, of course, other solutions.

    b) The assumptions given above require that, on entry to the SMAL Hawk version of qsort, certain registers must have been saved in the activation record. Which ones? (0.5 points)

    The assumptions state that R8, R9 and R10 are being used. Our standard contract between called routine and calling routine is, quoting from Chapter 6:

    If the calling routine has anything of value in R3 to R7, it should save it before the call and restore it after return. The caller may use these registers with impunity. It is up to the called routine to return with R8 to R15 unchanged, so if these registers are needed by a subroutine, they should be saved before use and restored afterward. Any time a subroutine needs to save and restore the value in some register, it will need a local variable for this.

    This leads to the answer: The activation record must contain locations to save the values of R8, R9 and R10 on entry to the routine and from which those registers can be restored on exit. Between entry and exit, these registers may be freely used.

  2. A small problem: Write a Makefile for machine problem 4, assuming no change to the code for MP4. You can use this to test your code. (0.5 points)
    # Makefile for MP4
    # this puts the executable in link.o
    
    link.o:mp4.o
            link mp4.o
    
    mp4.o:mp4.a
            smal mp4.a
    

  3. A problem: Assume that you break your code for MP4 into two files, one containing MAIN and one containing QSORT, and assume that the version of QSORT you use takes three parameters, the pointer to the array and two array indices.

    a) What USE directives go in each of the two assembly language files? (0.5 points)

    qsort.a needs

            USE     "hawk.h"
            USE     "string.h"
    

    main.a needs

            USE     "hawk.h"
            USE     "stdio.h"
            USE     "/mnt/nfs/clasnetappvm/fs3/dwjones/2630mp4.h"
    

    b) What INT and EXT directives go in each of the two files? (0.5 points)

    qsort.a needs

            INT     QSORT
    

    main.a needs

            INT     MAIN
            EXT     QSORT
    

    It would be possible to put INT QSORT in the header file qsort.h, so long at the file main.a includes this header. This makes the solution unnecessarily complex but is perfectly acceptable.

    c) Write a Makefile for the reorganized version of MP4. (Please do not mess with your code for MP4 in doing this problem!) (0.5 points)

    The following solution assumes that we have not introduced a qsort.h header file.

    # Makefile for MP4 after proposed break-up into pieces
    # this puts the executable in link.o
    
    link.o:main.o qsort.o
            link main.o qsort.o
    
    main.o:main.a
            smal main.a
    
    qsort.o:qsort.a
            smal qsort.a
    

    To support a qsort.h header file, we need to add it to the list of dependencies for main.o. If this were C code, we'd also make qsort.o depend on it, but SMAL doesn't allow us to do that.