Instructions

Your solution should be typed and printed with plenty of spacing within and between problems in black ink on single-sided, otherwise blank paper that is stapled (assuming it is more than one page, which it should be).

Read the entire problem set thoroughly before beginning to write your solutions.

For some problems, it may be helpful to write small C programs.

For some problems, it may be helpful to use SPIM, the MIPS simulator. You can download SPIM here. Documentation for SPIM can be found on its Web site and also in Appendix A (Section A.9) of Patterson and Hennessy.

Appendix A (Section A.10) also contains a reference manual for MIPS that has a complete list of instructions and pseudoinstructions.

If you are asked to provide MIPS instructions (assembly or machine) for any problem below, use only the instructions we have covered in class, unless it is explicitly stated otherwise.

1. Do exercise 2.32 in PH, p. 151.


2. Do exercise 2.37 in PH, p. 152, but only for the following four cases:

     move  $t1, $t2
     clear $t0
     li    $t1, small
     ble   $t3, $t5, L
   



3. Show a minimal sequence of MIPS assembly instructions (not pseudoinstructions) to place the hexadecimal value 64012c into register $s5, using the decimal representation of any immediate values. For each assembly instruction, show the corresponding machine code in hexadecimal notation.


4. Translate the following MIPS assembly into MIPS machine code:

     Start:  andi $t9, $s4, 3
     Loop:   beq  $t9, $zero, End
             addi $t9, $t9, 5
             j    Loop
     End:    sll  $zero, $zero, $zero
   

   Write each machine code both as a sequence of thirty-two bits (eight groups of four bits, with spaces between, please) and in hexadecimal notation. Assume that the instructions are stored consecutively beginning at hexadecimal memory address 0x00fafafa.


5. (This question is based on exercise 2.14 in PH, cd-section "For More Practice.") Consider the following C leaf procedure and a simple translation into MIPS:

     int foo(int n) {                  foo:   ori  $v0, $zero, 0    
       int s = 0;                             ori  $t0, $zero, 0    
       int i;                          Loop:  slt  $t1, $t0, $a0    
       for (i = 0; i < n; i++) {              beq  $t1, $zero, Exit 
         s += i;                              add  $v0, $v0, $t0    
       }                                      addi $t0, $t0, 1          
       return s;                              j    Loop         
     }                                 Exit:  jr   $ra
   

   1. If foo is called when $a0 contains the value 50, how many instructions are executed in the above MIPS code?
   
   
   2. Write an "optimized" version of the MIPS assembly for foo in which only one jump or branch is executed each time through the loop.
   
   
   3. If your optimized version of foo is called when $a0 contains the value 50, how many instructions are executed?
   
   
   4. What does your solution illustrate about the concept of "optimization"?


6. Do exercise 2.52 in PH, cd-section "In More Depth: Instruction Set Styles."


7. Consider the following MIPS procedure:

   mystery:
           addi $sp, $sp, -4
   	sw   $ra, 0($sp)
   	bne  $a0, $zero, Else
   	addi $v0, $zero, 1
   	addi $sp, $sp, 4
   	jr   $ra
   Else:
   	addi $a0, $a0, -1
   	jal  mystery
   	sll  $t0, $v0, 1
   	add  $v0, $t0, $v0
   	lw   $ra, 0($sp)
   	addi $sp, $sp, 4
   	jr   $ra
   

   1. If the following fragment is executed, what value will result in register $s7?

        ori $a0, $zero, 2
        jal mystery
        ori $s7, $v0, 0 
      

   
   
   2. Translate the mystery procedure into equivalent (but not necessarily literal, line-by-line) C code.
   
   
   3. In a clear and concise sentence, state what mystery computes.


8. Consider the following C function:

     void wow(char *s) {
       int n = strlen(s);
       int i;
       for(i = 0; i < n; i++) {
          s[i] &= 0xdf;
       }
     } 
   

   1. In a clear and concise sentence explain what the wow function accomplishes and of what feature of ASCII it takes advantage.
   
   
   2. Translate wow to MIPS assembly language, assuming that strlen exists as a library routine and so that wow is not a leaf procedure. Indicate via comments which C variables correspond to which MIPS registers.


9. Consider the following C function:

     int bfl(char *s) {
       char *p;
   
       for (p = s; *p; p++)
         ;
   
       if (p != s) {
         p--;
       }
   
       /** HELLO **/    
   
       while (p > s && *p == *s) {
         p--;
         s++;
       }
   
       return p <= s;
     } 
   

   1. What does the for loop accomplish? In particular, to what does p point at the place in the code marked by the comment HELLO?
   
   
   2. In a clear and concise sentence or two, explain what, given its input, the bfl function returns?



10. Consider the "load address" pseudoinstruction, denoted by la and used as in:

      la   $s0, HERE
    

    which take the memory address that the assembler computes for symbolic address HERE and stores it in register $s0. The assembler translates this to one or (usually) two instructions that use ori and (usually) lui to place the address in the register. This is a powerful feature of the assembler since otherwise it would be extremely difficult to know the exact address where a symbolically-addressed piece of data would be stored.

    Consider the following MIPS assembly:

      strange:
              addi $v0, $zero, 0
      Special:
              lw   $t0, 0($a0)
              slt  $t1, $t0, $zero
              bne  $t1, $zero, Exit
              add  $v0, $v0, $t0
              la   $t2, Special
              lw   $t3, 0($t2)
              addi $t3, $t3, 4
              sw   $t3, 0($t2)
              j    special
      Exit:
              jr   $ra
    

    Assume that the code represents a leaf procedure that takes one argument, $a0, which represents the address of an array of integers.
    1. If the array consists of the following elements:

         2, 5, 1, -4, 6, 3
       

       what does the procedure return in $v0?
    
    
    2. In a concise sentence or two, what does the procedure compute?
    
    
    3. What important principle does this code illustrate? Explain.