Assignment 4: Writing Y86 Programs

Due: Thursday April 21st, 11:59PM

Introduction

For this assignment you will write some Y86-64 programs and become familiar with the Y86-64 tools.

Logistics

You will work on this assignment alone. Any clarifications and revisions to the assignment will be posted to the class website.

You will continue working in the archlab code directory, which you downloaded for the lab assignment.

Y86-Programs

You will be working in directory archlab/misc for this assignment. Your task is to write and simulate three Y86-64 programs. The required behavior of these programs is defined by the example C functions in examples.c. Be sure to put your name in a comment at the beginning of each program. You can test your programs by first assembling them with the program yas and then running them with the instruction set simulator yis.

In all of your Y86-64 functions, you must follow the x86-64 conventions for passing function arguments, using registers, and using the stack. This includes saving and restoring any callee-save registers (%rbx, %rbp, %r12, %r13, and %r14) that you use.

sum.ys: Iteratively sum linked list elements

Write a Y86-64 program sum.ys that iteratively sums the elements of a linked list. Your program should consist code that sets up the stack structure, invokes a function, and then halts. For this program, we have provided starter code that does this for you. You should implement the Y86-64 code for a function sum_list that is functionally equivalent to the C sum_list function shown below.

/* linked list element */
struct ll_node {
    long val;
    struct ll_node *next;
};

/* sum_list - Sum the elements of a linked list */
long sum_list(struct ll_node *lst) {
    long val = 0;
    while (lst) {
        val += lst->val;
        lst = lst->next;
    }
    return val;
}

Test your program using the following three-element list:

# Linked List
    .align 8
ele1:
    .quad 0x00a
    .quad ele2

    .pos 48
ele2:
    .quad 0x0b0
    .quad ele3

    .pos 64
ele3:
    .quad 0xc00
    .quad 0

rsum.ys: Recursively sum linked list elements

Write a Y86-64 program rsum.ys 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 alist of numbers, as shown with the C function rsum_list shown below. Test your program using the same three-element list you used for testing list.ys.

/* rsum_list - Recursive version of sum_list */
long rsum_list(struct ll_node *lst) {
    long val;  // value for the node
    long rest; // rest of the list

    if (!lst) {
        return 0;
    }
    else {
        val = lst->val;
        rest = rsum_list(lst->next);
        return val + rest;
    }
}

Note: when implementing this recursive function, pay special attention to callee saved registers. I recommend looking at the X86-64 assembly code for this function (shown below) to get a sense of the overall structure.

rsum_list:
        testq   %rdi, %rdi
        jne     .L8
        movl    $0, %eax
        ret
.L8:
        pushq   %rbx
        movq    (%rdi), %rbx
        movq    8(%rdi), %rdi
        call    rsum_list
        addq    %rbx, %rax
        popq    %rbx
        ret

Notice how %rbx (which holds val) is used before and after the call to rsum_list. %rbx is a callee saved register so its value must not be changed by the call to rsum_list. To preserve the value of %rbx, the old value of %rbx is first pushed on the stack, and then restored by popping it off the stack before the return.

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

Write a program copy.ys that copies a block of words from one part of memory to another (non-overlapping) 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 the function copy_block, and then halts. The function should be functionally equivalent to the C function copy_block shown below.

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

Test your program using the following three-element source and destination blocks:

.align 8
# Source block
src:
    .quad 0x00a
    .quad 0x0b0
    .quad 0xc00

# Destination block
dest:
    .quad 0x111
    .quad 0x222
    .quad 0x333

Evaluation

Each solution program will be evaluated for correctness, including proper handling of the stack and registers, as well as functional equivalence with the example C functions in examples.c.

The programs sum.ys and rsum.ys will be considered correct if I do not spot any errors in them, and their respective sum_list and rsum_list functions return the sum 0xcba in register %rax.

The program copy.ys will be considered correct if I do not spot any errors in them, and the copy block function returns the sum 0xcba in register %rax, copies the three 64-bit values 0x00a, 0x0b0, and 0xc00 to the 24 bytes beginning at address dest, and does not corrupt other memory locations.

Submitting your work

Submit following files to Assignment 4 in Gradescope

Make sure you have included your name in a comment at the top of each of your files.

You may submit as many times as you like. I will only look at the latest submission for grading.