CIS341, Spring 2020
Assembly Lab: Programming a Y86 Processor
Assigned: Feb. 18st, Due: Mar. 13th, 8:59PM
1 Introduction
In this lab, you will learn about the Y86 instruction set architecture and how an assembly program executes
on a sequential Y86 processor. You are allowed to make any semantics-preserving transformation to the
program, and optionally make enhancements to the sequential processor. When you have completed the lab,
you will have a keen appreciation for the interactions between code and hardware that affect the performance
of your programs.
You will be hand-coding Y86 assembly codes with the goal of either making the code size small, or making
the code run fast. You may optionally extend the Y86 instruction set architecture for the SEQ processor to
speed up your assembly program.
2 Logistics
You will work on this lab alone. Any clarifications and revisions to the assignment will be posted on
blackboard.
3 Handout Instructions
Start by copying asmlab-handout.tar to your home directory on lcs-vc-cis341.syr.edu machine.
Then untar the tarball file to unpack the assignment in the directory.
unix> cp /home/cis341-proj/asmlab-handout.tar .
unix> tar -xvf asmlab-handout.tar
unix> cd asmlab-handout
In this directory, you will find subdirectories misc, ptest, seq, src, and y86-code, and two files
Makefile and README. You may build all the available tools at this working directory.
1
unix> make clean; make
Read the README files in all directories to familiarize yourself with the assignment.
4 Y86 Programming
You will be working in directory src in this part. Your task is to write and simulate the following two Y86
programs: selectsort.ys and quicksort.ys. The required behavior of these programs is defined
by C programs in the src directory. 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 should follow the x86-64 conventions for passing function arguments,
using registers, and using the stack. This includes saving and restoring any callee-save registers that you
use. The callee-save registers are %rbx, %rbp, %r12, %r13, and %r14. %rsp is a special case where it
should be restored to the value before the call via call/ret and push/pop mechanism.
selectsort.ys: selection sort algorithm
Write a Y86-64 program selectsort.ys that performs a selection sort on an array of data. 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 (selectsort) that is functionally equivalent to the C
selectsort function in Figure 1. The directory includes a skeleton file for you to implement everything
except for the selection sort algorithm itself.
You may choose to implement selectsort without calling swap: in such case, delete swap.
quicksort.ys: quick sort algorithm
Write a Y86-64 program quicksort.ys that performs a quick sort on an array of data. 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 (quicksort) that is functionally equivalent to the C
quicksort function in Figure 2. The directory includes a skeleton file for you to implement everything
except for the quick sort algorithm itself.
quicksort must recursively call itself, and must call partition. However, you may choose to implement
quicksort without calling swap: in such case, delete swap.
Getting started
You should first examine the C code to understand what the algorithm is doing line by line. Then try
compiling to x86 assembly with various optmization levels to understand how the compiler is generating
the assembly code.
unix> gcc -Og -S .c # optimize debugging experience
2
1 #include // includes definition for int64_t
2
3 /* swap - Swaps the data pointed by the two pointer arguments */
4 void swap(int64_t *srcA, int64_t *srcB) {
5 int64_t valA, valB;
6 valA = *srcA;
7 valB = *srcB;
8 *srcA = valB;
9 *srcB = valA;
10 }
11
12 /* selectsort - Sorts an array of data using selection sort algorithm */
13 void selectsort(int64_t *arr, int64_t size) {
14 int64_t i, j, min_idx;
15 for (i=0; i