c - While 循环遍历数组，MIPS 汇编

Question

我想将 while (w[i] == x) i += j; 转换为 MIPS 汇编代码。假设整数 i、j 和 x 分别在 $3、$4 和 $5 中。还假设在 while 循环之前最初 i=0。w => 整数数组，其基地址存储在 $6 中。到目前为止我已经有了这个。

Loop:
    sll $10, $3, 2    # $10 = i* 4
    add $10, $6, $10  # $10 has address of w[i]
    lw  $11, 0($10)   # $11 = w[i]
    bne $11, $5, Exit # exit from loop if w[i]!= x
    add $3,  $3, $4   # i= i+ j
    j Loop
Exit:

是否可以通过将基址本身移动 j*4 来优化此代码，并摆脱多个分支指令？因为我不知道如何做到这一点。

提前致谢!

Answer 1

要摆脱多分支指令，可以使用以下技巧:
警告:与您的代码不完全相同

Loop:
    sll $10, $3, 2    # $10 = i* 4
    add $10, $6, $10  # $10 has address of w[i]
    lw  $11, 0($10)   # $11 = w[i]
    add $3,  $3, $4   # i = i + j
    beq $11, $5, Loop # keep looping if w[i] == x
Exit:
    sub $3,  $3, $4   # i = i - j

诀窍是在测试是否保持循环之前执行i += j。
有时，这确实会带来一个问题:它可能会触发额外的整数溢出，而您的代码却不会。

编辑:

这就像重写这个:

while (some_condition())
    do_something();

进入此:

do
    do_something();
while (some_condition());
undo_something();

编辑:

好吧，这次让我尝试“将指针从基地址本身移动 j*4”:)

Start:
    sll $11, $3, 2    # $11 = i * 4
    add $10, $11, $6  # Let $10 be a "cursor" pointing to w[i]        
Loop:
    lw  $11, 0($10)   # $11 = w[i]
    sll $12, $4, 2    # $12 = j * 4
    add $10, $10, $12 # update $10 by 4 * j
    add $3,  $3, $4   # update i by j
    beq $11, $5, Loop # keep looping if w[i] == x
Exit:
    sub $3,  $3, $4   # i = i - j

但是它并不比我上面给出的版本更优化:它们都在循环体内使用了 5 条指令。