Instructions
Objective
Write a MIPS assignment program to examine MIPS instructions and determine dependencies.
Requirements and Specifications
Screenshots of output
Source Code
#############################################################
# NOTE: this is the provided main program
# of HW3 MIPS programming part.
#
# CS465-001 F2022
# HW3
#############################################################
#############################################################
# PUT YOUR TEAM INFO HERE
# NAME
# G#
# NAME 2
# G# 2
#############################################################
#############################################################
# Data segment
#############################################################
# Feel free to define additional data items if needed.
#############################################################
.data
PROMPT_N: .asciiz "How many instructions to process (valid range: [1,10])? "
ERROR_N: .asciiz "Incorrect number of instructions\n"
INPUTPROMPT: .asciiz "\nOpcode of next MIPS instruction: "
LABEL_HEAD: .asciiz "I"
COLON: .asciiz ": "
INSNCODE: .asciiz "\tInstruction Code: "
PROMPT_CONTROL: .asciiz "\tControl signals: "
RSPROMPT: .asciiz "\tEnter the $rs number: "
RTPROMPT: .asciiz "\tEnter the $rt number: "
RDPROMPT: .asciiz "\tEnter the $rd number: "
PROMPT_DEP: .asciiz "\tDependences: "
PROMPT_NONE: .asciiz "None"
INVALIDCODE: .word -1
INVALID: .asciiz "Invalid Input"
NEWLINE: .asciiz "\n"
NEWLINENUM: .word 0xA
# supported opcodes
ADDSTR: .asciiz "add"
ANDSTR: .asciiz "and"
ADDISTR: .asciiz "addi"
SLTSTR: .asciiz "slt"
LWSTR: .asciiz "lw"
SWSTR: .asciiz "sw"
BNESTR: .asciiz "bne"
JSTR: .asciiz "j"
.align 4
INPUT: .space 32 # 31 characters + 1 null byte
INST: .space 40 # array of 10 instructions, format: (inst, rs, rt, rd)
#############################################################
# Code segment
#############################################################
.text
#############################################################
# macro: print_int
#############################################################
# %x: value to be printed
.macro print_int (%x)
li $v0, 1
add $a0, $zero, %x
syscall
.end_macro
#############################################################
# main
#############################################################
main:
la $a0, PROMPT_N
li $v0, 4
syscall # Print out message asking for N (number of instructions to process)
li $v0, 5
syscall # read in an integer N
add $s0, $v0, $0
ble $s0, $0, error_report #if N<=0, error
bgt $s0, 10, error_report
li $s2, 0 # loop counter
######################################################
# Loop to Read in N MIPS instructions, one at a time
######################################################
input_loop:
#########################################
# get opcode as a string in INPUT buffer
#########################################
la $a0, INPUTPROMPT
li $v0, 4
syscall # print out MSG asking for one MIPS machine code
la $a0, INPUT
li $a1, 32
li $v0, 8
syscall # read in one string of up to 31 chars and store in INPUT
#######################################
# print a label
#######################################
addi $a0, $s2, 1
jal print_label
#######################################
# get instruction code and print
#######################################
la $a0, INPUT # load input string address
lb $t0, 0($a0) # load first char
beq $t0, 'a', if_a # if a, go to label
beq $t0, 'b', if_b # if b, go to label
beq $t0, 'j', if_j0 # if j, go to label
beq $t0, 'l', if_l # if l, go to label
beq $t0, 's', if_s # if s, go to label
# other input is error
j invalid
if_a:
lb $t0, 1($a0) # load second char
beq $t0, 'd', if_ad # if d, go to label
beq $t0, 'n', if_an # if n, go to label
j invalid # other input is error
if_ad:
lb $t0, 2($a0) # load third char
bne $t0, 'd', invalid # if not d, is invalid
lb $t0, 3($a0) # load fourth char
beq $t0, 10, if_add # if end, go to add
bne $t0, 'i', invalid # if not i, is invalid
lb $t0, 4($a0) # load fifth char
beq $t0, 10, if_addi # if end, go to addi
j invalid # other input is error
if_an:
lb $t0, 2($a0) # load third char
bne $t0, 'd', invalid # if not d, is invalid
lb $t0, 3($a0) # load fourth char
beq $t0, 10, if_and # if end, go to and
j invalid # other input is error
if_b:
lb $t0, 1($a0) # load second char
bne $t0, 'n', invalid # if not n, is invalid
lb $t0, 2($a0) # load third char
bne $t0, 'e', invalid # if not e, is invalid
lb $t0, 3($a0) # load fourth char
beq $t0, 10, if_bne # if end, go to bne
j invalid # other input is error
if_j0:
lb $t0, 1($a0) # load second char
beq $t0, 10, if_j # if end, go to j
j invalid # other input is error
if_l:
lb $t0, 1($a0) # load second char
bne $t0, 'w', invalid # if not n, is invalid
lb $t0, 2($a0) # load third char
beq $t0, 10, if_lw # if end, go to lw
j invalid # other input is error
if_s:
lb $t0, 1($a0) # load second char
beq $t0, 'l', if_sl # if l, go to label
beq $t0, 'w', if_sw0 # if w, go to label
j invalid # other input is error
if_sl:
lb $t0, 2($a0) # load third char
bne $t0, 't', invalid # if not t, is invalid
lb $t0, 3($a0) # load fourth char
beq $t0, 10, if_slt # if end, go to slt
j invalid # other input is error
if_sw0:
lb $t0, 2($a0) # load third char
beq $t0, 10, if_sw # if end, go to sw
j invalid # other input is error
if_add:
li $s3, 0x0 # instruction 0
li $t0, 0 # branch = 0
li $t1, 0 # jump = 0
li $t2, 1 # regwrite = 1
li $t3, 0 # memread = 0
li $t4, 0 # memwrite = 0
li $t5, 0 # alusrc = 00 = 0
li $t6, 0 # memtoreg = 00 = 0
li $t7, 1 # regdst = 01 = 1
j print_code # go to print the code
if_and:
li $s3, 0x1 # instruction 1
li $t0, 0 # branch = 0
li $t1, 0 # jump = 0
li $t2, 1 # regwrite = 1
li $t3, 0 # memread = 0
li $t4, 0 # memwrite = 0
li $t5, 0 # alusrc = 00 = 0
li $t6, 0 # memtoreg = 00 = 0
li $t7, 1 # regdst = 01 = 1
j print_code # go to print the code
if_addi:
li $s3, 0x3 # instruction 3
# addi is neither a branch nor a jump, the memory is not used so no memread
# and no memwrite, the alu result is saved in a register so regwrite is 1 and
# we need memtoreg = 0 to get result from the alu, the second input to alu is an
# immediate, so alusrc = 1, the result is saved to rt, so regdst = 0
li $t0, 0 # branch = 0
li $t1, 0 # jump = 0
li $t2, 1 # regwrite = 1
li $t3, 0 # memread = 0
li $t4, 0 # memwrite = 0
li $t5, 1 # alusrc = 01 = 1
li $t6, 0 # memtoreg = 00 = 0
li $t7, 0 # regdst = 00 = 0
j print_code # go to print the code
if_slt:
li $s3, 0x2 # instruction 2
li $t0, 0 # branch = 0
li $t1, 0 # jump = 0
li $t2, 1 # regwrite = 1
li $t3, 0 # memread = 0
li $t4, 0 # memwrite = 0
li $t5, 0 # alusrc = 00 = 0
li $t6, 0 # memtoreg = 00 = 0
li $t7, 1 # regdst = 01 = 1
j print_code # go to print the code
if_lw:
li $s3, 0x4 # instruction 4
li $t0, 0 # branch = 0
li $t1, 0 # jump = 0
li $t2, 1 # regwrite = 1
li $t3, 1 # memread = 1
li $t4, 0 # memwrite = 0
li $t5, 1 # alusrc = 01 = 1
li $t6, 1 # memtoreg = 01 = 1
li $t7, 0 # regdst = 00 = 0
j print_code # go to print the code
if_sw:
li $s3, 0x5 # instruction 5
li $t0, 0 # branch = 0
li $t1, 0 # jump = 0
li $t2, 0 # regwrite = 0
li $t3, 0 # memread = 0
li $t4, 1 # memwrite = 1
li $t5, 1 # alusrc = 01 = 1
li $t6, 2 # memtoreg = 10 = X
li $t7, 2 # regdst = 10 = X
j print_code # go to print the code
if_bne:
li $s3, 0x6 # instruction 6
li $t0, 1 # branch = 1
li $t1, 0 # jump = 0
li $t2, 0 # regwrite = 0
li $t3, 0 # memread = 0
li $t4, 0 # memwrite = 0
li $t5, 0 # alusrc = 00 = 0
li $t6, 2 # memtoreg = 10 = X
li $t7, 2 # regdst = 10 = X
j print_code # go to print the code
if_j:
# j is not a branch but it's a jump, the memory is not used so no memread
# and no memwrite, no register is written so no regwrite
# the alu is not used so alusrc = X, neither alu result nor memory is used so
# memtoreg = X and since no register is written regdst = X
li $s3, 0x7 # instruction 7
li $t0, 0 # branch = 0
li $t1, 1 # jump = 1
li $t2, 0 # regwrite = 0
li $t3, 0 # memread = 0
li $t4, 0 # memwrite = 0
li $t5, 2 # alusrc = 10 = X
li $t6, 2 # memtoreg = 10 = X
li $t7, 2 # regdst = 10 = X
print_code:
move $t8, $t0 # save t0
move $a0, $s3 # copy insn code
jal print_insn_code # print code
move $t0, $t8 # restore t0 #######################################
# get control signals and print
#######################################
li $s4, 0 # start with control bits in zero
sll $t0, $t0, 10 # shift branch bit to bit 10
or $s4, $s4, $t0 # add branch bit
sll $t1, $t1, 9 # shift jump bit to bit 9
or $s4, $s4, $t1 # add jump bit
sll $t2, $t2, 8 # shift regwrite bit to bit 8
or $s4, $s4, $t2 # add regwrite bit
sll $t3, $t3, 7 # shift memread bit to bit 7
or $s4, $s4, $t3 # add memread bit
sll $t4, $t4, 6 # shift memwrite bit to bit 6
or $s4, $s4, $t4 # add memwrite bit
sll $t5, $t5, 4 # shift alusrc bits to bits 4-5
or $s4, $s4, $t5 # add alusrc bits
sll $t6, $t6, 2 # shift memtoreg bits to bits 2-3
or $s4, $s4, $t6 # add memtoreg bits
or $s4, $s4, $t7 # add regdst bits
move $a0, $s4 # copy control signals
jal print_control_signals # print them
#######################################
# read in registers as needed
#######################################
li $s4, -1 # by default, no rs
li $s5, -1 # by default, no rt
li $s6, -1 # by default, no rd
beq $s3, 7, get_dep # if j instruction, no registers
la $a0, RSPROMPT # load string address
jal print_string # prompt for rs
li $v0, 5
syscall # read in an integer N
blt $v0, $0, invalid # if N<0, error
bgt $v0, 31, invalid # if N > 31, error
move $s4, $v0 # save rs
la $a0, RTPROMPT # load string address
jal print_string # prompt for rt
li $v0, 5
syscall # read in an integer N
blt $v0, $0, invalid # if N<0, error
bgt $v0, 31, invalid # if N > 31, error
move $s5, $v0 # save rt
bge $s3, 3, get_dep # if addi, lw, sw or bne, no rd register
la $a0, RDPROMPT # load string address
jal print_string # prompt for rd
li $v0, 5
syscall # read in an integer N
blt $v0, $0, invalid # if N<0, error
bgt $v0, 31, invalid # if N > 31, error
move $s6, $v0 # save rd
#######################################
# get dependence and print
#######################################
get_dep:
la $a0, PROMPT_DEP # print dependence message
jal print_string
li $s7, 0 # no dependences at start
beq $s2, $0, no_dep # if this is the first instruction, no dependencies
beq $s3, 7, no_dep # if j instruction, no dependencies
bge $s3, 3, get_dep_i # if addi, lw, sw or bne, go to I inst
get_dep_r:
move $a0, $s4 # pass rs
la $a1, INST # pass array
move $a2, $s2 # pass current array size
jal find_dependence # try to find a dependence
beq $v0, $0, tst_r_rt # if no dependence, try with rt
move $a0, $s4 # register dependence in rs
move $a1, $v0 # label of previous position
addi $a2, $s2, 1 # current label
jal print_dependence # print dependence
addi $s7, $s7, 1 # increment dependences
tst_r_rt:
beq $s4, $s5, no_dep # if rs = rt, we have found all dependences
move $a0, $s5 # pass rt
la $a1, INST # pass array
move $a2, $s2 # pass current array size
jal find_dependence # try to find a dependence
beq $v0, $0, no_dep # if no dependence, end
move $a0, $s5 # register dependence in rt
move $a1, $v0 # label of previous position
addi $a2, $s2, 1 # current label
jal print_dependence # print dependence
addi $s7, $s7, 1 # increment dependences
j no_dep # we have found all dependences
get_dep_i:
move $a0, $s4 # pass rs
la $a1, INST # pass array
move $a2, $s2 # pass current array size
jal find_dependence # try to find a dependence
beq $v0, $0, tst_i_rt # if no dependence, try with rt
move $a0, $s4 # register dependence in rs
move $a1, $v0 # label of previous position
addi $a2, $s2, 1 # current label
jal print_dependence # print dependence
addi $s7, $s7, 1 # increment dependences
tst_i_rt:
beq $s3, 3, no_dep # if addi, rt is not checked
beq $s3, 4, no_dep # if lw, rt is not checked
beq $s4, $s5, no_dep # if rs = rt, we have found all dependences
move $a0, $s5 # pass rt
la $a1, INST # pass array
move $a2, $s2 # pass current array size
jal find_dependence # try to find a dependence
beq $v0, $0, no_dep # if no dependence, end
move $a0, $s5 # register dependence in rt
move $a1, $v0 # label of previous position
addi $a2, $s2, 1 # current label
jal print_dependence # print dependence
addi $s7, $s7, 1 # increment dependences
no_dep:
bne $s7, $0, save_inst # if there were dependences, skip to save
la $a0, PROMPT_NONE # else, print no dependence
jal print_string # print message
save_inst:
la $t0, INST # load address of instruction array
sll $t1, $s2, 2 # N * 2
add $t0, $t0, $t1 # get address of array[N]
sb $s3, 0($t0) # save instruction code
sb $s4, 1($t0) # save rs
sb $s5, 2($t0) # save rt
sb $s6, 3($t0) # save rd
input_loop_end:
la $a0, NEWLINE
jal print_string
addi $s2, $s2, 1
blt $s2, $s0, input_loop# exit of main
exit:
li $v0, 10
syscall
error_report:
la $a0, ERROR_N
li $v0, 4
syscall # Print out error message for incorrect N
j exit
invalid:
jal print_invalid # print invalid input
j exit
######## end of main ###################
########################################
#############################################################
# subroutine: print_string
#############################################################
# $a0 set as the address of string to be printed
# no return
print_string:
li $v0, 4
syscall
jr $ra
#############################################################
# subroutine: print_invalid
#############################################################
# no argument; no return
print_invalid:
la $a0, INVALID
li $v0, 4
syscall
jr $ra
#############################################################
# subroutine: print_newline
#############################################################
# no argument; no return
print_newline:
la $a0, NEWLINE
li $v0, 4
syscall
jr $ra
#############################################################
# subroutine: print_label
#############################################################
# $a0: the number used in label
# no return
#############################################################
# Example usage
#
# li $a0, 1
# jal print_label # print out "I1:"
#############################################################
print_label:
add $t0, $a0, $0 # remember $a0
addi $sp, $sp, -4 # save $ra
sw $ra, 0($sp)
la $a0, LABEL_HEAD # print "I"
jal print_string
print_int($t0) # print the number
la $a0, COLON
jal print_string # print ":"
lw $ra, 0($sp) # restore $ra and $sp
addi $sp, $sp, 4
jr $ra
#############################################################
# subroutine: print_insn_code
#############################################################
# a0: instruction code to be printed
# no return
#############################################################
# Example usage
#
# li $a0, 1
# jal print_insn_code # print out "\tInstruction Code: 1"
#############################################################
print_insn_code:
add $t0, $a0, $0
la $a0, INSNCODE
li $v0, 4
syscall
print_int($t0)
la $a0, NEWLINE
li $v0, 4
syscall
jr $ra
#############################################################
# subroutine: print_control_signals
#############################################################
# a0: control signal to be printed
# no return
#############################################################
# Example usage
#
# li $a0, 0x111
# jal print_control_signals # print out "\tControl signals: 0x00000111"
#############################################################
print_control_signals:
add $t0, $a0, $0
la $a0, PROMPT_CONTROL
li $v0, 4
syscall
add $a0, $t0, $0
li $v0, 34
syscall
la $a0, NEWLINE
li $v0, 4
syscall
jr $ra
#############################################################
# subroutine: print_no_dependence
#############################################################
# no argument, no returnprint_no_dependence:
la $a0, PROMPT_DEP
li $v0, 4
syscall
la $a0, PROMPT_NONE
li $v0, 4
syscall
jr $ra
#############################################################
# subroutine: print_dependence
#############################################################
# $a0 set as the reg number;
# $a1 set as index of producer instruction
# $a2 set as index of consumer instruction
# no return
#############################################################
# Example usage
#
# li $a0, 1
# li $a1, 2
# li $a2, 3
# jal print_dependence # print out "(1, I2, I3)"
#############################################################
.data
LP: .asciiz "("
RP: .asciiz ")"
COMMA: .asciiz ", "
.text:
print_dependence:
#addi $t0, $0, 1
#sw $t0, NO_DEP($0)
addi $sp, $sp, -16 #save arguments and $ra
sw $ra, 12($sp)
sw $a0, 8($sp)
sw $a1, 4($sp)
sw $a2, 0($sp)
la $a0, LP #print start
jal print_string
lw $a0, 8($sp) #print reg num
print_int($a0)
la $a0, COMMA #print comma
jal print_string
la $a0, LABEL_HEAD #print I
jal print_string
lw $a0, 4($sp) #print producer
print_int($a0)
la $a0, COMMA #print comma
jal print_string
la $a0, LABEL_HEAD #print I
jal print_string
lw $a0, 0($sp) #print consumer
print_int($a0)
la $a0, RP #print start
jal print_string
lw $ra, 12($sp)
addi $sp, $sp, 16
jr $ra
#############################################################
# subroutine: find_dependence
#############################################################
# $a0 set as the reg number;
# $a1 pointer to array
# $a2 array size
# returns $v0 = found dependency, 0 if none
#############################################################
# Example usage
#
# li $a0, 1
# li $a1, INST
# li $a2, 3
# jal find_dependence # find instruction
#############################################################
find_dependence:
li $v0, 0 # assume no dependence by default
li $t0, 0 # i = 0
find_loop:
sll $t1, $t0, 2 # i*4
add $t1, $t1, $a1 # address of array[i]
lb $t2, 0($t1) # load instruction code
lb $t3, 1($t1) # load rs
lb $t4, 2($t1) # load rt
lb $t5, 3($t1) # load rd
beq $t2, 7, next_dep # if is j, there is no dependence
bge $t2, 3, find_dep_i # if is I, check dependence
find_dep_r:
bne $a0, $t5, next_dep # if reg != previous rd, check next
addi $v0, $t0, 1 # save dependence label
j next_dep # find next dependence
find_dep_i:
beq $t2, 5, next_dep # if previous was sw, there is no dependence
beq $t2, 6, next_dep # if previous was bne, there is no dependence
bne $a0, $t4, next_dep # if reg != previous rt, there is no dependence
addi $v0, $t0, 1 # save dependence label
next_dep:
addi $t0, $t0, 1 # go to next instruction
blt $t0, $a2, find_loop # repeat while there are more instructions
jr $ra # return