Как перевести оптимизированный цикл asm x86-64 обратно в цикл C for? - PullRequest
Новая
       58

Как перевести оптимизированный цикл asm x86-64 обратно в цикл C for?

0 голосов
/ 30 апреля 2019

У меня есть следующее: 

foo:
   movl $0, %eax                      //result = 0
   cmpq %rsi, %rdi                    // rdi = x, rsi = y?
   jle .L2

.L3:
   addq %rdi, %rax                    //result = result + i?
   subq $1, %rdi                      //decrement?
   cmp %rdi, rsi
   jl .L3

.L2
   rep
   ret

И я пытаюсь перевести это на: 

long foo(long x, long y)
{
    long i, result = 0;
    for (i=     ;               ;         ){

      //??

   }

 return result;
}

Я не знаю, что означает cmpq% rsi,% rdi.Почему нет другого & eax на долгое время?

Я хотел бы помочь в выяснении этого.Я не знаю, что мне не хватает - я просматривал свои заметки, учебники и остальную часть Интернета, и я застрял.Это обзорный вопрос, и я занимаюсь этим часами.

Ответы [ 2 ]

2 голосов
/ 30 апреля 2019

Предполагая, что это функция, принимающая 2 параметра. Предполагая, что это использует соглашение о вызовах gcc amd64, он передаст два параметра в rdi и rsi. В вашей функции C вы вызываете эти x и y. 

long foo(long x /*rdi*/, long y /*rsi*/)
{
    //movl $0, %eax
    long result = 0;  /* rax */

    //cmpq %rsi, %rdi
    //jle .L2
    if (x > y) {
        do {
            //addq %rdi, %rax
            result += x;

            //subq $1, %rdi
            --x;

            //cmp %rdi, rsi
            //jl .L3            
        } while (x > y);
    }

    return result;
}
1 голос
/ 01 мая 2019

Я не знаю, что означает cmpq %rsi, %rdi 1003 *

Это синтаксис AT & T для cmp rdi, rsi. https://www.felixcloutier.com/x86/CMP.html

Вы можете посмотреть детали того, что делает одна инструкция в руководстве по ISA.

Что еще более важно, cmp / jcc как cmp %rsi,%rdi / jl похоже на jump if rdi<rsi. Сборка - JG / JNLE / JL / JNGE после CMP . Если вы изучите все детали того, как cmp устанавливает флаги и какие флаги каждый jcc проверяет условия, вы можете убедиться, что это правильно, но на намного проще всего используйте семантическое значение JL = Jump on Less-than (при условии, что флаги были установлены cmp), чтобы запомнить, что они делают.

(Обратно из-за синтаксиса AT & T; предикаты jcc имеют правильное семантическое значение для синтаксиса Intel. Это одна из основных причин, по которой я обычно предпочитаю синтаксис Intel, но вы можете привыкнуть к синтаксису AT & T.)

Из-за использования rdi и rsi в качестве входных данных (чтение их без / до их записи), они являются проходящими через arg регистрами. Так что это соглашение о вызовах System V для x86-64, где целочисленные аргументы передаются в RDI, RSI, RDX, RCX, R8, R9, а затем в стек. ( Каковы соглашения о вызовах для системных вызовов UNIX и Linux на i386, а x86-64 охватывает вызовы функций, а также системные вызовы). Другое основное соглашение о вызовах x86-64 - это Windows x64, которая передает первые 2 аргумента в RCX и RDX (если они оба являются целочисленными типами).

Так что да, x = RDI и y = RSI. И да, результат = RAX. (запись в EAX с нулевым расширением в RAX).

Из структуры кода (без сохранения / перезагрузки каждой переменной C в память между операторами) он компилируется с включенным уровнем оптимизации, поэтому цикл for() превратился в нормальный asm-цикл с условной ветвью в дно. Почему циклы всегда компилируются в стиле "do ... while" (прыжок в хвост)? (ответ @ BrianWalker показывает, что цикл asm транслитерируется обратно в C, без попытки его преобразования в идиоматическая for петля.)

Из cmp / jcc перед циклом мы можем сказать, что компилятор не может доказать, что цикл выполняет ненулевое число итераций. Так что, каково бы ни было условие цикла for(), в первый раз оно может быть ложным (Это неудивительно, учитывая целые числа со знаком).

