add $t0, $t0, $zero # i = 0
不,它保持$t0
不变,保留它以前做过的任何垃圾。也许您打算使用addi $t0, $zero, 0
?
此外,MIPS 没有 2 寄存器寻址模式(用于整数加载/存储),只有16-bit-constant ($reg)
. $t5($s2)
是不合法的。您需要单独的addu
指令,或者更好的是指针增量。
(您应该使用指针数学addu
来代替add
;如果地址计算从地址空间的低半部分跨越到高半部分,这不是错误。)
在 C 中,另一个线程在您编写对象时读取它是未定义的行为,因此我们可以优化外部循环的实际循环。 除非类型D
是_Atomic int *D
or volatile int *D
,但问题中没有指定。
无论外部循环计数器如何,内部循环每次都写入相同的元素,因此我们可以优化外部循环,只进行最后的外部迭代,使用i = a-1
. 除非a <= 0
,那么我们必须跳过外部循环体,即什么也不做。
将除最后一个商店之外的所有位置优化到每个位置称为“死店消除”。早期外循环迭代中的存储是“死的”,因为它们被覆盖而没有读取它们的值。
您通常希望将循环条件放在循环的底部,因此循环分支就是一个bne $t0, $t1, top_of_loop
例子。(MIPS 具有bne
本机硬件指令;blt
除非第二个寄存器是 ,否则它只是伪指令$zero
。)所以我们想要优化j<b
到,j!=b
因为我们知道我们在向上计数。
在循环之前放置一个条件分支以检查它是否可能需要运行零次。例如blez $s0, after_loop
跳过内部循环体 if b <= 0
。
asm 中的惯用for(i=0 ; i<a ; i++)
循环在 C 中看起来像这样(或对此的一些变体)。
if(a<=0) goto end_of_loop;
int i=0;
do{ ... }while(++i != a);
或者如果i
没有在循环内使用,那么i=a
和do{}while(--i)
。(即添加-1
和使用bnez
)。尽管 MIPS 可以像在 上一样有效地进行分支i!=a
,但i!=0
与大多数具有 FLAGS 寄存器的架构不同,其中倒计时可以保存比较指令。
D[4*j]
意味着我们在一个字数组中跨过 16 个字节。分别使用乘以 4 和移位 2 是疯狂的多余。只需将指针保存在单独的寄存器中,每次迭代将其递增 16,就像 C 编译器一样。
我们不知道 的类型D
或任何其他变量。如果它们中的任何一个是窄无符号整数,我们可能需要实现 8 位或 16 位截断/换行。
但是您的实现假设它们都是int
or unsigned
,所以让我们这样做。
我假设一个没有分支延迟槽的 MIPS,就像 MARS 默认模拟的那样。
i+j
a-1
从设置最终值的最后一个外循环迭代开始(j=0) 。它运行到j=b-1
,所以最大值是a-1 + b-1
。
在编写任何 asm之前,将问题简化为我们需要存储的值以及需要存储它们的位置,这意味着我们编写的 asm 更简单,更容易调试。
您可以通过在 C 源代码中进行这些转换并使用 C 中的单元测试进行检查来检查大多数转换的有效性。
# int a: $s0
# int b: $s1
# int *D: $s2
# Pointer to D[4*j] : $t0
# int i+j : $t1
# int a-1 + b : $t2 loop bound
blez $s0, EXIT # if(a<=0) goto EXIT
blez $s1, EXIT # if(b<=0) goto EXIT
# now we know both a and b loops run at least once so there's work to do
addiu $t1, $s0, -1 # tmp = a-1 // addu because the C source doesn't do this operation, so we must not fault on signed overflow here. Although that's impossible because we already excluded negatives
addu $t2, $t1, $s1 # tmp_end = a-1 + b // one past the max we store
add $t0, $s2, $zero # p = D // to avoid destroying the D pointer? Otherwise increment it.
inner: # do {
sw $t1, ($t0) # tmp = i+j
addiu $t1, $t1, 1 # tmp++;
addiu $t0, $t0, 16 # 4*sizeof(*D) # could go in the branch-delay slot
bne $t1, $t2, inner # }while(tmp != tmp_end)
EXIT:
我们本可以在存储之前先完成增量,然后使用a-2
anda+b-2
作为 and 的初始化tmp
器tmp_end
。在一些真正的流水线/超标量 MIPS CPU 上,最好避免将增量放在bne
读取它之前。(将指针增量移动到分支延迟槽后)。当然,您实际上会展开以节省工作,例如使用sw $t1, 16($t0)
and 32($t0)
/ 48($t0)
。
再次在具有分支延迟的真正 MIPS 上,您将移动一些 init$t0..2
以填充早期输出blez
指令中的分支延迟槽,因为它们不能相邻。
如您所见,您的版本至少可以说过于复杂。问题中没有说我们必须将每个 C 表达式分别音译为 asm,而 C 的全部意义在于允许这样优化的“as-if”规则。