Exam 2 Review

The exam will consist of short-answer questions and writing your own code. A significant portion will consist of writing code (more than half the points), so you should be prepared to do this.

The review below, in addition to Lab 4, Lab 5, and Lab 6, are all fair game for the exam. For the labs, this includes both code you've written and questions you've answered. Between this review and the aforementioned three labs, this information is intended to be comprehensive; there will be no material on the exam which isn't touched by either the labs or this review.

If you're pushed for time, my personal recommendation is to spend the majority of your time studying what you wrote for your labs, both code and questions. You'll find the review below to be largely (though not entirely) redundant with that information.

Memory-Intensive MIPS Assembly

Translate the following C code to assembly. The variables used refer to registers which should be used. You may assume that any registers used without initialization have already been initialized for you. You do not need to worry about saving or restoring registers. If you need additional registers than what are used below, use registers $t0 - $t9. You may assume that the C types int, unsigned int, and int* are each 32 bits long.
```
int s0 = 0;
unsigned int s1;
// `s1` and `s2` are of type `unsigned int`
// `s3` is of type `int*`
for (s1 = 0; s1 < s2; s1++) {
  s0 = s0 + s3[s1];
}
```
```
  move $s0, $zero
  move $s1, $zero
loop:
  slt $t0, $s1, $s2
  beq $t0, $zero, after_loop
  sll $t1, $s1, 2
  addu $t2, $t1, $s3
  lw $t3, 0($t2)
  addu $s0, $s0, $t3
  addiu $s1, $s1, 1
  j loop
after_loop:
```
Translate the following C code to assembly. The variables used refer to registers which should be used. You may assume that any registers used without initialization have already been initialized for you. You do not need to worry about saving or restoring registers. If you need additional registers than what are used below, use registers $t0 - $t9. You may assume that the C types int, unsigned int, and int* are each 32 bits long. You may assume that array was declared globally, and it is an array of unsigned int.
```
array[0] = 0;
array[1] = 1;  
unsigned int s0;
for (s0 = 2; s0 <= s1; s0++) {
  array[s0] = array[s0 - 1] + array[s0 - 2];
}
s2 = array[s1];
```
```
  la $t0, array
  sw $zero, 0($t0)
  li $t1, 1
  sw $t1, 4($t0)
  li $s0, 2
loop:
  slt $t1, $s1, $s0
  bne $t1, $zero, after_loop
  sll $t2, $s0, 2
  addu $t3, $t0, $t2
  lw $t4, -4($t3)
  lw $t5, -8($t3)
  addu $t6, $t4, $t5
  sw $t6, 0($t3)
  addiu $s0, $s0, 1
  j loop
after_loop:
  sll $t1, $s1, 2
  addu $t2, $t1, $t0
  lw $s2, 0($t2)
```
Consider the assembly code below, which is intended to iterate through each element of myArray (which is declared elsewhere, and is of length 10), and do something with each element:
```
  # initialize registers
  move $t0, $zero
  li $t1, 10
loop:
  # check that we're still in the loop
  slt $t2, $t0, $t1
  beq $t2, $zero, after_loop

  # load myArray[$t0] into $t5
  la $t3, myArray
  addu $t4, $t3, $t2
  lw  $t5, 0($t4)

  # do something with myArray[$t0], AKA $t5.
  # this has been omitted

  # increment counter and go back to the top
  addiu $t0, $t0, 1
  j loop
after_loop:
  # this is where code after the loop goes  
```
The code above has a bug in it which will cause it not to iterate through the loop correctly. Specifically, $t3 won't always hold the value of myArray[$t3]. Two questions follow:
1. What is wrong with the above code? - it indexes into myArray[$t2] as bytes. This is broken for two reasons:
  1. $t2 is either a 0 or a 1, as it is derived from the above slt instruction. This has no relation to $t0, which is what we want.
  2. This does not take into account the fact that each element of myArray is four bytes long (each element is a 32 bit word). As such, this will access portions between elements, and treat these portions as distinct words.
2. A single instruction can be added to this code somewhere which will fix the bug. Which instruction is it, and where does it need to be placed? - sll $t2, $t0, 2 needs to be placed immediately after la $t3, myArray.
This isn't a question, but the following example files from the course webpage are all fair game:

MIPS Calling Convention

You should be familiar with the rules in the MIPS calling convention documentation. The following questions all indirectly relate to that document.

