CS 3330: Lab/HW 4: More Y86 and HCL

This page does not represent the most current semester of this course; it is present merely as an archive.

Use the simulator distribution described in Lab 3 for this lab.

You may work with one partner in this lab/homework. If you work with a partner you should both commit to work together (conversing on a single task at a time throughout, not divide-and-conquer) through the entire assignment. You may start in a pair and then split to finish the assignment individually. Once you do some work without your partner, you must finish the assignment by yourself.

You do not need to submit anything during lab. Once you finish all parts, submit it for homework.

Write an Simulate 3 Programs

Work in directory sim/misc. You can test your programs by, e.g.,

linux> ./yas rsum.ys
linux> ./yis rsum.yo

You can also download hw4yschecker.hs into sim/misc to run more tests. The checker assumes you have only one ret per method and will fail otherwise.

linux> bash hw4yschecker.sh

You may use the simulator to see what's happening, but if you do make sure you use seq-std.hcl not seq-hw3.hcl or your stack won't work right.

Write Y86 code that simulates the following C code methods:

/* linked list element */
typedef struct ELE {
    int val;
    struct ELE *next;
} *list_ptr;

/* sum_list - Sum the elements of a linked list */
int sum_list(list_ptr ls) {
    int val = 0;
    while (ls) {
        val += ls->val;
        ls = ls->next;
    }
    return val;
}

/* rsum_list - Recursive version of sum_list */
int rsum_list(list_ptr ls) {
    if (!ls)
        return 0;
    else {
        int val = ls->val;
        int rest = rsum_list(ls->next);
        return val + rest;
    }
}

/* copy_block - Copy src to dest and return xor checksum of src */
int copy_block(int *src, int *dest, int len) {
    int result = 0;
    while (len > 0) {
        int val = *src++;
        *dest++ = val;
        result ^= val;
        len--;
    }
    return result;
}

Hint: gcc -Og -S will help to get you started…

sum.ys: Iteratively sum linked list elements

Write a Y86 program that iteratively sums the elements of a linked list. Your program should consist of some code that sets up the stack structure, invokes a function, and then halts. In this case, the function should be Y86 code for a function sum_list that is functionally equivalent to the C sum_list function. Test your program using the following three-element list:

# Sample linked list
.align 4
ele1:
    .long 0x00a
    .long ele2
ele2:
    .long 0x0b0
    .long ele3
ele3:
    .long 0xc00
    .long 0

One example of correct output:

Stopped in 31 steps at PC = 0x15.  Status 'HLT', CC Z=1 S=0 O=0
Changes to registers:
%eax:   0x00000000  0x00000cba
%ecx:   0x00000000  0x00000c00
%esp:   0x00000000  0x000000fc
%ebp:   0x00000000  0x00000100

Changes to memory:
0x00f4: 0x00000000  0x00000100
0x00f8: 0x00000000  0x00000015
0x00fc: 0x00000000  0x00000018

Addresses changed may vary...

Note: you must pass the address of the linked list to the function on the stack (push before the call). That's how functions work in C and assembly.

rsum.ys: Recursively sum linked list elements

Write a Y86 program that recursively sums the elements of a linked list. This code should be similar to the code in sum.ys, except that it should use a function rsum_list that recursively sums a list of numbers, as shown with the C function rsum_list. Test your program using the same three-element list you used for testing list.ys.

One example of correct output:

Stopped in 65 steps at PC = 0x15.  Status 'HLT', CC Z=0 S=0 O=0
Changes to registers:
%eax:   0x00000000  0x00000cba
%edx:   0x00000000  0x00000018
%esp:   0x00000000  0x000000fc
%ebp:   0x00000000  0x00000100

Addresses changed may vary, but there should be many changed (recursion does a lot with the stack).

Note: you must pass the address of the linked list to the function on the stack (push before the call). That's how functions work in C and assembly.

copy.ys: Copy a source block to a destination block

Write a program that copies a block of words from one part of memory to another (non-overlapping area) area of memory, computing the checksum (Xor) of all the words copied. Your program should consist of code that sets up a stack frame, invokes a function copy_block, and then halts. The function should be functionally equivalent to the C function copy_block. Test your program using the following three-element source and destination blocks:

.align 4
# Source block
src:
    .long 0x00a
    .long 0x0b0
    .long 0xc00
# Destination block
dest:
    .long 0x111
    .long 0x222
    .long 0x333

Key elements of correct output are:

Changes to registers:
%eax:   0x00000000  0x00000cba

Changes to memory:
0x0034: 0x00000111  0x0000000a
0x0038: 0x00000222  0x000000b0
0x003c: 0x00000333  0x00000c00

(note: the exact addresses may vary)

Note: you must pass the addresses of the two blocks and the number of elements top copy to the function on the stack (push before the call). Since we invoke it as (src, dst, num) you need to push the number, then the destination, then the source. That's how functions work in C and assembly.

Add iaddl and leave to Y86

Work in the sim/seq directory for this part.

Extend the SEQ processor to support two new instructions: iaddl (described in Homework problems 4.47 and 4.49; briefly, iaddl V, rB had opcode byte C0 and adds an immediate value to regB) and leave (described in Homework problems 4.48 and 4.50; briefly, leave is encoded as byte D0 and is equivalent to rrmovl %ebp,%esp followed by popl %ebp). To add these instructions, modify the file seq-full.hcl, which implements the version of SEQ described in the CS:APP2e textbook. In addition, it contains declarations of some constants that you will need for your solution.

You might be interested in this guide to simulator HCL signal names.

Testing

The basic testing process is

linux> make clean
linux> make VERSION=full
linux> ./ssim -t ../y86-code/asumi.yo  # tests iaddl
linux> ./ssim -t ../y86-code/asuml.yo  # tests leave

You can compare the output to the ISA simulator

linux> ../misc/yis ../y86-code/asumi.yo  # correct iaddl behavior
linux> ../misc/yis ../y86-code/asuml.yo  # correct leave behavior

If it doesn't work, using ssim in gui mode (-g) is advised to debug.

Once it seems to work, try

linux> cd ../y86-code; make testssim

That doesn't test the new instructions, just that you didn't break any of the old ones.

If that passes, try the regression tests:

linux> cd ../ptest; make SIM=../seq/ssim
linux> cd ../ptest; make SIM=../seq/ssim TFLAGS=-il

If all of that passes, you passed everything!

Submission

If you worked with a partner, both partners should submit the same files and the first line of each file must contain the computing IDs of both partners.

Submit in the usual place.