c - 从 C 编译器理解 MIPS 汇编代码

Question

我将 C 代码转换为 MIPS，但我无法理解 MIPS 指令的一部分:

#include <inttypes.h>
#include <stdint.h>

uint16_t
chksum(uint16_t sum, const uint8_t *data, uint16_t len)
{
    uint16_t t;
    const uint8_t *dataptr;
    const uint8_t *last_byte;

    dataptr = data;
    last_byte = data + len - 1;

    while (dataptr < last_byte)
    {
        t = (dataptr[0] << 8) + dataptr[1];
        sum += t;
        if (sum < t)
        {
            sum++;
        }
        dataptr += 2;
    }
    if (dataptr == last_byte)
    {
        t = (dataptr[0] << 8) + 0;
        sum += t;
        if (sum < t)
        {
            sum++;
        }
    }
    return sum;
}

我用了MIPS gcc5.4 on the Godbolt compiler explorer -O2 优化，经典 MIPS1 的默认 -march 没有加载互锁:

chksum(unsigned short, unsigned char const*, unsigned short):
  andi $6,$6,0xffff
  addiu $6,$6,-1
  addu $6,$5,$6
  sltu $3,$5,$6
  beq $3,$0,$L2
  andi $2,$4,0xffff

  move $4,$5
$L4:
  lbu $3,0($4)
  lbu $7,1($4)
  sll $3,$3,8
  addu $3,$3,$7
  andi $3,$3,0xffff
  addu $2,$3,$2
  andi $2,$2,0xffff
  addiu $4,$4,2
  sltu $3,$2,$3
  sltu $7,$4,$6
  beq $3,$0,$L3
  addiu $8,$2,1

  andi $2,$8,0xffff
$L3:
  bne $7,$0,$L4
  nor $3,$0,$5

  addu $3,$3,$6
  srl $3,$3,1
  addiu $3,$3,1
  sll $3,$3,1
  addu $5,$5,$3
$L2:
  beq $6,$5,$L8
  nop

$L9:
  j $31
  nop

$L8:
  lbu $3,0($6)
  nop
  sll $3,$3,8
  addu $2,$3,$2
  andi $2,$2,0xffff
  sltu $3,$2,$3
  beq $3,$0,$L9
  nop

  addiu $2,$2,1
  j $31
  andi $2,$2,0xffff

我将大部分指令与代码匹配，但我无法理解 $L3 中以 nor 指令开头的部分，直到 addu在 $L2 之前。

Compiler Explorer 显示该部分与 while 相关，但我不明白为什么它在 $L2 中的分支之前操作 $5 >.

Answer 1

让我们分析一下代码在做什么。一些映射使代码易于理解:

Initial parameters:
    $4: sum  parameter
    $5: data parameter
    $6: len  parameter

Labels:
    $L4: while body
    $L3: while condition
    $L2: if condition

Registers:
    $2: sum
    $4: dataptr
    $6: last_byte

相关代码:

    // [...]
    sltu $3,$5,$6     // $3 = $5 (data parameter) < $6 (last_byte) ? 1 : 0
    beq $3,$0,$L2     // if $3 == 0 goto $L2 (if condition)
    andi $2,$4,0xffff // $2 (sum) = $4 (sum parameter) & 0xFFFF
    move $4,$5        // $4 (dataptr) = $5 (data parameter)

$L4: // while body
    // [...]
    sltu $7,$4,$6     // $7 = $4 (dataptr) < $6 (last_byte) ? 1 : 0
    // [...]

$L3: // while condition
    bne $7,$0,$L4     // if $7 != 0 goto $L4 (while body) [1]

    nor $3,$0,$5      // $3 = $5 (data) nor 0

    addu $3,$3,$6     // $3 += $6 (last_byte)

    srl $3,$3,1       // $3 >>= 1
    addiu $3,$3,1     // $3++
    sll $3,$3,1       // $3 <<= 1

    addu $5,$5,$3     // $5 += $3

$L2: // if condition
  beq $6,$5,$L8       // if $6 (last_byte) == $5 goto $L8 [2]

while循环结束于 [1] .其余说明直到 [2] 计算一个值到寄存器 $5与 $6 进行比较( last_byte ), 这是 if在源代码中。

这里的问题是:$5 中的值是多少？ ？如果将所有操作放在一起，您会得到:

$5 = $5 + ((((($5 nor 0) + $6) >> 1) + 1) << 1)

让我们来解开这个表达式。首先，意识到:

x NOR 0 = NOT(x OR 0) = ~(x | 0) = ~x

所以它只是对 $5 求反(补码) .

然后，它添加 $6 ，即 last_byte .

接下来的 3 个操作(>> 1、+ 1、<< 1)是计算下一个偶数的方法。看看几个案例会发生什么:

0000 (0) -> 0010 (2)
0001 (1) -> 0010 (2)
0010 (2) -> 0100 (4)
0011 (3) -> 0100 (4)
0100 (4) -> 0110 (6)
0101 (5) -> 0110 (6)
0110 (6) -> 1000 (8)
0111 (7) -> 1000 (8)

最后，它添加了 $5 的原始值，这是 data参数。

如果将所有内容放在一起，并为清楚起见用 C 变量的名称替换，您将得出:

$5 = data + next_even(~data + last_byte)

回想一下，对于二进制补码整数:

x - y == x + ~y + 1

因此:

$5 = data + next_even(last_byte - data - 1)
   = data + next_even(len - 2)

现在，计算减去 2 后的下一个偶数基本上是删除最低位的信息；换句话说，偶数的“下限”。这可以表示为如果是偶数则返回相同的数，如果是奇数则减一，即:

$5 = data + (len % 2 ? len : len - 1)

最后，编译器将这个寄存器与 $6 进行比较(last_byte)。简化:

     last_byte == data + (len % 2 ? len : len - 1)
data + len - 1 == data + (len % 2 ? len : len - 1)
       len - 1 == len % 2 ? len : len - 1
       len % 2 != 0

现在我们也可以看到表达式实际上只依赖于len , 而不是 data .

使用所有这些指令的编译器正在有效地重新计算 dataptr来自 data和 last_bytes .事实上，如果你认为 dataptr仅从 data 前进以 2 为增量，我们可以将其重写为:

data + 2 * n_increments
data + 2 * (len / 2)
data + (len % 2 ? len : len - 1)

这正是 $5 的值以上计算。

知道了这一点，人们就会想知道为什么编译器会得出这个解决方案。 GCC (8.1.0) 和 x86-64 的最新版本也是如此:

mov rdx, rsi
not rdx
add rdx, r8
shr rdx
lea rsi, [rsi+2+rdx*2]

很明显，优化器正在意识到 dataptr 的最终值可以独立于 while 计算循环——但是，不清楚为什么它决定这样做而不是从寄存器中选取值。也许它已经决定避免对循环结果的依赖比其他方式更快(由于指令流水线)。