使用循环展开计算正数、负数和零数的最有效方法
The most efficient way of counting positive, negative and zero number using loop unrolling
假设我有以下指令，只需检查一个数字是否为正数（负数或零），如果它是正数，则将 1 添加到我们的计数器（我们不关心数字是负数还是零).我可以通过一个简单的循环展开来做到这一点：
Loop:
mrmovq (%rdi), %r10 # read val[0] from src
andq %r10, %r10 # val[0] <= 0?
jle Npos1 # if so, goto Npos:
iaddq , %rax # count++
Npos1:
mrmovq 8(%rdi), %r11 # read val[1] from src+8
andq %r11,%r11 # val <= 0?
jle Npos2 # if so, goto next npos:
iaddq , %rax
Npos2:
mrmovq 16(%rdi), %r11 # read val[2] from src+8
andq %r11,%r11 # val <= 0?
jle Npos3 # if so, goto next npos:
iaddq , %rax
我的问题是，如果我还想检查是否为零或负数，我如何才能获得同样有效的结构。在这种情况下，我将有三个计数器（一个用于 pos，一个用于 neg，一个用于零）
一种低效的方法是这样的。我试图制作与前面示例相同的结构（我们在 %rax 中存储正数，在 %rbx 中存储负数，在 %rcx 中存储零）：
Loop: mrmovq (%rdi), %r10 # read val from src...
andq %r10, %r10 # val <= 0?
jle Npos # if so, goto Npos:
irmovq , %r11
addq %r11, %rax # Count positives in rax - count_pos++
jmp Rest
Npos: andq %r10, %r10 # Not positive
je Zero
irmovq , %r11
addq %r11, %rbx # Count negatives in rbx - count_neg++
jmp Rest
Zero: irmovq , %r11
addq %r11, %rcx # Count zeroes in rcx - count_zero++
Rest: irmovq , %r10
subq %r10, %rdx # len--
irmovq , %r10
addq %r10, %rdi # src++
addq %r10, %rsi # dst++
andq %rdx,%rdx # len > 0?
jg Loop # if so, goto Loop:
update：看到非分支版本的最后，应该 much 更好，而且展开起来很简单。但是剩下的答案仍然值得一读，IMO。
我确实找到了一种方法来保存每个测试值执行的几条指令，并展开，但与我使用循环尾复制的优化版本所管理的相比，它非常小。 （见下文）。
在很多情况下，与真实架构相比，y86 过于精简，无法提供高效的代码。一方面，似乎没有一种方法可以在不破坏标志的情况下有条件地增加。 （x86 有 lea rax, [rax+1]）。
我看不出有什么方法可以通过只计算正数和零，并在循环后计算负数来节省大量指令。您仍然需要分支来测试每个值。 更新：不，你不需要，因为你可以使用 y86 的 cmov!
来模拟 x86 的 setcc
不过，我确实在您的代码中发现了几项重大改进：
重复使用第一次测试设置的标志，而不是重新测试
另一件重要的事情是将 %r11 = 1 提升到循环之外，这样你就可以只增加一个 insn。即使在实际代码中，在寄存器中设置常量也是一件很常见的事情。大多数 ISA（包括 RISC 加载存储机器）都有立即添加指令，如 x86 的 add , %rax，但 y86 没有，因此它需要这种技术，即使是增量（x86 inc %rax）！
sub 设置标志，因此使用它们而不是进行单独的测试。
风格问题：
有了描述性的标签名称，您就不需要那么多评论了。
此外，将您的操作数缩进到一致的列，而不仅仅是可变长度助记符后的单个 space。它更具可读性。我喜欢减少分支目标的缩进，使它们脱颖而出，但这段代码中有太多分支，实际上看起来很难看：/
irmovq , %r11 # hoisted out of the loop
irmovq , %r8
Loop: mrmovq (%rdi), %r10 # read val from src...
andq %r10, %r10 # set flags from val
jle not_positive
addq %r11, %rax # Count positives in rax - count_pos++
jmp Rest
not_positive:
je Zero # flags still from val
addq %r11, %rbx # Count negatives in rbx - count_neg++
jmp Rest
Zero:
addq %r11, %rcx # Count zeroes in rcx - count_zero++
Rest:
addq %r8, %rdi # src+=8
//addq %r8, %rsi # dst++ // why? Not used... Also note that si stands for source index, so prefer keeping src pointers in rsi, and dest pointers in rdi for human readability.
subq %r11, %rdx # len--, setting flags
jg Loop # } while( len-- > 1). fall through when rdx=0
循环尾重复：
您可以增加代码大小，但可以通过复制循环尾减少实际 运行 的指令数。
我还重构了循环，因此循环体中每次迭代只有一个分支。
irmovq , %r11 # hoisted out of the loop
irmovq , %r8
Loop: mrmovq (%rdi), %r10 # read val from src...
addq %r8, %rdi # src+=8 for next iteration
andq %r10, %r10 # set flags from val
je Zero
jl Negative
# else Positive
addq %r11, %rax # Count positives in rax - count_pos++
subq %r11, %rdx
jg Loop
jmp end_loop
Negative:
addq %r11, %rbx # Count negatives in rbx - count_neg++
subq %r11, %rdx
jg Loop
jmp end_loop
Zero:
addq %r11, %rcx # Count zeroes in rcx - count_zero++
subq %r11, %rdx # len--, setting flags
jg Loop # } while( len-- > 1). fall through when rdx=0
end_loop:
展开并没有太多好处，因为循环体太大了。如果你这样做了，你可能会这样做：
请注意，我们每次迭代只更新和检查一次 len。这意味着我们需要一个清理循环，但一次只递减和检查一个将大大破坏展开的目的。
由两个展开，尾部重复
irmovq , %r11 # hoisted out of the loop
irmovq , %r12
irmovq , %r8
sub %r12, %rdi
jl end_loop # unrolled loop requires len >= 2
Loop: mrmovq (%rdi), %r10 # read val from src...
mrmovq 8(%rdi), %r9 # read next val here so we don't have to duplicate this
addq %r8, %rdi # src+=16 for next iteration
andq %r10, %r10 # set flags from val
je Zero1
jl Negative1
# else Positive1
addq %r11, %rax # Count positives in rax - count_pos++
andq %r9, %r9 # set flags from val2
je Zero2
jl Negative2
Positive2:
addq %r11, %rax # Count positives in rax - count_pos++
subq %r12, %rdx # loop tail
jge Loop
jmp end_loop
Negative1:
addq %r11, %rbx # Count negatives in rbx - count_neg++
andq %r9, %r9 # set flags from val2
je Zero2
jg Positive2
Negative2:
addq %r11, %rbx # Count negatives in rbx - count_neg++
subq %r12, %rdx # loop tail
jge Loop
jmp end_loop
Zero1:
addq %r11, %rcx # Count zeroes in rcx - count_zero++
andq %r9, %r9 # set flags from val2
jg Positive2
jl Negative2
Zero2:
addq %r11, %rcx # Count zeroes in rcx - count_zero++
subq %r12, %rdx # len-=2, setting flags
jge Loop # fall through when rdx=-1 or -2
end_loop:
# loop epilogue to handle cases where there was an odd number of elements, so rdx=-1 here:
add %r12, %rdx
jne all_done
#else there's one more to do
#... load and test a single element
如果我的循环条件或其他情况出现差一错误，我不会感到惊讶。
就像 Jester 在评论中指出的那样，x86 可以用
计算负数
sar , %r10 # broadcast the sign bit to all bits: -1 or 0
sub %r10, %rbx # subtracting -1 (or 0): i.e. add 1 (or 0)
更新：使用 cmov 模拟 setcc 的非分支版本
我们可以使用 cmov 将寄存器设置为 0 或 1，然后将其添加到我们的计数中。这避免了所有分支。 （0 是加法恒等式。此基本技术适用于任何具有恒等式元素的运算。例如，全一是 AND 的恒等式元素。1 是乘法的恒等式元素。）
展开这很简单，但是与需要重复的 8 条指令相比，循环开销有 3 条指令。收益会很小。
irmovq , %r11 # hoisted out of the loop
irmovq , %r8
mov %rdx, %rbx # neg_count is calculated later
Loop: mrmovq (%rdi), %r10 # read val from src...
addq %r8, %rdi # src+=16 for next iteration
andq %r10, %r10 # set flags from val
irmovq [=14=], %r13
cmovg %r11, %r13 # emulate setcc
irmovq [=14=], %r14
cmove %r11, %r14
add %r13, %rax # pos_count += (val > 0)
add %r14, %rcx # zero_count += (val == 0)
subq %r11, %rdx # len-=1, setting flags
jg Loop # fall through when rdx=0
end_loop:
sub %rax, %rbx
sub %rcx, %rbx # neg_count = initial_len - pos_count - zero_count
如果分支（尤其是不可预测的分支）很昂贵，这个版本会做得更好。在这种情况下，使用 Jester 的建议从其他两个计算其中一个计数有很大帮助。
这里有很好的指令级并行性。一旦测试结果准备好，两个单独的 setcc -> 添加依赖链可以 运行 并行。
假设我有以下指令，只需检查一个数字是否为正数（负数或零），如果它是正数，则将 1 添加到我们的计数器（我们不关心数字是负数还是零).我可以通过一个简单的循环展开来做到这一点：
Loop:
mrmovq (%rdi), %r10 # read val[0] from src
andq %r10, %r10 # val[0] <= 0?
jle Npos1 # if so, goto Npos:
iaddq , %rax # count++
Npos1:
mrmovq 8(%rdi), %r11 # read val[1] from src+8
andq %r11,%r11 # val <= 0?
jle Npos2 # if so, goto next npos:
iaddq , %rax
Npos2:
mrmovq 16(%rdi), %r11 # read val[2] from src+8
andq %r11,%r11 # val <= 0?
jle Npos3 # if so, goto next npos:
iaddq , %rax
我的问题是，如果我还想检查是否为零或负数，我如何才能获得同样有效的结构。在这种情况下，我将有三个计数器（一个用于 pos，一个用于 neg，一个用于零）
一种低效的方法是这样的。我试图制作与前面示例相同的结构（我们在 %rax 中存储正数，在 %rbx 中存储负数，在 %rcx 中存储零）：
Loop: mrmovq (%rdi), %r10 # read val from src...
andq %r10, %r10 # val <= 0?
jle Npos # if so, goto Npos:
irmovq , %r11
addq %r11, %rax # Count positives in rax - count_pos++
jmp Rest
Npos: andq %r10, %r10 # Not positive
je Zero
irmovq , %r11
addq %r11, %rbx # Count negatives in rbx - count_neg++
jmp Rest
Zero: irmovq , %r11
addq %r11, %rcx # Count zeroes in rcx - count_zero++
Rest: irmovq , %r10
subq %r10, %rdx # len--
irmovq , %r10
addq %r10, %rdi # src++
addq %r10, %rsi # dst++
andq %rdx,%rdx # len > 0?
jg Loop # if so, goto Loop:
update：看到非分支版本的最后，应该 much 更好，而且展开起来很简单。但是剩下的答案仍然值得一读，IMO。
我确实找到了一种方法来保存每个测试值执行的几条指令，并展开，但与我使用循环尾复制的优化版本所管理的相比，它非常小。 （见下文）。
在很多情况下，与真实架构相比，y86 过于精简，无法提供高效的代码。一方面，似乎没有一种方法可以在不破坏标志的情况下有条件地增加。 （x86 有 lea rax, [rax+1]）。
我看不出有什么方法可以通过只计算正数和零，并在循环后计算负数来节省大量指令。您仍然需要分支来测试每个值。 更新：不，你不需要，因为你可以使用 y86 的 cmov!
setcc
不过，我确实在您的代码中发现了几项重大改进：
重复使用第一次测试设置的标志，而不是重新测试
另一件重要的事情是将
%r11 = 1提升到循环之外，这样你就可以只增加一个 insn。即使在实际代码中，在寄存器中设置常量也是一件很常见的事情。大多数 ISA（包括 RISC 加载存储机器）都有立即添加指令，如 x86 的add , %rax，但 y86 没有，因此它需要这种技术，即使是增量（x86inc %rax）！sub设置标志，因此使用它们而不是进行单独的测试。
风格问题：
有了描述性的标签名称，您就不需要那么多评论了。
此外，将您的操作数缩进到一致的列，而不仅仅是可变长度助记符后的单个 space。它更具可读性。我喜欢减少分支目标的缩进，使它们脱颖而出，但这段代码中有太多分支，实际上看起来很难看：/
irmovq , %r11 # hoisted out of the loop
irmovq , %r8
Loop: mrmovq (%rdi), %r10 # read val from src...
andq %r10, %r10 # set flags from val
jle not_positive
addq %r11, %rax # Count positives in rax - count_pos++
jmp Rest
not_positive:
je Zero # flags still from val
addq %r11, %rbx # Count negatives in rbx - count_neg++
jmp Rest
Zero:
addq %r11, %rcx # Count zeroes in rcx - count_zero++
Rest:
addq %r8, %rdi # src+=8
//addq %r8, %rsi # dst++ // why? Not used... Also note that si stands for source index, so prefer keeping src pointers in rsi, and dest pointers in rdi for human readability.
subq %r11, %rdx # len--, setting flags
jg Loop # } while( len-- > 1). fall through when rdx=0
循环尾重复：
您可以增加代码大小，但可以通过复制循环尾减少实际 运行 的指令数。
我还重构了循环，因此循环体中每次迭代只有一个分支。
irmovq , %r11 # hoisted out of the loop
irmovq , %r8
Loop: mrmovq (%rdi), %r10 # read val from src...
addq %r8, %rdi # src+=8 for next iteration
andq %r10, %r10 # set flags from val
je Zero
jl Negative
# else Positive
addq %r11, %rax # Count positives in rax - count_pos++
subq %r11, %rdx
jg Loop
jmp end_loop
Negative:
addq %r11, %rbx # Count negatives in rbx - count_neg++
subq %r11, %rdx
jg Loop
jmp end_loop
Zero:
addq %r11, %rcx # Count zeroes in rcx - count_zero++
subq %r11, %rdx # len--, setting flags
jg Loop # } while( len-- > 1). fall through when rdx=0
end_loop:
展开并没有太多好处，因为循环体太大了。如果你这样做了，你可能会这样做：
请注意，我们每次迭代只更新和检查一次 len。这意味着我们需要一个清理循环，但一次只递减和检查一个将大大破坏展开的目的。
由两个展开，尾部重复
irmovq , %r11 # hoisted out of the loop
irmovq , %r12
irmovq , %r8
sub %r12, %rdi
jl end_loop # unrolled loop requires len >= 2
Loop: mrmovq (%rdi), %r10 # read val from src...
mrmovq 8(%rdi), %r9 # read next val here so we don't have to duplicate this
addq %r8, %rdi # src+=16 for next iteration
andq %r10, %r10 # set flags from val
je Zero1
jl Negative1
# else Positive1
addq %r11, %rax # Count positives in rax - count_pos++
andq %r9, %r9 # set flags from val2
je Zero2
jl Negative2
Positive2:
addq %r11, %rax # Count positives in rax - count_pos++
subq %r12, %rdx # loop tail
jge Loop
jmp end_loop
Negative1:
addq %r11, %rbx # Count negatives in rbx - count_neg++
andq %r9, %r9 # set flags from val2
je Zero2
jg Positive2
Negative2:
addq %r11, %rbx # Count negatives in rbx - count_neg++
subq %r12, %rdx # loop tail
jge Loop
jmp end_loop
Zero1:
addq %r11, %rcx # Count zeroes in rcx - count_zero++
andq %r9, %r9 # set flags from val2
jg Positive2
jl Negative2
Zero2:
addq %r11, %rcx # Count zeroes in rcx - count_zero++
subq %r12, %rdx # len-=2, setting flags
jge Loop # fall through when rdx=-1 or -2
end_loop:
# loop epilogue to handle cases where there was an odd number of elements, so rdx=-1 here:
add %r12, %rdx
jne all_done
#else there's one more to do
#... load and test a single element
如果我的循环条件或其他情况出现差一错误，我不会感到惊讶。
就像 Jester 在评论中指出的那样，x86 可以用
计算负数sar , %r10 # broadcast the sign bit to all bits: -1 or 0
sub %r10, %rbx # subtracting -1 (or 0): i.e. add 1 (or 0)
更新：使用 cmov 模拟 setcc 的非分支版本
我们可以使用 cmov 将寄存器设置为 0 或 1，然后将其添加到我们的计数中。这避免了所有分支。 （0 是加法恒等式。此基本技术适用于任何具有恒等式元素的运算。例如，全一是 AND 的恒等式元素。1 是乘法的恒等式元素。）
展开这很简单，但是与需要重复的 8 条指令相比，循环开销有 3 条指令。收益会很小。
irmovq , %r11 # hoisted out of the loop
irmovq , %r8
mov %rdx, %rbx # neg_count is calculated later
Loop: mrmovq (%rdi), %r10 # read val from src...
addq %r8, %rdi # src+=16 for next iteration
andq %r10, %r10 # set flags from val
irmovq [=14=], %r13
cmovg %r11, %r13 # emulate setcc
irmovq [=14=], %r14
cmove %r11, %r14
add %r13, %rax # pos_count += (val > 0)
add %r14, %rcx # zero_count += (val == 0)
subq %r11, %rdx # len-=1, setting flags
jg Loop # fall through when rdx=0
end_loop:
sub %rax, %rbx
sub %rcx, %rbx # neg_count = initial_len - pos_count - zero_count
如果分支（尤其是不可预测的分支）很昂贵，这个版本会做得更好。在这种情况下，使用 Jester 的建议从其他两个计算其中一个计数有很大帮助。
这里有很好的指令级并行性。一旦测试结果准备好，两个单独的 setcc -> 添加依赖链可以 运行 并行。