优化此汇编代码

Question

我现在正在学习计算机体系结构课程,我们正在讨论基本的R-type和I-type指令(也就是RISC架构)等等.我似乎无法弄清楚如何优化这个码.

说明:此代码在数组中添加单词(由$ s1指向),直到达到零.结果存储在$ t1中.$ t0保留当前单词.

        add   $t1, $zero, $zero      # Initialize result to zero
again:  
        lw    $t0, 0($s1)            # Load the word from the array
        beq   $t0, $zero, done       # Terminate if current word is a zero
        add   $t1, $t1, $t0          # Add current word to result
        addi  $s1, $s1, 4            # Point to the next word in the array
        beq   $t1, $t1, again        # Loop again
done:
        nop                          # Do nothing

我很难优化代码.我觉得beq $t1, $t1, again(因为它总是如此)是不必要的,但我不知道如何删除它.这是我的尝试,但我现在意识到我的代码不会终止.

        add   $t1, $zero, $zero      # Initialize result to zero
again:  
        lw    $t0, 0($s1)            # Load the word from the array
        add   $t1, $t1, $t0          # Add current word to result
        addi  $s1, $s1, 4            # Point to the next word in the array
        bne   $t1, $zero, again      # If result is not zero, loop
done:
        nop                          # Do nothing

我永远不会检查终止零点并跳转完成.但是,如果我添加另一个检查,那么代码不会像以前一样吗？

Answer 1

通常，您希望将顶部循环的测试转换为底部循环的测试。为此，您经常必须（或多或少）跳到循环体的中间进行第一次迭代。在伪代码中，你现在所拥有的基本上是：

    initialize sum
beginning:
    load a word
    if (done) goto end
    add to sum
    increment pointer
    goto beginning
end:

为了优化它，我们希望将结构更改为如下所示：

    initialize sum
    goto start_loop

beginning:
    add to sum
    increment pointer
start_loop:
    load a word
    if (!done) goto beginning

这样，每个循环只有一次跳转，而不是两次（这是一个短的向后跳转，因此目标几乎总是在缓存中）。

也就是说，我应该补充一点，这种优化实际上基本上已经过时了——通过良好的分支预测，无条件跳转通常基本上是免费的。

编辑：既然已经提到了循环展开，我将添加我的两分钱。分支预测通常会使循环展开变得过时，除非您可以使用它来并行执行更多指令。这在这里不是问题，但在现实生活中通常很有用。例如，如果我们假设 CPU 有两个单独的加法器可用，我们可以展开循环的两次迭代，并将这些迭代的结果添加到两个单独的目标寄存器中，因此我们通过同时添加两个值来利用两个加法器时间。然后，当循环终止时，我们将这两个寄存器相加以获得最终值。在类似 C 的伪代码中，结果会是这样的：

odds = 0
evens = 0

do {   
    evens += pointer[0];
    odds += pointer[1];
    pointer += 2;
while (pointer[0] && pointer[1]);
total = odds + evens;

正如所写，这增加了一些额外的要求，即两个连续的零（而不是仅一个）来终止序列，并且在数组中至少添加两项。但请注意，真正提供主要优势的并不是循环展开，而是并行执行。

如果没有这一点，我们实际上只有在未采用的分支比采用的分支便宜的情况下才能看到循环展开的好处（即使两者都被正确预测）。在较旧的处理器（例如，较旧的英特尔）上，采用分支确实会相对于未采用的分支带来惩罚。同时，展开的循环将使用更多的缓存空间。因此，在现代处理器上，这通常是整体损失（除非，正如我之前所说，我们可以使用展开来获得并行性）。