CS 61C Spring 1995 Midterm 1 solutions 1. Arithmetic. value sign-magnitude ones complement twos complement 37 00100101 00100101 00100101 -37 10100101 11011010 11011011 Note that all three answers in the first row are equal; positive numbers look the same in all these representations. Taking the entire first row as one answer, there were four answers, worth 1/2 point each, rounded down. Exception: If you got the first row wrong, and your second-row answers were consistent with your first-row answer, you got credit for the second row (and therefore one point out of two). 2. LW vs LA a[3] = x translates to LW $8, x LA $9, a sw $8, 12($9) LW loads data from memory, so we get the value stored at location x. LA loads the address -- from the instruction itself -- so we get the address of the beginning of the array a, which is then used in the address calculation 12($9) in the next instruction. Scoring: One point for each blank. 3. Inventing new instructions. Many people got this wrong by misreading the question. You answered a different question: "Without changing the architecture, can we implement these assembler instructions in a single actual MIPS hardware instruction?" The actual question was this: "Suppose we want to CHANGE THE HARDWARE by adding new instructions. Can we implement a single hardware instruction to do each of these assembler instructions?" (And if so, would it be an R-format or an I-format instruction?) (a) BLOCKZERO from, to This could not be done in one instruction, because an I-format instruction only allows for one memory address. Some people said "it could be done in r-format if you put the addresses in registers" but this misses two points: (1) That could be said about anything! We could always have a register that points to a huge block of memory containing a zillion sub-arguments! (2) If this were going to be r-format, then the assembler instruction would not include two addresses, as the problem stated. It would instead include two register numbers. (b) QUOREM result, dividend, divisor This can be done as an R-format instruction. It's true that four registers are involved, but since the two result registers are constrained to be SEQUENTIAL, only one of them need be included in the instruction itself. Otherwise the problem would have said QUOREM result1, result2, dividend, divisor and for that the answer would be "more than one instruction." (c) PUSH stack, value This is a typical I-format instruction, with one register operand (stack) and one memory operand (value). Some people said "you can't fit a 32-bit address in the instruction and still have room for an opcode" but this could equally be said about any memory load/store instruction! By this reasoning you can't have a LW instruction either. Scoring: One point each. Note: For most of these instructions there are reasons (having to do with pipelining, which we'll talk about very soon) why it might be a BAD IDEA to implement them in hardware. But that isn't what the question was asking. The question was merely, can the instruction fit into one of the existing instruction formats. Questions 4-8, on translating C pointer references: We were surprised at the amount of trouble you had understanding the C code. We didn't intend this to be a test of your knowledge of C; we just took as given that you knew C! The hard part was supposed to be understanding how the (known by you) behavior of C could be implemented on a machine. (Arrays and pointers work the same in C and C++, by the way.) 4. How many bytes of stack for a? The declaration is int a[10]; This means that we are declaring an array of ten integers, which means that 40 bytes of stack space are needed. Perhaps some of you were confused by the fact that when an array is used AS AN ARGUMENT to a procedure, only a pointer is actually passed on the stack. (That is, arrays are call-by-reference.) But here we aren't talking about an argument; we're talking about a local variable belonging to the procedure foo. If foo doesn't allocate the space, who does?? Scoring: One point, for the right answer. 5. How many bytes of stack for p? The answer we were looking for was 4 bytes, because the declaration says int *p = {4, 5, 6}; and a pointer is four bytes, no matter what it points to! Unfortunately the declaration above is illegal. You can initialize a char pointer, by saying, e.g., char *cp = "hello"; but you can't initialize other kinds of pointers with explicit arrays. The crucial point, which you should understand anyway, is that a pointer takes four bytes, period. If the pointer points to something, then that something has to be allocated somewhere else. In the cp case, the string "hello" would *not* be on the stack; it would be allocated in the data segment along with any other constant strings in the program. But since we got it wrong, too, we'll give everyone another point. (The extra point isn't included in what glookup says -- don't complain about it!) 6. Translate p=a; (C) addi $8, $sp, 24 sw $8, 8($sp) The crucial point here is that "a" is the name of an array, so it's an abbreviation for &a[0] -- that is, the address of the beginning of the array. Since p is a pointer, it's appropriate to assign it a value that's the address of an integer. We don't have to load anything from memory to find out the address of a[0]; we already know that it's at 24($sp). So we add 24 to the value in $sp, and the result is the value we want to store into p. Answer (a), which says LW $8, 24($sp), would be a translation of p=a[0], which would be an illegal instruction because it assigns an integer value to a pointer variable. Answer (b), which uses LB and SB, would only make sense if we were dealing with character variables. Scoring: 2 points, all or nothing. 7. Translate p[0]=a[1]; (B) lw $8, 28($sp) # $8 gets a[1] lw $9, 8($sp) # $9 gets &p[0] sw $8, 0($9) # p[0] gets a[1] Some people thought this would be illegal, because p is a pointer and can't be subscripted. But, in general in C, x[i] is just an abbreviation for *(x+i). Of course this instruction will work only if p actually points to something! But if so, then p[0] is a perfectly legal notation. (A) stores into 8($sp), so it changes the value of p. This would implement p=a[1], which is an illegal assignment of an integer value to a pointer variable. (C) also stores into 8($sp), but this time it's storing an address, so it implements p=&a[1]. This is a legal instruction, but not the one we wanted. Scoring: 2 points, all or nothing. 8. Matching translations. This was where we were most surprised at people's ignorance of C/C++ notation. (We recommend that you get a copy of Kernighan & Ritchie for reference.) In particular, many people don't understand the difference between p++ and ++p, or the difference between either of those and p+1. So... p+1 an expression whose value is the address after the one p points to. This expression has no side effects. ++p this expression CHANGES THE VALUE IN P to point to one location after its previous value (like saying p=p+1) and returns that new value of p. p++ this expression CHANGES THE VALUE IN P as above, but returns the OLD value of p. So... ch = *cp++; This means the same as ch = *cp; cp = cp+1; so it's translated by (A) lb $16, 0($4) # ch = *cp; addi $4, $4, 1 # cp = cp+1; ch = (*cp)++; This means the same as ch = *cp; *cp = *cp+1; so it's translated by (F) lb $16, 0($4) # ch = *cp; addi $8, $16, 1 # $8 = ch+1; /* which is *cp + 1 */ sb $8, 0($4) # *cp = ch+1; ch = (*cp)+1; This doesn't modify cp or *cp, so it's translated by (C) lb $16, 0($4) # ch = *cp; addi $16, $16, 1 # ch = ch+1; ch = *(cp+1); This also doesn't modify cp or *cp, but uses a temp pointer: (B) addi $8, $4, 1 # $8 = cp+1; lb $16, 0($8) # ch = *($8); Note that it could also be translated more simply: lb $16, 1($4) # ch = *(cp+1); ch = *++cp; This means the same as cp = cp+1; ch = *cp; so it's translated by (E) addi $4, $4, 1 # cp = cp+1; lb $16, 0($4) # ch = *cp; The unused answer was (D) lb $16, 0($4) addi $16, $16, 1 sb $16, 0($4) which translates ch = ++(*cp); Scoring: One point each. 9. Translate C to MIPS. The most straightforward solution, with no code optimization: foo: addiu $sp, $sp, -16 # prologue sw $31, 0($sp) sw $16, 4($sp) sw $4, 8($sp) sw $5, 12($sp) bnez $4, nonzero # if (x == 0) ... lw $4, 12($5) # y[3] jal proc move $16, $2 # a = proc(y[3]); b ret nonzero:lw $8, 12($5) # y[3] add $4, $4, $8 # x + y[3] jal proc move $16, $2 # a = proc(x + y[3]); ret: lw $8, 12($sp) # $8 = y lw $9, 8($8) # y[2] add $16, $16, $9 # a = a+y[2] ... addi $16, $16, -5 # ... -5; move $2, $16 # return a; lw $31, 0($sp) # epilogue lw $16, 4($sp) addiu $sp, $sp, 16 jr $31 This can be optimized in various ways: * There's no need to save $4, because it's not used after the call to proc. * The two branches of the IF statement can share some instructions. * (In fact, you can ignore the IF, because if x is 0, x+y[3] = y[3]!!) * It saves some fetching if you save $5 in $17 rather than on the stack. * There's no real need to keep the value of A in $16 rather than $2. Several people seem to be afraid of nonzero offsets. For example, instead of lw $4, 12($5) you said something like la $8, 12($5) # or: addi $8, $5, 12 lw $4, 0($8) This works, but is entirely unnecessary. Scoring: It's hard to give a complete list, but here are some common problems and their scores. The key idea, we thought, was understanding that calling proc might destroy the values in any registers other than $16-$23. Don't save $16 ==> at most 4 points. Don't save $31 ==> at most 3 points. Don't save $5 ==> at most 3 points. No stack at all ==> at most 2 points. Nonexistent addressing modes like lw $4, $8($5) ==> at most 3 points. No return value in $2 ==> at most 4 points. Not a procedure (starts at __start, ends with "done", etc.) ==> 0 points. Branch backwards ==> at most 5 points. Byte indexing instead of word ==> at most 5 points. By the way, there is no SUBI instruction in the MIPS architecture. ----------------------------------- If you don't like your grade, first check these solutions. If we graded your paper according to the standards shown here, and you think the standards were wrong, too bad -- we're not going to grade you differently from everyone else. If you think your paper was not graded according to these standards, bring it to Mike or Brian. We will regrade the entire exam carefully; we may find errors that we missed the first time around. :-) If you believe our solutions are incorrect, we'll be happy to discuss it, but you're probably wrong!