Подпрограммы с вложенными вызовами в MIPS

Эта программа предназначена для замены всех строчных букв в строке символом *.

У меня проблема во вложенном вызове подпрограмм. т.е. одни и те же регистры $t и $a используются в разных подпрограммах. Таким образом, когда подпрограмма вызывается в другой подпрограмме, регистры подпрограммы вызывающей перепутались.

.data
    str: .asciiz "WindOnTheHill" 

.text
    la $a0, str # start of the string
    li $a1, '*'
    jal ReplaceAllLower

    #la $a0, str # start of the string
    jal PrintStr
    jal Exit

ReplaceAllLower:
    # backup return address
    addi $sp, $sp, -12 #  create space for 3 words
               # (3*4=12 bytes) on the stack 
               # (push) for $ra
    sw $ra, 0($sp) # backup return address $ra

    # protect arguments from change
    sw $a0, 4($sp) # backup string address
    sw $a1, 8($sp) # backup char 

    # get string length
    jal StrLen # obtain string length
    move $t0, $v0 # backup string length

    # retrieve argument values  
    lw $a1, 8($sp) # restore char 
    lw $a0, 4($sp) # restore string address

    move $t1, $a0 # obtain string address
    move $t2, $a1 # obtain char
    li $t3, 0 # loop counter    

    while:  
        bgt $t3, $t0, end_while 

        jal IsLower

        beq $t0, 1, lower_case
        j not_lower_case

        lower_case:
            sb $t2, ($a0)           

        not_lower_case: 
            addi $a0, $a0, 1 # increment address
            addi $t3, $t3, 1 # increment loop counter

        j while
    end_while:  

    move $a0, $t1

    # restore stack     
    lw $ra, 0($sp) # restore $ra
    addi $sp, $sp, 16 # return the space on the stack(pop)

    # return 
    jr $ra  

IsLower:
    lb $t0, ($a0) # obtain the character
    li $t1, 97 # 'a' - character
    li $t2, 122 # 'z' - character

    bge $t0, $t1, con1_fulfilled #bigger tha or equal to 0  
    j con1_not_fulfilled

con1_fulfilled:
    ble $t0, $t2, con2_fullfilled #less than or equal to 9
    j con2_not_fulfilled

con2_fullfilled:
    li $v0, 1
    j return

con1_not_fulfilled:
con2_not_fulfilled:
    li $v0, 0

return:                                                                     
    # return 
    jr $ra 

StrLen:
    move $a1, $a0 # start of string
    # run a loop
    li $t0, '\0' # null character 
    li $t1, 0 # prepare the counter

    start_loop: 
        lb $v0, ($a0) # obtain the 1st character

        beq $v0, $t0, end_loop  # exit loop if '\0'-char found

        addi $t1, $t1, 1 # increment counter
        addi $a0, $a0, 1 # increment address

        j start_loop # iterate again
    end_loop:

    move $a0, $a1 #restore string address
    move $v0, $t1 # return value

    # return 
    jr $ra  

PrintStr:   
    li $v0, 4
    syscall
    # return 
    jr $ra


Exit:
    # push $s0 on stack
    addi $sp, $sp, -4 # create 4-bytes on the stack
    sw $s0, ($sp) # cpy $s0 to stack

    #terminate program
    li $v0, 10
    syscall

    # free stack  
        addi $sp, $sp, 4 
    # return 
    jr $ra  

_{Примечание. Не будем сейчас концентрироваться на алгоритме.}

Итак, мой вопрос:
Какую технику мне следует использовать, чтобы избавиться от этой проблемы, так как очень трудно заранее знать, какая подпрограмма будет вызываться в будущем (библиотека может расширяться со временем)?