从 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 ,,0xffff
  addiu ,,-1
  addu ,,
  sltu ,,
  beq ,[=11=],$L2
  andi ,,0xffff

  move ,
$L4:
  lbu ,0()
  lbu ,1()
  sll ,,8
  addu ,,
  andi ,,0xffff
  addu ,,
  andi ,,0xffff
  addiu ,,2
  sltu ,,
  sltu ,,
  beq ,[=11=],$L3
  addiu ,,1

  andi ,,0xffff
$L3:
  bne ,[=11=],$L4
  nor ,[=11=],

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

$L9:
  j 
  nop

$L8:
  lbu ,0()
  nop
  sll ,,8
  addu ,,
  andi ,,0xffff
  sltu ,,
  beq ,[=11=],$L9
  nop

  addiu ,,1
  j 
  andi ,,0xffff

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

Compiler Explorer 显示该部分与 while 有关，但我不明白为什么它在 $L2.

中的分支之前操作

Answer 1

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

Initial parameters:
    : sum  parameter
    : data parameter
    : len  parameter

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

Registers:
    : sum
    : dataptr
    : last_byte

相关代码：

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

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

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

    nor ,[=11=],      //  =  (data) nor 0

    addu ,,     //  +=  (last_byte)

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

    addu ,,     //  += 

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

while 循环在 [1] 处结束。其余说明直到 [2] 计算一个值到寄存器 </code> 以与 <code> (last_byte) 进行比较，即源码中的if

这里的问题是：</code>中的值是多少？如果你把所有的操作放在一起，你会得到： <pre><code> = + ((((( nor 0) + ) >> 1) + 1) << 1)

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

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

所以它只是在 </code> 上取反（补码）。 然后，它添加<code>，即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)

最后，它添加 </code> 的原始值，即 <code>data 参数。

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

 = data + next_even(~data + last_byte)

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

x - y == x + ~y + 1

因此：

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

现在，减去2后计算下一个偶数，基本上就是去掉最低位的信息；换句话说，"floor" 到偶数。这可以表示为如果是偶数则返回相同的数，如果是奇数则减一，即：

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

最后，编译器将此寄存器与</code> (<code>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。

编译器使用所有这些指令有效地从 data 和 last_bytes 重新计算 dataptr。实际上，如果您认为 dataptr 仅以 2 的增量从 data 前进，我们可以将其重写为：

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

这正是上面计算的 </code> 的值。 知道这一点，人们可能想知道为什么编译器会得出这个解决方案。最新版本的 GCC (8.1.0) 和 x86-64 也会发生同样的情况： <pre><code>mov rdx, rsi not rdx add rdx, r8 shr rdx lea rsi, [rsi+2+rdx*2]

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

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

Understanding MIPS assembly code from C compiler

c

assembly

compilation

reverse-engineering

mips