Понимание кода сборки MIPS от компилятора C - PullRequest
0 голосов
/ 12 мая 2018

Я конвертировал код 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 в проводнике компилятора Godbolt с *Оптимизация 1006 * со стандартным -march классического MIPS1, который не имеет блокировок загрузки:

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.

Проводник компилятора показывает, что часть связана с while, но я не понимаю, почему он манипулирует $5 до переходав $L2.

1 Ответ

0 голосов
/ 13 мая 2018

Давайте проанализируем, что делает код.Несколько сопоставлений, облегчающих выполнение кода:

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 цикл - однако, неясно, почему он решает сделать это вместо того, чтобы выбрать значение из регистра.Возможно, он решил, что избежать зависимости от результата цикла быстрее (из-за конвейерной обработки команд), чем в противном случае.

...