CSci 2021 (010) Spring 2020 Midterm 2 solutions notes

The correct answers for multiple choice questions and grading comments are available via Canvas. This document gives explanations about how the questions were answered.

Question “0” (shows up as 1)

These identifying questions did not affect your grade, even if Canvas marked them as “wrong”.

Question “1” (shows up as 2-9)

Each of these loops does something like adding together all the numbers in a range of integers.

These eight different loops differed in three different aspects:

• Whether the loop was a “while” loop or a “do-while” loop. This makes a difference if the range would have otherwise been empty, because a while loop will return 0 for an empty range, while a do-while loop will always include a in the total even if the range should be empty.
• Whether the integers are signed or unsigned. This doesn’t affect the compilation of either “i++” or “total += i”, because addition is the same operation on signed or unsigned integers. But it does affect the meaning of the comparison between i and b.
• Whether the upper-bound b is included as part of the range or not.

The naming of the C functions represented the above differences:

• First digit: 0 for a while loop, 1 for a do-while loop
• Second digit: 0 for unsigned, 1 for signed
• Third digit: 0 for b included in range, 1 for b not included

Here’s how the three differences showed up in the assembly language functions:

• A do-while loop has a simpler structure with only one label and conditional jump. The code before the loop falls into the loop body, and then after the loop body there is a conditional jump that jumps back to the beginning for the loop (L2) if the loop is not finished yet. For a while loop the condition has to be executed before the first execution of the body, and in these examples this was always done by entering the loop for the first time via an unconditional jump to the condition (L2); in the while loop versions, the label for the start of the body was L3.
• The comparison instructions that use signed arithmetic use “l” and “g” for “less than” and “greater than”. The comparison instructions that use unsigned arithmetic are different and use the letters “b” and “a” for “below” and “above”.
• In all of these cases the ending condition was compiled directly the way it appeared in the C source, with a comparison between i in %edi and b in %esi (written in the reverse order according to AT&T syntax). Therefore, the versions where b was not included in the range had the condition be false when i == b, while the versions where b was included in the range had the condition be true in this case. This difference shows up in whether “e”, short for “or equal”, appears in the conditional jump instruction.

Question “2a” (10)

Field p is at offset 0, because the first field of a structure is always at offset 0. Field p is 8 bytes long because it is a pointer, so the first place where field i can go is at offset 8, and that’s the correct location for it because it is properly aligned (8 is a multiple of 4). The first available offset after the end of field i would be 8+4=12, but field q can’t go at offset 12. Field q is an 8-byte pointer that needs to be 8-byte aligned, so its location is the first offset starting from  12 that is a multiple of 8, namely 16.

Question “2b” (11)

This function implements search in a binary search tree: similar to a function in project 1, but comparing integers instead of string prefixes. We intentionally used generic variable names, but the “i” field is the number stored in each binary search tree node, while “p” and “q” represent the left and right subtree pointers. Among the function parameters, “n” is the pointer to the root of a subtree being searched, while “x” is the number we’re looking for, and the function returns a pointer to the node containing the number if it is found, otherwise a null pointer. Here are two examples of correct C code that could have compiled to the assembly:

struct node *func(struct node *n, long x) {

   if (n == NULL) {

        return NULL;

   }

   long y = n->i;

   if (y > x) {

       return func(n->p, x);

   } else if (y != x) {

       return func(n->q, x);      

   } else {

       return n;

   }

}

struct node *func(struct node *n, long x) {

    if (!n) {

        return 0;

    }

    long y = n->i;

    if (x < y) {

        return func(n->p, x);

    } else if (x == y) {

        return n;

    } else {

        return func(n->q, x);

    }

}

Question “3” (12-21)

Here are the complete instruction descriptions once all the sticky notes were put back. These aren’t necessarily the only way these instructions could be implemented, just what one team came up with.

Common for all instructions:

icode:ifun <- M1[PC]

rA:rB <- M1[PC + 1]

• rrxchgq rA, rB. Interchange (swap) the values in registers rA and rB. The value that used to be in rA is moved to rB, and vice versa. (question 19)

• valP <- PC + 2
• valA <- R[rA]
• valB <- R[rB]
• R[rA] <- valB
• R[rB] <- valA
• PC <- valP

• rjmp *rA. Like the x86-64 "jmp *%rax", jump to the address held in register rA. (Might be used for a switch statement.) (question 20)

• valP <- PC + 2
• valA <- R[rA]
• PC <- valA

• rcall *rA. Like the x86-64 "call *%rax", call a function whose address is held in register rA. (Might be used for a function pointer.) (question 12)

• valP <- PC + 2
• valA <- R[rA]
• valB <- R[%rsp]
• valE <- valB + -8
• M8[valE] <- valP
• R[%rsp] <- valE
• PC <- valA

• incq rB. Add 1 to the value in register rB. rB = rB + 1. (question 16)

• valP <- PC + 2
• valB <- R[rB]
• valE <- valB + 1
• R[rB] <- valE
• PC <- valP

• decq rB. Subtract 1 from the value in register rB. rB = rB - 1. (question 15)

• valP <- PC + 2
• valB <- R[rB]
• valE <- valB + -1
• R[rB] <- valE
• PC <- valP

• negq rB. Unary negation: replace the value in rB with its negative. rB = -rB. (question 18)

• valP <- PC + 2
• valB <- R[rB]
• valE <- 0 - valB
• R[rB] <- valE
• PC <- valP

• leaq D(rB), rA. Load effective address. Compute D + rB, and store the result in rA. (question 13). This instruction is similar to iaddq from the lab, except that it has a separate destination register.

• valP <- PC + 10
• valC <- M8[PC + 2]
• valB <- R[rB]
• valE <- valC + valB
• R[rB] <- valE
• PC <- valP

• shlq rB. Left shift by 1. rB = rB << 1. (question 14). The Y86-64 ALU doesn’t have a shifting operation, but shifting left by one is the same as doubling or adding a number to itself.

• valP <- PC + 2
• valB <- R[rB]
• valE <- valB + valB
• R[rB] <- valE
• PC <- valP

• immovq C, (rB). Move immediate value to memory. Copy the 64-bit constant value C into the memory location pointed to by rB. (question 17)

• valP <- PC + 10
• valC <- M8[PC + 2]
• valB <- R[rB]
• valE <- valB + 0
• M[valE] <- valC
• PC <- valP

• setCCq rB. Set based on condition. If the condition is true, set rB to 1, otherwise set it to 0. (question 21)

• valP <- PC + 2
• valE <- 0 + (Cnd ? 1 : 0)
• R[rB] <- valE
• PC <- valP

Notice that “PC <- valA” is used in both rjmp and in rcall. We considered “rjmp” to be the best answer for question 20 because question 12 could only have been rcall (since call but not jump pushes a value on the stack), and the instructions asked you to use each instruction once. But we gave full credit for rcall as an answer for question 20 as well.

Question “4” (22)

The “essay” question at the end didn’t affect your grade, but we did read all of your comments. We will avoid test designs that require so much scrolling in the future.