What's wrong with the MIPS code snippet below, with respect to the MIPS calling convention?
```
li $t0, 10         # save 10 into $t0
jal foo            # call foo
add $t1, $t0, $t0  # 10 + 10 = 20
```
The above code assumes that the foo function does not change the value of $t0, which it assumes will be 10 after the call. According to the MIPS calling convention, register $t0 isn't preserved across a call, so there is no guarantee that the value of $t0 will continue to be 10 after a call is performed.
Consider the C code below:
```
int add2(int x, int y) {
  return x + y;
}
```
Answer the following questions, which are all related to how the above code behaves with respect to the MIPS calling convention:
1. When add2 is called, in what registers will the values of x and y be initially placed? - $a0 and $a1, respectively
2. When add2 returns, in what register will its return value (x + y) be placed? - $v0
The function bar below is implemented in MIPS assembly, which takes two parameters, which we'll name x and y, respectively. The function is supposed to return the result of (x * y) - (x + y). However, there is a bug in the function, with respect to the MIPS calling convention. What's wrong with the code, and how could it be fixed?
```
bar:
  mult $a0, $a1
  mflo $s0
  add  $s1, $a0, $a1
  sub  $v0, $s0, $s1
  jr $ra
```
The above code uses registers $s0 and $s1, which are supposed to be preserved across a call according to the MIPS calling convention. As such, in order to safely use $s0 and $s1, the code needs to first save their values on the stack, and then later restore their values from the stack just before returning from bar. However, the code above does not do this, so it is buggy. The solution is to either save and restore registers $s0 and $s1 as described, or use registers $t0 and $t1 instead, which do not need to be preserved across calls.
Consider the function first, below, which calls another function second. second doesn't take any parameters, and it doesn't return anything. There is a bug in the code below. What's wrong with the code, and how could it be fixed?
```
first:
  jal second
  jr $ra
```
When the jal instruction is used, it will overwrite the value stored in $ra with the return address for the call to second. In doing so, it will overwrite the return address needed for the initial call to first. As such, when first goes to execute jr $ra, instead of jumping to the caller of first, it will jump to where second returned to, which in this case happens to be jr $ra. This will continue for infinity. The solution is to save $ra on the stack before making the call to second, and then restore the value saved on the stack to $ra once the call to second returns.
Consider the function third, below, which calls another function fourth. fourth doesn't take any parameters, and it doesn't return anything. There is a bug in the code below. What's wrong with the code, and how could it be fixed?
```
third:
  addiu $sp, $sp, -4
  sw $ra, 0($sp)
  jal fourth
  lw $ra, 0($sp)
  jr $ra
```
The above code fails to deallocate space on the stack after $ra is restored. As such, when third returns, the $sp register will hold a different value than expected. The offsets of all data saved on the stack are now off by 4 (the value $sp is off by), and so anything trying to restore values from the stack will restore the wrong values. This can be easily fixed by adding a addiu $sp, $sp, 4 instruction immediately before the jr $ra instruction.
Say that the value of $t0 needs to be maintained through a call, but we're constrained in that we're not allowed to store $t0's value in a preserved register (e.g., $s0 - $s7). This can't be done directly, as the MIPS calling convention allows the caller to clobber $t0. However, there is still a way to save the value of $t0 somewhere where it can survive the call, without needing to use a preserved register. Where can $t0 be saved? How can this be done, specifically with valid MIPS assembly which obeys the MIPS calling convention?
The value of $t0 can be placed on the stack just before the call, and then restored from the stack immediately after the call. For example, say we are calling a function named func, and we need to save $t0 through the call. This can be done like so:
```
addiu $sp, $sp, -4
sw $t0, 0($sp)
jal func
lw $t0, 0($sp)
addiu $sp, $sp, 4
```
This isn't a question, but the following example files from the course webpage are all fair game:
You will not be asked about tail-recursion.

Basic Circuit Design

What component is shown below?

An OR gate.
What component is shown below?

An AND gate.
What component is shown below?

A NOT gate.
What component is shown below?

An XOR gate.
Draw the circuit corresponding to the following sum-of-products equation, where !A refers to the negation of variable A, and so on:
```
R = !A!B + AB
```
Consider the following sum-of-products equation:
```
R = !ABC + ABC + A!B!C
```
Using the above equation, do the following:
- Write it as a truth table:
- Simplify it using boolean algebra:
- Simplify it using a Karnaugh map:
  
  R = A!B!C + BC