Поскольку мы не видим, чтобы отдельный регистр использовался для i, мы можем заключить, что оптимизация повторно использовала регистр другого var для i. Как, вероятно, for(i=x;, а затем с исходным значением x, не использованным для остальной функции, он «мертв», и компилятор может просто использовать RDI как i, уничтожая исходное значение x.

Я угадал i=x вместо y, потому что RDI - это регистр arg, который изменяется внутри цикла. Мы ожидаем, что источник C изменяет i и result внутри цикла и, по-видимому, не изменяет свои входные переменные x и y. Нет смысла делать i=y, а затем делать что-то вроде x--, хотя это был бы еще один правильный способ декомпиляции.

cmp %rdi, %rsi / jl .L3 означает, что условие цикла (повторного) входа в цикл составляет rsi-rdi < 0 (со знаком) или i<y.

cmp / jcc перед цикл проверяет противоположное состояние; обратите внимание, что операнды меняются местами, и он проверяет jle, т.е. jng. Так что это имеет смысл, это действительно то же самое условие цикла, которое выводится из цикла и реализуется по-другому. Таким образом, он совместим с источником C, представляющим собой простой цикл for() с одним условием.

sub $1, %rdi, очевидно, i-- или --i. Мы можем сделать это внутри for() или в нижней части тела цикла. Самое простое и идиоматичное место для его размещения - 3-й раздел оператора for(;;).

addq %rdi, %rax явно добавляет i к result. Мы уже знаем, что такое RDI и RAX в этой функции.

Соединяя кусочки, мы приходим к: 

long foo(long x, long y)
{
    long i, result = 0;
    for (i= x    ;    i>y    ;    i-- ){
        result += i;
    }

    return result;
}

Какой компилятор создал этот код?

Из имен меток .L3: это похоже на вывод из gcc.(Что-то испортилось, удалив : из .L2 и, что более важно, удалив % из %rsi в одном cmp. Убедитесь, что вы копируете / вставляете код в SO вопросы, чтобы избежать этого.)

Так что, возможно, с правильной версией / опциями gcc вытащить именно этот asm для некоторого C-ввода.Вероятно, это gcc -O1, потому что movl $0, %eax исключает -O2 и выше (где GCC будет искать оптимизацию глазка xor %eax,%eax для эффективного обнуления регистра).Но это не -O0, потому что это будет хранить / перезагружать счетчик цикла в память.И -Og (немного оптимизировать для отладки) предпочитает использовать jmp для условия цикла вместо отдельного cmp/jcc для пропуска цикла.Этот уровень детализации в основном не имеет значения для простой декомпиляции в C, который делает то же самое.

rep ret - это еще один признак gcc;gcc7 и более ранние версии использовали это в своем выводе tune=generic по умолчанию для ret, который достигнут как цель ветвления или откат от jcc, благодаря предсказанию ветвления AMD K8 / K10. Что означает `rep ret`?

gcc8 и более поздние версии все равно будут использовать его с -mtune=k8 или -mtune=barcelona.Но мы можем исключить это, потому что этот параметр настройки будет использовать dec %rdi вместо subq $1, %rdi.(Только у некоторых современных процессоров есть проблемы с inc/dec, оставляя CF неизмененным для операндов регистра. Инструкция INC против ADD 1: это имеет значение? )

gcc4.8 и более поздних версийrep ret на той же строке.gcc4.7 и более ранние версии распечатайте его, как вы показали, с префиксом rep в строке перед.

gcc4.7 и более поздними, например, ставьте начальную ветвь перед в mov $0, %eax, что выглядит как пропущенная оптимизация.Это означает, что им нужен отдельный return 0 путь из функции, который содержит еще один mov $0, %eax.

gcc4.6.4 -O1 воспроизводит ваш вывод точно , дляисточник, показанный выше, в проводнике компилятора Godbolt 

# compiled with gcc4.6.4 -O1 -fverbose-asm
foo:
        movl    $0, %eax        #, result
        cmpq    %rsi, %rdi      # y, x
        jle     .L2       #,
.L3:
        addq    %rdi, %rax      # i, result
        subq    $1, %rdi        #, i
        cmpq    %rdi, %rsi      # i, y
        jl      .L3 #,
.L2:
        rep
        ret

Так же, как и эта другая версия, которая использует i=y.Конечно, мы могли бы добавить много вещей, которые могли бы оптимизировать, например, i=y+1 и затем иметь условие цикла вроде x>--i.(Переполнение со знаком является неопределенным поведением в C, поэтому компилятор может предположить, что этого не происходит.) 

// also the same asm output, using i=y but modifying x in the loop.
long foo2(long x, long y) {
  long i, result = 0;
  for (i= y    ;    x>i    ;    x-- ){
      result += x;
   }
   return result;
}

На практике способ, которым я фактически изменил это:

  • Я скопировал / вставил шаблон C в Godbolt (https://godbolt.org/). Я сразу увидел (из mov $0 вместо xor-zero и из имен меток), что он выглядел как gcc -O1 output, поэтомуЯ вставил в эту опцию командной строки и выбрал версию gcc старой версии, например, gcc6. (Оказывается, эта версия asm была от гораздо более старой версии gcc).

  • Я попытался сделать первоначальное предположение, например x<y основанный на cmp / jcc и i++ (до того, как я действительно прочитал остальную часть асма вообще ), потому что для циклов часто используют i++. Тривиально выглядящий бесконечный-вывод asm цикла показал мне, что это было явно неправильно: P

  • Я догадался, что i = x, но после неправильного поворота с версией, которая сделала result += x но i--, японял, что i отвлекает и поначалу упростил, не используя i.просто использовал x-- при первом обращении к нему, потому что, очевидно, RDI = x.(Я знаю соглашение о вызовах x86-64 System V достаточно хорошо, чтобы сразу увидеть это.)

  • После рассмотрения тела цикла, result += x и x-- были полностью очевидны изинструкции add и sub.

  • cmp/jl, очевидно, были условиями цикла something < something, включающими 2 входных переменных.

  • Я не был уверен, был ли это x<y или y<x, и более новые версии gcc использовали jne в качестве условия цикла. Я думаю, что в тот момент я обманул и посмотрел на ответ Брайана, чтобы проверить, действительно ли он был x > y, вместо того, чтобы потратить минуту, чтобы разобраться с реальной логикой. Но как только я понял, что это было x--, только x>y имело смысл. Другое было бы верно до циклического перехода, если оно вообще вошло в цикл, но переполнение со знаком - неопределенное поведение в C.

  • Затем я посмотрел на некоторые более старые версии gcc, чтобы увидеть, сделал ли какой-нибудь asm больше как в вопросе.

  • Затем я вернулся и заменил x на i внутри цикла.

Если это кажется случайным и слабым, это потому, что этот цикл настолько мал, что я не ожидал, что у него возникнут какие-либо проблемы с его выяснением, и меня больше интересует поиск версии source + gcc, которая точно воспроизводит его, скорее чем первоначальная проблема просто полностью изменить его.

(я не говорю, что новичкам должно быть легко), я просто документирую мой мыслительный процесс на случай, если кому-то будет любопытно. *

...