Introduction to Computer Systems

Tutorial / Laboratory 05 - procedures

Week 6

Preparation [1 mark]

1. What are some advantages of using a stack frame for passing parameters for a routine?
2. Given the following expression:

    (2*x) + ((x+3) / 7) 

   convert this into 'reverse polish' so it could be executed via a stack machine.
3. The below code uses a recursive approach for adding two integers. Errors have been added to the code. Locate and fix these errors.

   0x0100 : load #3 R0
            load #4 R1
            push R5
            push R0
            push R1
            call add
            pop R1
            pop R0
            pop R5
            store R5 result
            halt
   result : block 1
            
   ;int add(int a, int b) {
   ;   if (a == 0) {
   ;      return b;
   ;   } else {
   ;      return add(a-1,b+1);
   ;   }
   ;}
   
   ; stack frame:
   ;   return address #0
   ;   b #-1
   ;   a #-2
   ;   result #-3
   
   add: load SP #-2 R0   ; if (a == 0)
        jumpz R0 addif
        load SP #-1 R1   ; else part
        load #1 R2
        add R1 R2 R0
        sub R0 R2 R1
        push R5
        push R1
        call add
        pop R1
        pop R0
        pop R5
        store R5 #-3 SP
        return
   addif : load SP #-1 R1
           store R1 #-3 SP
           return
   

Lab [4 Marks]

1. Reserve locations in main memory for integer variables x and y. In rPeANUt implement code that does the following:

   int x = 6;
   int y;
   void main(){
      y = (2*x) + ((x+3) / 7);
   }
   

   Your implementation should first use the simple stack approach based on the reverse polish form of the expression calculated in prep question. Run the simulator from the command line and count the number of instructions executed (using -count). Now re-implement the program that does the same computation but make it execute in the least number of instructions. How do the approaches compare in terms of number of instructions executed?
2. In rPeANUt implement the "char getchar()" and "void printstring(char *str)" functions. Using these functions implement the following:

   void main() {
      while (1) {
         char c = getchar();
         if (c == 'a') {
            printf("A - apple\n");
         } else if (c == 'b'){
            printf("B - ball\n");
         } else if (c == 'c'){
            printf("C - cat\n");
         } else {
            printf("%c - ??\n", c);
         }
      }
   }
   

3. Implement, in rPeANUt, the a Fibonacci function by using the simple recursive approach. The Fibonacci function can be implemented in c as follow:

   int fib(int x) {
     if (x<2) {
       return x;
     } else {
       return fib(x-1) + fib(x-2);
     }
   }
   

   Test your implementation (e.g. fib(5) == 5, fib(7) == 13, fib(8) == 21)? What is the biggest Fibonacci number you can calculate in under about 1min of execution time?
4. (just for fun) Write some rPeANUt code that jumps to an address location that is stored within a register.