CS224-Lab 3 Relatively Big MIPS Assembly Language Programming Machine Instruction Generation Solved

Part 1 Code generation for symbolic and pseudo machine instructions. Learning the principles of recursive programming and the implementation of dynamic link list data structure by program analysis  in MIPS assembly language.

Part 2  (More experience with linked lists and recursive programming.



 

Part 1. Preliminary Work / Preliminary Design Report 

You have to provide a neat presentation prepared by Word or a word processor with similar output quality. At the top of the paper on left provide the following information and staple all papers. In this part provide the program listings with proper identification. Please make sure that this info is there for proper grading of your work, otherwise some points will be taken off.

 

1.    Generating machine instructions  
Give the object code in hexadecimal for the instructions 1 to 6. The beginning positions of text and data are provide below after the code segment.

        again:           add        $t0, $t0, $t1

                              add        $t0, $t0, $t1

                              add        $t0, $t0, $t1

                              add        $t0, $t0, $t1

                              beq        $t0, $t1, next     # inst. no. 1

                              bne        $t0, $t1, again   # inst. no. 2

                              add        $t0, $t0, $t1

                              add        $t0, $t0, $t1

        next:             j              again                    # inst. no. 3

                               la            $t0, array            # inst. no. 4

                              lw           $t1, array            # inst. no. 5

                              bge        $t1, $t2, next     # inst. no. 6

                              ...

                              .data

                              .space   7

                              .align     2             # align: an assembler directive, see the Mars help menu or try and learn.

        array:            .word    10, 20, 30

               

        Assume that the label again is located at the memory location 00 40 01 8016. 

        Assume that the data segment starts at the memory location 10 01 00 8016.  

        For the pseudo instructions first provide the symbolic machine instructions to be generated.

 

2.    recursiveMultiplication Write a recursive MIPS subprogram that performs multiplication of two positive numbers by successive additions. Error check is optional. For recursiveMultiplication and recursivesummation provide a simple user interface to test them under the same main program..

 

3.    recursiveSummation Write a recursive MIPS subprograms that finds the summation of numbers from 1 to N. Error check is optional. 

 

4.    DeleteAll_x Study the linked list program provided and the linked list explanation provided below in Part 2. Delete all elements from the linked list with value x: the pointer to the linked list is passed in $a0, and the integer value of the element to be deleted is given in $a1. Return value in $v0= 0 if successful (was able to delete), -1 if not. In either case, the return value in $v1 contains the pointer to the head of the linked list. Are you able to return the deleted nodes back to the heap? If not include  a comment in the program to explain why. Modify the given linked list program to include this option.

 

Part 2. Lab Work: Creating Linked List Utility Routines 

Linked lists are important dynamic data structures, useful to a variety of algorithms because of their ability to grow and shrink.  Utilities libraries for linked lists are therefore useful, so that common functions can be available to users, pre-written, tested and ready to go. In this lab, you will write the utility functions defined below for linked lists, in MIPS assembly language.  Your utilities will be combined with other utility programs such as create_list and display_list, and called by a main program. [Any code other than the you are asked to write in this lab will be provided (see the Unilica folder)—you don’t need to write it.] 

In memory, the linked lists your utilities will work with are implemented as follows: each element consists of 2 parts: pointerToNext, and value. Each part is a 32-bit MIPS  word in memory. The two parts are located in successive word addresses, with the pointerToNext being first.  For example, if the byte address of the pointerToNext is 100, then the byte address of the value will be 104.  Remember, MIPS memory is byte addressable.

In the last element of the linked list, the pointerToNext has value 0, in other words it is the null pointer. This means that there is not any next element. Do not forget that the last element still has a value.

Write the following linked list utility routines. Follow MIPS programming conventions in terms of using the stack and registers. Ignore the other methods not implemented.  Modify the menu to include  the following  possibilities.

1.      Insert_end Insert an element to the linked list at end: the pointer to the linked list is passed in $a0, and the integer value of the new element to be inserted is given in $a1. This utility will request space in memory by syscall, use it to create a new element, and then insert the new element into the linked list at the end.  Upon return, the value in $v0 =0 if successful, -1 if not. In either case, the pointer to the head of the linked list should be the same as it was before the call.

2.      Delete_n (Delete an element from the linked list at position n: the pointer to the linked list is passed in $a0, and the position of the element to be deleted is given in $a1. The first element is in position 1, the second element in position 2, etc.  Return value in $v0 =0 if successful, -1 if not.  In either case, the return value in $v1 contains the pointer to the head of the linked list.

3.      Invert_List : Invert a linked list. This means that if the list contains - 10 - 20 - 30 after the call it becomes - 30 - 20 - 10. No restriction in implementation: it can be recursive or non recursive. It must return the new list head in $v0.

4.      Display_Reverse_Order_Recursively  Display the elements of the linked list in reverse order. This means that if the list contains - 10 - 20 - 30 it displays the list in the reverse order 30, 20, 10. This must be a recursive subprogram: it must call itself with jal.