B[49345]=A[3][i-j]
假设 i
和 j
分别在寄存器 $s0
和 $s1
中,如何编写与此表达式对应的高效 MIPS 汇编代码?
我的实现是这样的
sll $t0,$s0,2
sub $t0,$t0,$s1
sll $t0,2
lw $t1,12($t0)
add $t1,$s2,$t0
lw $t1,12($t0)
li $t2,49345
sll $t2,2
add $s3,$s3,$t2
sw $t1,0($s3)
数组声明:
int A[5][20];
int B[50000];
如果我在这里做错了什么,请告诉我。
您正在计算
i*4-j
,这不是规定的 C 表达式,它实际上想要 i-j
— 该子表达式 i-j
具有比任何隐式缩放更高的优先级,因此必须在之前计算(并且作为输入到)缩放。
对于二维数组,由于这是一个矩形数组,所以只需要一次(内存访问)加载,剩下的都是地址计算。
对于
int A[5][20]
,我们每行有5行20*sizeof(int)=80
字节。因此,A[3] 指的是数组的基地址 + 80*3
元素——然后按 i-j
缩放量对其进行索引。
如果两个索引都是变量表达式(而不是一个是常量),我们可能会计算
(80*3 + i-j)*4
以便在索引计算结束时仅缩放 (*4
) 一次。但是,由于第一个索引是常量,我们可以将 (distribute) 重构为 80*3*4 + (i-j)*4 = 960 + (i-j)*4
。这样做的原因是我们可以使用 960(在您使用 12 的地方)。因此,计算 (i-j)*4 + base
,然后使用 960 作为 lw
中的偏移量。
我们必须知道哪些寄存器引用了
A
和B
,或者只是将它们加载到寄存器中,你没有说也没有加载它们但我想我们应该推断出$s2
和$s3
来自您的代码。
如果我们假设
B
在 $s3
中,那么您正在改变它,这可能会也可能不会,但如果我是一名讲师,我会指出来。您正在计算 B = B+49345*4
(又名 B += 49345*4
)——我在这里使用 B
来表示 $s3
——所以 $s3
不再指代 B[0]
,这可能会弄乱同一函数中的后续代码如果有任何依赖$s3
访问/索引数组B
。建议将索引加上基数总和计算到一个新的/不同的寄存器(并在sw
中使用它),这样你就可以保持$s3
不变。
当处理小于整个函数的代码片段时,最好不要对周围的代码假设太多,并且可能应该考虑到您不能随意修改参数或给定的寄存器,因此这适用于
i
的寄存器, j
、A
和 B
。在一个完整的可编译函数的上下文中,我们可以通过进一步查看函数中这些变量的使用来确定我们是否可以自由覆盖这些寄存器。
可能的优化
您有一个 4 指令序列要存储到
B
中,就像在作业 B[49345]=
中一样。正如 Peter 所说,我们可以通过使用 sw
指令的偏移量来缩短一条指令——对于 MIPS 上的每条加载和存储指令,我们都会免费添加一个较小的常量(因此我们尽可能使用它,而当我们使用 0 时我们找不到合适的小常量)。
一种方法是计算值
49345*4 = 197,380 = 0x00030304
,然后将其分成两个 16 位的一半,并在 lui
指令中使用高 16 位一半 (0x0003) 和低 16 位一半 (0x0304 = 772 基数 10) 在 sw
指令中。 lui
使用 0x0003 作为立即数,只需将 0x00030000 加载到某个临时寄存器(您的选择)中。然后从 B
添加 $s3
的基数,然后使用 sw
存储你想要写入内存的值,使用你选择的寄存器,以及低 16 位值 0x0304 aka 772。这就是一个 3指令序列,lui
,addu
,sw
.
(精明的读者可能会意识到
lw
和 sw
的常数是符号扩展的,所以如果使用的 16 位立即数是负数,我们必须将 lui
中使用的常数偏移 1,以便添加-1 来自符号扩展将得到所需的地址。这在这里不是问题,因为 lw
和 sw
中使用的常量都是正的 16 位立即数。)