Projects‎ > ‎

Project 1

Project 1 is due at 11:59pm on Tuesday, February 22nd, 2011.  You will submit your solution via your svn repository.  Please create a cs315 repository and put your solution in a directory called Project1.

Basic Block Finder for MIPS

Write a MIPS assembly program (bblist.s) that will find all of the basic blocks in a MIPS program. Your program will be analyzing other MIPS programs.

A basic block is a sequence of instructions that can only be entered at the top of the basic block and exit at the bottom of the block.  That is, a basic block is a sequence of non-control instructions that can only start execution at the first instruction of the basic block; there can be no branch or jump into the middle of the basic block.  Consider the following MIPS code.

       1  # bfind.s
     2  .data
     3  string: .space 128
     4  .text
     5  .globl main
     6  main:
     7          subu    $sp, $sp, 132
     8          sw      $ra, 0($sp)        # allocate space on stack
     9          li      $v0, 8             # get string
    10          addi    $a1, $zero, 256
    11          la      $a0, string
    12          syscall
    13          jal     bfind              # find the first 'b'
    14          add     $a0, $v0, $zero    # print the index of 'b'
    15          addi    $v0, $zero, 1
    16          syscall
    17          lw      $ra, 0($sp)
    18          addu    $sp, $sp, 132
    19          jr      $ra
    20  .globl bfind
    21  bfind:
    22          add     $t2, $a0, $zero
    23          add     $t3, $zero, $zero
    24          addi    $t1, $zero, 98     # ASCII 'b'
    25  loop:   lbu     $t0, 0($t2)        # load the first byte
    26          beq     $t0, $t1, done     # if it's a 'b' we're done
    27          beq     $t0, $zero, done   # if it's a 0 we're done
    28          addi    $t3, $t3, 1
    29          addi    $t2, $t2, 1        # increment pointer
    30          j       loop               # keep looping
    31  done:
    32          add     $v0, $t3, $zero    # return the result
    33          jr      $ra

The first basic block in this code starts and line 7 and ends at line 11 (that is the instruction at line 11 is included in the basic block).  We will consider the syscall pseudoinstruction to be a control instruction because it is really an OS trap.  The next basic block starts at line 14 and ends at 15.  The next starts at line 17 and ends at line 18.

The next basic block is a bit tricky because it is not delineated by a control instruction.  The next block starts at line 22 and ends at line 24.  Even though the instruction at line 25 is a non-control instruction, it can be jumped to by the control instruction at line 30, therefore it starts another basic block.  Note, in this example, I'm not expanding pseudo instructions.  In your solution you only need to find basic blocks in the final assembled code (e.g., with the pseudo instructions expanded).

In order to analyze an assembled MIPS program, you need a way to load the binary image of another MIPS program into memory.  I am providing the basic code that allows you to read a binary file containing an assembled mips program into memory.  To create binary images, all you need to do is to use the MARS File->Dump Memory... command.  Ensure that the output format is binary.  This way you can create your own test inputs.  I will also provide test input for grading.

Note that when you load the binary image into memory, it will be located in heap memory, not the text segment.  This means that the instructions will reside somewhere just above address 0x10010000.  Keep this in mind when doing your analysis.  Any direct jumps will be to addresses starting with 0x00400000.  

The programs that you will be analyzing will all end with the following instruction:

add $zero, $zero, $zero

This is equivalent to the word 0x00000020.  Do not include this instruction in the basic block count.

Your program should output a list of pairs.  Each pair is an address and the number of instructions in the basic block starting at that address.  Here is an example:

0x00400000  4
0x00400010  2
0x00400018  2

Some things to note:
  • Your program must analyze the actual instruction words in memory (you will not be parsing MIPS assembly code).
  • Remember that MARS will automatically translate pseudoinstructions into real MIPS instructions.
  • You might want to think about how you would write this program in C before you write the MIPS assembly version.
  • You are going to have to decode MIPS instructions to figure out the different types of instructions so that you can find the basic blocks.
  • Your solution need not be efficient.

Note: in MARS, to print out a hexadecimal number, you can use a built-in system call:

# syscall 34, $a0 = number to print, $v0 = 34
li $a0, 0xABCD1234
li $v0, 34
syscall

Here is a MIPS function to print out a hexadecimal number:

#
# printhex - put number to print into $a0
#

.data
result: .space 8
        .asciiz "\n"
hprefix:.asciiz "0x"

.text
printhex:
        li $t0,8        # eight hex digits in word
        la $t3,result   # answer string set up here

loop:   rol $a0,$a0,4   # start with leftmost digit
        and $t1,$a0,0xf # mask one digit
        ble $t1,9,print # check if 0 to 9
        add $t1,$t1,7   # 7 chars between '9' and 'A'
print:  add $t1,$t1,48  # ASCII '0' is 48
        sb $t1,($t3)    # save in string
        add $t3,$t3,1   # advance destination pointer
        add $t0,$t0,-1  # decrement counter
        bnez $t0,loop   # and continue if counter>0

        la $a0,hprefix
        li $v0,4
        syscall
        la $a0,result   # print result on terminal
        li $v0,4
        syscall
        jr $ra

Subpages (1): Results
ċ
input1.bin
(0k)
Greg Benson,
Feb 23, 2010, 5:14 PM
ċ
input1.s
(1k)
Greg Benson,
Feb 23, 2010, 5:14 PM
ċ
input2.bin
(0k)
Greg Benson,
Feb 23, 2010, 7:48 PM
ċ
input2.s
(1k)
Greg Benson,
Feb 23, 2010, 7:48 PM
ċ
input3.bin
(1k)
Greg Benson,
Feb 23, 2010, 5:15 PM
ċ
input3.s
(2k)
Greg Benson,
Feb 23, 2010, 5:15 PM
ċ
input4.bin
(1k)
Greg Benson,
Feb 23, 2010, 5:15 PM
ċ
input4.s
(2k)
Greg Benson,
Feb 23, 2010, 5:15 PM
ċ
input5.bin
(0k)
Greg Benson,
Feb 23, 2010, 5:15 PM
ċ
input5.s
(3k)
Greg Benson,
Feb 23, 2010, 5:15 PM
ċ
loadcode.s
(1k)
Greg Benson,
Feb 16, 2010, 12:12 PM
Comments