MIPS 全排列失败
MIPS full permutation fail
我的任务是将以下代码转换为程序集（MIPS），我可以完成除 return 部分以外的所有其他部分，因为我基本上不知道如何保存值前一个i.
#include <stdio.h>
#include <stdlib.h>
int symbol[7], array[7];
int n;
void FullArray(int index)
{
int i;
if(index>=n)
{
for(i=0;i<n;i++)
{
printf("%d ",array[i]);
}
printf("\n");
return;
}
for(i=0;i<n;i++)
{
printf("here4");
if(symbol[i]==0)
{
array[index] = i+1;
symbol[i]=1;
FullArray(index+1);
symbol[i]=0;
}
}
}
int main(void)
{
int i;
scanf("%d", &n);
FullArray(0);
return 0;
}
这是我的 MIPS 代码：
.data
array: .space 28
symbol:.space 28
ispace: .asciiz " "
ienter: .asciiz "\n"
.text
li $v0, 5
syscall
move $t0, $v0
move $s0, $t0 #n
move $s1, $zero #index
move $s2, $zero #i=0
move $s5, $zero
j fullarray
fullarray:
bge $s1, $s0, print #if index is larger or equal to n, go to print loop
j always
print:
move $s2, $zero #i=0
j print2
print2:
bge $s2, $s0, always #while i<n
move $s3, $s2
add $s3, $s3, $s2
sll $s3, $s3, 1
lw $t0, array($s3)
move $a0, $t0
li $v0, 1
syscall
la $a0, ispace
li $v0, 4
syscall
addi $s2, $s2, 1
blt $s2, $s0, print2
la $a0, ienter
li $v0, 4
syscall
jr $ra
always:
move $s2, $zero #i=0
j always2
always2:
bge $s2, $s0, end #while i<n
move $s3, $s2
add $s3, $s3, $s2
sll $s3, $s3, 1
lw $t0, symbol($s3) #load symbol of the current array number
beq $t0, $zero, storearray #store array value
addi $s2, $s2, 1 #i++
blt $s2, $s0, always2
j end
storearray:
move $s4, $s1
add $s4, $s4, $s1
sll $s4, $s4, 1
addi $t2, $s2, 1 #set array number to i+1
sw $t2, array($s4)
addi $t2, $zero, 1
sw $t2, symbol($s3) #set the symbol of the current array number to 1
sub $sp, $sp, 12
sw $ra, 0($sp) #save $ra
sw $s1, 4($sp) #save index
sw $s2, 8($sp)
addi $s1, $s1, 1 #index + 1
jal fullarray
lw $s1, 4($sp)
lw $s2, 8($sp)
lw $ra, 0($sp)
add $sp, $sp, 12
move $s4, $s1
add $s4, $s4, $s1
sll $s4, $s4, 1
move $s2, $s1
move $s3, $s2
add $s3, $s3, $s2
sll $s3, $s3, 1
sw $zero, symbol($s3) #set the symbol of current array number to 0
addi $s2, $s2, 1 #i++
blt $s2, $s0, always2
beq $s1, $zero, end
jr $ra
end:
示例预期输出为：
（输入=4）
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
等
但我的代码总是 return 给我
1 2 3 4
1 2 4 3
1 2 4 3
1 2 4 3
...
1 2 4 3
请帮忙！
建议从头再来写一遍
您当前的MIPS代码使用s0, s1, ...作为全局变量，这对于非递归代码来说是非常合理的，但是递归通常基于local/functional编写代码的方式。
而你的错误来自滥用 s# 寄存器，多次粗心地添加无用的指令和冗余计算，直到你最终不小心修改了一些你本来想保留的东西。
一些粗略的草图你可以如何（我会）组织代码：
main部分
初始化s0 = n，这个和"global variable"一样好用，不用改。
但之后尝试模仿C类函数调用fullArray(0);:
start:
# read N from user, set $s0 to N
...
# call recursive function fullarray with argument value 0
move $a0, $zero # first argument "index" = 0
jal fullarray # call the function (not jump)
li $v0,10 # exit syscall
syscall
这部分和你的类似，但是你用j而不是jal输入fullarray，所以你将很难终止整个代码，而原来的C算法将简单地从所有嵌套循环中 运行 和 return 到 main，不需要对 fullarray.
内的终止条件进行额外测试
并且在跳入函数之前初始化函数的 LOCAL 变量。那应该已经 听起来 奇怪了，在编写源代码时尽量遵循 "locality" 原则，因为通常在源代码中写的东西正是它们属于/正在使用的地方。局部变量应该在函数内部初始化（并且接近它们的实际用法，前面的行不多）。当你知道你不会调用一些进一步的子程序时，你应该为本地人使用非保留的 $t# 寄存器，这会修改它们。
（这只是惯例，因为编写代码的程序员负责保存 $s# 寄存器，它们在物理上与 $t# 寄存器相同，CPU 不会它们之间有任何区别......但是有经验的 MIPS 汇编程序员在阅读源代码时会以不同的方式思考它们）
fullarray功能概览设计
让我们使用通用调用约定，其中 a0 包含函数参数，$ra 是 return 地址，函数不应修改 $s# 寄存器。
fullarray:
if (a0 "index" >= N) { print_array; return; }
preserve in stack: $ra (return address) and $s1 (will be modified)
for (s1 : all_possible_symbols) { // that's range 1..N
if (symbol s1 is used already) continue;
mark symbol s1 as used;
array[a0 "index"] = s1;
fullarray(index + 1); // <=> ++a0; jal fullarray; --a0;
// because symbol ("i" variable) is in $s1, it is still valid even here!
// (if function fullarray() is correct and preserves $s# registers)
// EDIT: in common convention function is allowed to modify a0,
// but this design expect it to be preserved! (sort of bug)
unmark symbol s1 (is unused now);
} //for(all symbols s1 on position "index")
restore $ra and $s1 and $sp
jr $ra
("edit" 发布前：实施时，我注意到我已经计划在头上保留 $a0 原因 simplicity/performance，但通用调用约定并不要求, 所以这是最后的自定义调用约定)
fullarray函数实现-先试试
让我有点奇怪，您已经拥有多少代码，虽然听起来很简单。现在我会像这样在第一个版本中将其重写为 asm：
（请注意，我对 array 和 symbol 使用 byte 数组，因为最大 N 仅为 7，因此无需使用 word 值，并且它简化了索引，不需要做 *4 来计算地址)
fullarray:
# extra requirement for this fullarray function: preserve also $a0!
# if (a0 "index" >= N) { print_array; return; }
bge $a0, $s0, print_array
# preserve in stack: $ra (return address) and $s1 (will be modified)
addi $sp, $sp, -8
sw $ra, 0($sp) #save return address
sw $s1, 4($sp) #preserve old $s1 value
# for (s1 : all_possible_symbols) { // that's range 1..N
# this will be actually do {} while() loop, because we know N is valid (the main should test input!)
move $s1, $zero # s1 = current symbol index, going from zero to N-1 (symbol = index+1)
symbol_loop:
#here: s0 = N, s1 = symbol index, a0 = array index
# if (symbol s1 is used already) continue;
lb $t0, symbol($s1)
bnez $t0, symbol_loop_advance
# mark symbol s1 as used (by N value, any non-zero value is good, N is non-zero and in $s0)
sb $s0, symbol($s1)
# array[a0 "index"] = s1;
addi $t0, $s1, 1 # t0 = symbol value (= symbol_index+1) (avoiding $s# usage for temporary)
sb $t0, array($a0) # array[a0] = symbol
# call fullrray(index+1) recursively
addi $a0, $a0, 1
jal fullarray
addi $a0, $a0, -1
# unmark symbol s1 (is unused now)
sb $zero, symbol($s1)
# end of for/do_while loop
symbol_loop_advance:
addi $s1, $s1, 1 # next symbol index
blt $s1, $s0, symbol_loop # while(symbol_index < N);
# restore $ra and $s1 and $sp ($a0 is also preserved, that's extra requirement)
lw $ra, 0($sp) #restore return address
lw $s1, 4($sp) #restore old $s1 value
addi $sp, $sp, 8
# return from function
jr $ra
print_array:
# extra requirement for this fullarray function: preserve also $a0!
#TODO printing (don't modify any $s# register, or $ra)
jr $ra # return
"fullarray:" 函数的核心（w/o 打印）大约有 20 条伪指令。您的核心部分有大约 40 条伪指令。但大多数情况下，每条指令都应该清楚地连接到原始 algorithm/intention，在 MIPS 汇编不允许单指令实现的情况下，只有最少的帮助指令（比如 if (symbol[i]) 必须首先从内存中获取值，然后它可以测试它）。
fullarray功能实现-改进建议
现在汇编主要是关于性能（有时用汇编编写代码的另一个好理由是代码的大小）。在 MIPS 上，代码的大小通常会直接影响性能。
如果您要检查该函数的反汇编，在本机 MIPS 指令中（在 MARS 中：编译后 "Execute" 选项卡中的 "Basic" 列），您会注意到 symbol 周围的部分/array 内存使用量确实大幅增长。在 MIPS 上加载地址不是微不足道的，你还有一些备用的 $s# 寄存器，所以你可以使用一些作为另一个全局值，只加载一次 symbol/array 地址，比如：
# somewhere in main before calling fullarray(0)
la $s6, symbol
la $s7, array
然后在函数内部您可以重用该值进行寻址：
# if (symbol s1 is used already) continue;
addu $t1, $s6, $s1 # t1 = symbol($s1)
lb $t0, ($t1)
bnez $t0, symbol_loop_advance
# mark symbol s1 as used (by N value, any non-zero value is good, N is non-zero and in $s0)
sb $s0, ($t1)
# array[a0 "index"] = s1;
addu $t1, $s7, $a0 # t1 = array($a0)
addi $t0, $s1, 1 # t0 = symbol value (= symbol_index+1) (avoiding $s# usage for temporary)
sb $t0, ($t1) # array[a0] = symbol
这将产生更少的本机 MIPS 指令 = 更小更快的代码。
另外，由于最大 N 为 7，您可以完全摆脱 symbol 数组，并使用存储在寄存器中的位图，通过特定位 set/unset 标记符号的使用（MIPS 寄存器是 32 位大，所以这很容易达到 N = 32）。
我会调整 +1 发生的位置（符号索引与屏幕上的符号），通常在 ASM/C 编程中你希望事情从 0 开始，到 N-1 结束，所以我会生成array 中的排列与符号 0..N-1，并在打印部分对人类 1..N 符号进行 +1 修复，只是重新格式化输出。
如果这是我的代码，我会将符号重命名为更有意义的名称，例如：
array = permutation
symbol = used_symbols
fullarray = permutate_position
print = show_permutation
print2 = show_permutation_symbol
...etc...
在用编程语言编写代码时，始终对其进行编辑，直到它读 好。想象你是一个程序员，他并没有编写原始源代码，而是需要帮助他的同事，或者修复其他人代码中的错误——以这种心态阅读你的代码，看看有什么不太清楚，有什么可以更好地注释（主要是 "intent" 代码的一小部分应该实现），functions/variables 的哪些名称有意义，代码需要更多白色 space 以更具可读性等.
在将源代码写入易于阅读的源代码的过程中投入时间会在调试和维护阶段 return 迅速。通常来源比写的多 read/edited 很多倍。
此外，我什至会更积极地 reuse/preserve 寄存器中的值，避免内存，避免递归（因为它根本不需要这个任务，它甚至使它变得更难)。我会以这样的代码结束：
我写的会是什么样子
.eqv MAX_N, 8 # 8 will work at most (BTW, that's ~40k of permutations)
.data
permutation: .space MAX_N
# must follow in memory the permutation array directly, at +MAX_N offset, do not move it
symbol_masks: .space MAX_N # current symbol mask per position in "permutation" array
input_N_prompt: .asciiz "Enter N (permutation size, 1..7): "
.text
start:
li $v0, 4
la $a0, input_N_prompt
syscall # display input prompt
li $v0, 5
syscall # read integer from user
# validate N (1 <= N <= MAX_N)
blez $v0, start
bgt $v0, MAX_N, start
# initialize global "variables"
move $s0, $v0 # s0 = N
move $s1, $zero # s1 = symbols used (none) = bitmask, each symbol has one bit
la $s2, permutation # s2 = permutation.begin() address
addu $s3, $s2, $s0 # s3 = permutation.end() address
addi $s4, $zero, 1 # s4 = 1
move $t7, $s2 # t7 = current position in permutation (address)
symbol_loop_init_position:
# initialize current (position) symbol to 0 with mask 0x01
sb $zero, ($t7)
sb $s4, MAX_N($t7)
symbol_loop: # loops through all symbols for current position $t7
# will try if symbol at current position is valid
lb $t0, MAX_N($t7) # load bit mask of current symbol
and $at, $t0, $s1 # check usage
beq $at, $t0, advance_to_next_symbol # when used, advance to next symbol
# valid symbol in permutation found, mark symbol as used
or $s1, $s1, $t0
# advance to next position
addi $t7, $t7, 1
bne $t7, $s3, symbol_loop_init_position
# permutation is complete, display it
jal print_permutation
# after print continue with "symbol_loop_retreat" logic (back to valid position)
symbol_loop_retreat: # current position "exhausted" in search (or printed), retreat
beq $t7, $s2, all_permutations_printed # retreating from first position => end
addi $t7, $t7, -1 # retreat one position back
lb $at, MAX_N($t7)# load bitmask of current symbol at current position
xor $s1, $s1, $at # unmark the currently used symbol
# and try next symbol for new (previous) current position
advance_to_next_symbol:
lb $at, ($t7)
addi $at, $at, 1 # advance to next symbol value
beq $at, $s0, symbol_loop_retreat # symbol == N -> retreat to previous position
sb $at, ($t7) # store next symbol into permutation
lb $at, MAX_N($t7)
sll $at, $at, 1 # advance also symbol bitmask
sb $at, MAX_N($t7)
j symbol_loop # and try it in permutation, if the new symbol is valid
all_permutations_printed:
# terminate execution
li $v0, 10
syscall
# not a general subroutine, using known registers heavily, modifies only v0, a0 (t7 = s3 at end (again))
print_permutation:
move $t7, $s2 # permutation.begin() address for display loop
print_permutation_loop:
# print one symbol from permutation
move $v0, $s4 # v0 = 1 (print integer)
lb $a0, ($t7) # load permutation symbol (in 0..N-1 value)
add $a0, $a0, $s4 # do +1 to make it "human" formatted 1..N value
syscall
# print single space character
li $v0, 11
li $a0, ' '
syscall
# loop until all symbols were printed
addi $t7, $t7, 1 # ++address of current symbol
bne $t7, $s3, print_permutation_loop
# print newline character
li $v0, 11
li $a0, '\n'
syscall
jr $ra # return
写完之后，其实非递归版本的控制流程比较难理解，写了挺费时间的，还好第一次尝试成功了，就不用debug了（但这就是为什么我花了很多时间来写它，大概大约 2 小时，直到我设法清理它，使它有意义并很好地组合在一起。
但是从性能的角度来看，这是200B左右的长代码，你的是350B左右。此外，执行的指令总量会少得多，因为我在内存中只保留 storing/restoring 符号及其使用位掩码，而不是接触堆栈。 （尽管使用 "print integer" 控制台的输出实际上会使它与您的原始代码一样慢......如果我考虑任务的 "print" 部分 - 我只认为排列生成器是主要焦点 -我会更改排列生成器以直接生成整行字符串，改变 ASCII 字母本身，而不是整数元素，这将消除 "print integer" 调用的需要，这是迄今为止执行的最复杂的代码（不幸的是隐藏在 MARS 中模拟器实现，不是在 MIPS 汇编中创建的，因此您无法在调试器中查看将整数值打印为字符串需要多少努力）。
它仍然可以缩短几个字节，但我尽量保持它的可读性，这样你就有机会通读它，并理解它是如何工作的。它应该有点棘手，希望使用您可能不知道或尚未使用的几个概念（例如位设置为 store/check 哪些符号是 used/unused，使用内存地址而不是主循环的索引值等...）。当然它不是递归的，所以你不能提交它作为你的 class 的解决方案......修复你的，它与我的 "first try" 示例和调试器一起并不那么困难。
（还有一件事.. 关于 $at 寄存器的使用...宁可不要那样做，如果你不是 100% 确定如何安全地做到这一点，基本上你必须知道哪些指令是本机的MIPS 并且是伪指令，因为它们经常使用 $at 寄存器进行中间计算，因此使用 $at 获取某些值的代码将在意外使用某些伪指令时中断......我是使用 $at 作为部分有趣的挑战，让它变得更复杂，我不会在一些严肃的生产代码中。）
关于你的原始代码的另一件事，我忘记提到了，但这表明你理解了这个概念，但需要练习才能获得更多技能（别担心，它与你编写的代码量有关, 需要时间):
这样的代码：
move $s3, $s2
add $s3, $s3, $s2
sll $s3, $s3, 1
本质上是在做 s3 = s2*4，但是以复杂的方式：s3 = s2, s3 += s2 (that's s2*2), s3 <<= 1 (s3 = s3*2).
在 MIPS 上可以用一条指令完成：
sll $s3, $s2, 2 # s3 = s2 * 4 (by shifting s2 value 2 bits left)
这是您的主要错误的部分原因，因为您一直为此使用多个寄存器，直到您不小心也 "i" 进行了更改（当您可以通过一条指令简单地设置一个临时寄存器时）。
我的任务是将以下代码转换为程序集（MIPS），我可以完成除 return 部分以外的所有其他部分，因为我基本上不知道如何保存值前一个i.
#include <stdio.h>
#include <stdlib.h>
int symbol[7], array[7];
int n;
void FullArray(int index)
{
int i;
if(index>=n)
{
for(i=0;i<n;i++)
{
printf("%d ",array[i]);
}
printf("\n");
return;
}
for(i=0;i<n;i++)
{
printf("here4");
if(symbol[i]==0)
{
array[index] = i+1;
symbol[i]=1;
FullArray(index+1);
symbol[i]=0;
}
}
}
int main(void)
{
int i;
scanf("%d", &n);
FullArray(0);
return 0;
}
这是我的 MIPS 代码：
.data
array: .space 28
symbol:.space 28
ispace: .asciiz " "
ienter: .asciiz "\n"
.text
li $v0, 5
syscall
move $t0, $v0
move $s0, $t0 #n
move $s1, $zero #index
move $s2, $zero #i=0
move $s5, $zero
j fullarray
fullarray:
bge $s1, $s0, print #if index is larger or equal to n, go to print loop
j always
print:
move $s2, $zero #i=0
j print2
print2:
bge $s2, $s0, always #while i<n
move $s3, $s2
add $s3, $s3, $s2
sll $s3, $s3, 1
lw $t0, array($s3)
move $a0, $t0
li $v0, 1
syscall
la $a0, ispace
li $v0, 4
syscall
addi $s2, $s2, 1
blt $s2, $s0, print2
la $a0, ienter
li $v0, 4
syscall
jr $ra
always:
move $s2, $zero #i=0
j always2
always2:
bge $s2, $s0, end #while i<n
move $s3, $s2
add $s3, $s3, $s2
sll $s3, $s3, 1
lw $t0, symbol($s3) #load symbol of the current array number
beq $t0, $zero, storearray #store array value
addi $s2, $s2, 1 #i++
blt $s2, $s0, always2
j end
storearray:
move $s4, $s1
add $s4, $s4, $s1
sll $s4, $s4, 1
addi $t2, $s2, 1 #set array number to i+1
sw $t2, array($s4)
addi $t2, $zero, 1
sw $t2, symbol($s3) #set the symbol of the current array number to 1
sub $sp, $sp, 12
sw $ra, 0($sp) #save $ra
sw $s1, 4($sp) #save index
sw $s2, 8($sp)
addi $s1, $s1, 1 #index + 1
jal fullarray
lw $s1, 4($sp)
lw $s2, 8($sp)
lw $ra, 0($sp)
add $sp, $sp, 12
move $s4, $s1
add $s4, $s4, $s1
sll $s4, $s4, 1
move $s2, $s1
move $s3, $s2
add $s3, $s3, $s2
sll $s3, $s3, 1
sw $zero, symbol($s3) #set the symbol of current array number to 0
addi $s2, $s2, 1 #i++
blt $s2, $s0, always2
beq $s1, $zero, end
jr $ra
end:
示例预期输出为：
（输入=4）
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
等
但我的代码总是 return 给我
1 2 3 4
1 2 4 3
1 2 4 3
1 2 4 3
...
1 2 4 3
请帮忙！
建议从头再来写一遍
您当前的MIPS代码使用s0, s1, ...作为全局变量，这对于非递归代码来说是非常合理的，但是递归通常基于local/functional编写代码的方式。
而你的错误来自滥用 s# 寄存器，多次粗心地添加无用的指令和冗余计算，直到你最终不小心修改了一些你本来想保留的东西。
一些粗略的草图你可以如何（我会）组织代码：
main部分
初始化s0 = n，这个和"global variable"一样好用，不用改。
但之后尝试模仿C类函数调用fullArray(0);:
start:
# read N from user, set $s0 to N
...
# call recursive function fullarray with argument value 0
move $a0, $zero # first argument "index" = 0
jal fullarray # call the function (not jump)
li $v0,10 # exit syscall
syscall
这部分和你的类似，但是你用j而不是jal输入fullarray，所以你将很难终止整个代码，而原来的C算法将简单地从所有嵌套循环中 运行 和 return 到 main，不需要对 fullarray.
并且在跳入函数之前初始化函数的 LOCAL 变量。那应该已经 听起来 奇怪了，在编写源代码时尽量遵循 "locality" 原则，因为通常在源代码中写的东西正是它们属于/正在使用的地方。局部变量应该在函数内部初始化（并且接近它们的实际用法，前面的行不多）。当你知道你不会调用一些进一步的子程序时，你应该为本地人使用非保留的 $t# 寄存器，这会修改它们。
（这只是惯例，因为编写代码的程序员负责保存 $s# 寄存器，它们在物理上与 $t# 寄存器相同，CPU 不会它们之间有任何区别......但是有经验的 MIPS 汇编程序员在阅读源代码时会以不同的方式思考它们）
fullarray功能概览设计
让我们使用通用调用约定，其中 a0 包含函数参数，$ra 是 return 地址，函数不应修改 $s# 寄存器。
fullarray:
if (a0 "index" >= N) { print_array; return; }
preserve in stack: $ra (return address) and $s1 (will be modified)
for (s1 : all_possible_symbols) { // that's range 1..N
if (symbol s1 is used already) continue;
mark symbol s1 as used;
array[a0 "index"] = s1;
fullarray(index + 1); // <=> ++a0; jal fullarray; --a0;
// because symbol ("i" variable) is in $s1, it is still valid even here!
// (if function fullarray() is correct and preserves $s# registers)
// EDIT: in common convention function is allowed to modify a0,
// but this design expect it to be preserved! (sort of bug)
unmark symbol s1 (is unused now);
} //for(all symbols s1 on position "index")
restore $ra and $s1 and $sp
jr $ra
("edit" 发布前：实施时，我注意到我已经计划在头上保留 $a0 原因 simplicity/performance，但通用调用约定并不要求, 所以这是最后的自定义调用约定)
fullarray函数实现-先试试
让我有点奇怪，您已经拥有多少代码，虽然听起来很简单。现在我会像这样在第一个版本中将其重写为 asm：
（请注意，我对 array 和 symbol 使用 byte 数组，因为最大 N 仅为 7，因此无需使用 word 值，并且它简化了索引，不需要做 *4 来计算地址)
fullarray:
# extra requirement for this fullarray function: preserve also $a0!
# if (a0 "index" >= N) { print_array; return; }
bge $a0, $s0, print_array
# preserve in stack: $ra (return address) and $s1 (will be modified)
addi $sp, $sp, -8
sw $ra, 0($sp) #save return address
sw $s1, 4($sp) #preserve old $s1 value
# for (s1 : all_possible_symbols) { // that's range 1..N
# this will be actually do {} while() loop, because we know N is valid (the main should test input!)
move $s1, $zero # s1 = current symbol index, going from zero to N-1 (symbol = index+1)
symbol_loop:
#here: s0 = N, s1 = symbol index, a0 = array index
# if (symbol s1 is used already) continue;
lb $t0, symbol($s1)
bnez $t0, symbol_loop_advance
# mark symbol s1 as used (by N value, any non-zero value is good, N is non-zero and in $s0)
sb $s0, symbol($s1)
# array[a0 "index"] = s1;
addi $t0, $s1, 1 # t0 = symbol value (= symbol_index+1) (avoiding $s# usage for temporary)
sb $t0, array($a0) # array[a0] = symbol
# call fullrray(index+1) recursively
addi $a0, $a0, 1
jal fullarray
addi $a0, $a0, -1
# unmark symbol s1 (is unused now)
sb $zero, symbol($s1)
# end of for/do_while loop
symbol_loop_advance:
addi $s1, $s1, 1 # next symbol index
blt $s1, $s0, symbol_loop # while(symbol_index < N);
# restore $ra and $s1 and $sp ($a0 is also preserved, that's extra requirement)
lw $ra, 0($sp) #restore return address
lw $s1, 4($sp) #restore old $s1 value
addi $sp, $sp, 8
# return from function
jr $ra
print_array:
# extra requirement for this fullarray function: preserve also $a0!
#TODO printing (don't modify any $s# register, or $ra)
jr $ra # return
"fullarray:" 函数的核心（w/o 打印）大约有 20 条伪指令。您的核心部分有大约 40 条伪指令。但大多数情况下，每条指令都应该清楚地连接到原始 algorithm/intention，在 MIPS 汇编不允许单指令实现的情况下，只有最少的帮助指令（比如 if (symbol[i]) 必须首先从内存中获取值，然后它可以测试它）。
fullarray功能实现-改进建议
现在汇编主要是关于性能（有时用汇编编写代码的另一个好理由是代码的大小）。在 MIPS 上，代码的大小通常会直接影响性能。
如果您要检查该函数的反汇编，在本机 MIPS 指令中（在 MARS 中：编译后 "Execute" 选项卡中的 "Basic" 列），您会注意到 symbol 周围的部分/array 内存使用量确实大幅增长。在 MIPS 上加载地址不是微不足道的，你还有一些备用的 $s# 寄存器，所以你可以使用一些作为另一个全局值，只加载一次 symbol/array 地址，比如：
# somewhere in main before calling fullarray(0)
la $s6, symbol
la $s7, array
然后在函数内部您可以重用该值进行寻址：
# if (symbol s1 is used already) continue;
addu $t1, $s6, $s1 # t1 = symbol($s1)
lb $t0, ($t1)
bnez $t0, symbol_loop_advance
# mark symbol s1 as used (by N value, any non-zero value is good, N is non-zero and in $s0)
sb $s0, ($t1)
# array[a0 "index"] = s1;
addu $t1, $s7, $a0 # t1 = array($a0)
addi $t0, $s1, 1 # t0 = symbol value (= symbol_index+1) (avoiding $s# usage for temporary)
sb $t0, ($t1) # array[a0] = symbol
这将产生更少的本机 MIPS 指令 = 更小更快的代码。
另外，由于最大 N 为 7，您可以完全摆脱 symbol 数组，并使用存储在寄存器中的位图，通过特定位 set/unset 标记符号的使用（MIPS 寄存器是 32 位大，所以这很容易达到 N = 32）。
我会调整 +1 发生的位置（符号索引与屏幕上的符号），通常在 ASM/C 编程中你希望事情从 0 开始，到 N-1 结束，所以我会生成array 中的排列与符号 0..N-1，并在打印部分对人类 1..N 符号进行 +1 修复，只是重新格式化输出。
如果这是我的代码，我会将符号重命名为更有意义的名称，例如：
array = permutation
symbol = used_symbols
fullarray = permutate_position
print = show_permutation
print2 = show_permutation_symbol
...etc...
在用编程语言编写代码时，始终对其进行编辑，直到它读 好。想象你是一个程序员，他并没有编写原始源代码，而是需要帮助他的同事，或者修复其他人代码中的错误——以这种心态阅读你的代码，看看有什么不太清楚，有什么可以更好地注释（主要是 "intent" 代码的一小部分应该实现），functions/variables 的哪些名称有意义，代码需要更多白色 space 以更具可读性等.
在将源代码写入易于阅读的源代码的过程中投入时间会在调试和维护阶段 return 迅速。通常来源比写的多 read/edited 很多倍。
此外，我什至会更积极地 reuse/preserve 寄存器中的值，避免内存，避免递归（因为它根本不需要这个任务，它甚至使它变得更难)。我会以这样的代码结束：
我写的会是什么样子
.eqv MAX_N, 8 # 8 will work at most (BTW, that's ~40k of permutations)
.data
permutation: .space MAX_N
# must follow in memory the permutation array directly, at +MAX_N offset, do not move it
symbol_masks: .space MAX_N # current symbol mask per position in "permutation" array
input_N_prompt: .asciiz "Enter N (permutation size, 1..7): "
.text
start:
li $v0, 4
la $a0, input_N_prompt
syscall # display input prompt
li $v0, 5
syscall # read integer from user
# validate N (1 <= N <= MAX_N)
blez $v0, start
bgt $v0, MAX_N, start
# initialize global "variables"
move $s0, $v0 # s0 = N
move $s1, $zero # s1 = symbols used (none) = bitmask, each symbol has one bit
la $s2, permutation # s2 = permutation.begin() address
addu $s3, $s2, $s0 # s3 = permutation.end() address
addi $s4, $zero, 1 # s4 = 1
move $t7, $s2 # t7 = current position in permutation (address)
symbol_loop_init_position:
# initialize current (position) symbol to 0 with mask 0x01
sb $zero, ($t7)
sb $s4, MAX_N($t7)
symbol_loop: # loops through all symbols for current position $t7
# will try if symbol at current position is valid
lb $t0, MAX_N($t7) # load bit mask of current symbol
and $at, $t0, $s1 # check usage
beq $at, $t0, advance_to_next_symbol # when used, advance to next symbol
# valid symbol in permutation found, mark symbol as used
or $s1, $s1, $t0
# advance to next position
addi $t7, $t7, 1
bne $t7, $s3, symbol_loop_init_position
# permutation is complete, display it
jal print_permutation
# after print continue with "symbol_loop_retreat" logic (back to valid position)
symbol_loop_retreat: # current position "exhausted" in search (or printed), retreat
beq $t7, $s2, all_permutations_printed # retreating from first position => end
addi $t7, $t7, -1 # retreat one position back
lb $at, MAX_N($t7)# load bitmask of current symbol at current position
xor $s1, $s1, $at # unmark the currently used symbol
# and try next symbol for new (previous) current position
advance_to_next_symbol:
lb $at, ($t7)
addi $at, $at, 1 # advance to next symbol value
beq $at, $s0, symbol_loop_retreat # symbol == N -> retreat to previous position
sb $at, ($t7) # store next symbol into permutation
lb $at, MAX_N($t7)
sll $at, $at, 1 # advance also symbol bitmask
sb $at, MAX_N($t7)
j symbol_loop # and try it in permutation, if the new symbol is valid
all_permutations_printed:
# terminate execution
li $v0, 10
syscall
# not a general subroutine, using known registers heavily, modifies only v0, a0 (t7 = s3 at end (again))
print_permutation:
move $t7, $s2 # permutation.begin() address for display loop
print_permutation_loop:
# print one symbol from permutation
move $v0, $s4 # v0 = 1 (print integer)
lb $a0, ($t7) # load permutation symbol (in 0..N-1 value)
add $a0, $a0, $s4 # do +1 to make it "human" formatted 1..N value
syscall
# print single space character
li $v0, 11
li $a0, ' '
syscall
# loop until all symbols were printed
addi $t7, $t7, 1 # ++address of current symbol
bne $t7, $s3, print_permutation_loop
# print newline character
li $v0, 11
li $a0, '\n'
syscall
jr $ra # return
写完之后，其实非递归版本的控制流程比较难理解，写了挺费时间的，还好第一次尝试成功了，就不用debug了（但这就是为什么我花了很多时间来写它，大概大约 2 小时，直到我设法清理它，使它有意义并很好地组合在一起。
但是从性能的角度来看，这是200B左右的长代码，你的是350B左右。此外，执行的指令总量会少得多，因为我在内存中只保留 storing/restoring 符号及其使用位掩码，而不是接触堆栈。 （尽管使用 "print integer" 控制台的输出实际上会使它与您的原始代码一样慢......如果我考虑任务的 "print" 部分 - 我只认为排列生成器是主要焦点 -我会更改排列生成器以直接生成整行字符串，改变 ASCII 字母本身，而不是整数元素，这将消除 "print integer" 调用的需要，这是迄今为止执行的最复杂的代码（不幸的是隐藏在 MARS 中模拟器实现，不是在 MIPS 汇编中创建的，因此您无法在调试器中查看将整数值打印为字符串需要多少努力）。
它仍然可以缩短几个字节，但我尽量保持它的可读性，这样你就有机会通读它，并理解它是如何工作的。它应该有点棘手，希望使用您可能不知道或尚未使用的几个概念（例如位设置为 store/check 哪些符号是 used/unused，使用内存地址而不是主循环的索引值等...）。当然它不是递归的，所以你不能提交它作为你的 class 的解决方案......修复你的，它与我的 "first try" 示例和调试器一起并不那么困难。
（还有一件事.. 关于 $at 寄存器的使用...宁可不要那样做，如果你不是 100% 确定如何安全地做到这一点，基本上你必须知道哪些指令是本机的MIPS 并且是伪指令，因为它们经常使用 $at 寄存器进行中间计算，因此使用 $at 获取某些值的代码将在意外使用某些伪指令时中断......我是使用 $at 作为部分有趣的挑战，让它变得更复杂，我不会在一些严肃的生产代码中。）
关于你的原始代码的另一件事，我忘记提到了，但这表明你理解了这个概念，但需要练习才能获得更多技能（别担心，它与你编写的代码量有关, 需要时间):
这样的代码：
move $s3, $s2
add $s3, $s3, $s2
sll $s3, $s3, 1
本质上是在做 s3 = s2*4，但是以复杂的方式：s3 = s2, s3 += s2 (that's s2*2), s3 <<= 1 (s3 = s3*2).
在 MIPS 上可以用一条指令完成：
sll $s3, $s2, 2 # s3 = s2 * 4 (by shifting s2 value 2 bits left)
这是您的主要错误的部分原因，因为您一直为此使用多个寄存器，直到您不小心也 "i" 进行了更改（当您可以通过一条指令简单地设置一个临时寄存器时）。