Вопрос по optimization, encoding, assembly, algorithm – Почему алгоритм «начать с малого» для смещения ветвей не оптимален?

3

[вопрос выделен жирным шрифтом внизу]

Когда ассемблер генерирует двоичную кодировку, он должен решить, сделать ли каждую ветку длинной или короткой, если короткая лучше, если это возможно. Эта часть ассемблера называетсяалгоритм оптимизации смещения ветвей (BDO), Типичный подход заключается в том, что ассемблер делаетвсе кодировка ветвей короткая (если они меньше некоторого порога), затем итеративно увеличивает любой переход, переходящий к длинным, которые не достигают. Это, конечно, может привести к тому, что другие ветви будут преобразованы в прыжки в длину. Таким образом, ассемблер должен продолжать проходить через список переходов до тех пор, пока не потребуется больше увеличения. Мне кажется, что этот подход с квадратичным временем является оптимальным алгоритмом, но предположительно BDO является NP-полным, и этот подход на самом деле не является оптимальным.

Рэндалл Хайд представил контрпример:

                  .386 
                  .model  flat, syscall
00000000          .code
00000000          _HLAMain        proc


00000000  E9 00000016          jmpLbl:         jmp     [near ptr] target
00000005 = 00000005            jmpSize         =       $-jmpLbl
00000005  00000016 [                           byte    32 - jmpSize*2
dup
(0)
            00
           ]
0000001B                       target:
0000001B                       _HLAMain        endp
                                                end

При добавлении части в скобках «[near ptr]» и форсировании 5-байтового кодирования двоичный код фактически становится короче, потому что выделенный массив уменьшается вдвое по сравнению с величиной прыжка. Таким образом, делая кодировку перехода короче, конечный код на самом деле длиннее.

Мне кажется, что это крайне патологический случай, и он не очень актуален, потому что кодировки ветвлений все еще меньше, именно этот странный побочный эффект для не связанной с ветвями части программы приводит к увеличению размера двоичного файла. Поскольку сами кодировки ветвей все еще меньше, я не считаю это правильным контрпримером к алгоритму «начать с малого».

Могу ли я считать начальный-маленький алгоритм оптимальным алгоритмом BDO или существуетреалистический случай, когда он не обеспечивает минимальный размер кодирования для всех ветвей?

@harold Нет. Для целей вопроса мне интересно, буду ли я производить минимальные кодировки команд с помощью start-small. Я считаю вопросы выравнивания и тому подобное неактуальными. Я имею в виду, что если я получу дополнительные 0 байтов в качестве заполнения, я не считаю это нарушением оптимальности. Я бы предпочел более короткие инструкции по прыжкам и много отступов, чем наоборот. Tyler Durden
@rici: Спасибо, я вижу, как эти два списка можно построить за O (1) раз за прыжок, если двинуться вперед на два указателя. Ваше упоминание о «проблеме наименьшей фиксированной точки» предполагает, что это пример общего класса проблем, которые могут быть решены таким же образом, но страница Википедии была не слишком полезна ... Знаете какие-нибудь полезные ссылки в этом направлении? j_random_hacker
@rici: Интересно, спасибо! j_random_hacker
Не по теме, но, возможно, интересно: наивный алгоритм не должен быть квадратичным. На самом деле это задача с наименьшей фиксированной точкой, и она может быть решена за линейное время при условии, что число добавлений экземпляра в набор кандидатов равно O (1). В этом случае экземпляр представляет собой короткую ветвь, а набор кандидатов - это набор коротких ветвей, которые могли бы стать длинными в результате изменения другой ветви. Ограничение O (1) выполнено, потому что диапазон действия изменения оператора ветвления ограничен диапазоном короткой ветви, и в этом диапазоне находится только конечное число ветвей. rici

Ваш Ответ

2   ответа
4

что Start Small является оптимальным для упрощенного случая, когда нет отступов, звучит разумно. Тем не менее, это не очень полезно вне оптимизированных для размера функций.Настоящий асмделает иметьALIGN директивы, и этоделает Сделать разницу.

Вот самый простой пример, который я мог бы построить для случая, когда Start Small не дает оптимального результата (протестировано с NASM и YASM).использованиеjz near .target0 заставить долго кодировать, двигаяanother_function: На 32 байта раньше и уменьшает заполнение внутриfunc.

func:
.target0:               ; anywhere nearby
    jz  .target0        ; (B0)  short encoding is easily possible
.target1:
   times 10 vpermilps xmm14, xmm15, [rdi+12345]
        ; A long B0 doesn't push this past a 32B boundary, so short or long B0 doesn't matter
ALIGN 32
.loop:
   times 12 xor r15d,r15d
    jz  .target1         ; (B1)  short encoding only possible if B0 is long
   times 18 xor r15d,r15d
    ret   ; A long B1 does push this just past a 32B boundary.

ALIGN 32
another_function:
    xor  eax,eax
    ret

Если B0 короткая, то B1 должна быть длинной, чтобы достичь target1.

Если B0 длинный, он перемещает target1 ближе к B1, позволяя достичь короткого кодирования.

Таким образом, самое большее из B0 и B1 может иметь короткое кодирование, новажно, какой из них короткий, Короткий B0 означает еще 3 байта отступа выравнивания без сохранения размера кода. Длинный B0, позволяющий короткий B1делает сохранить общий размер кода. В моем примере я проиллюстрировал самый простой способ, который может произойти: путем нажатия на конец кода после B1 за границей следующего выравнивания. Это также может повлиять на другие отрасли, например, требуется длинное кодирование для ветви.loop.

Желаемый: B0 длинный, B1 короткий.

Старт-малый результат: B0 короткий, B1 длинный. (Их начальные состояния первого прохода.) Start-Small не пытается удлинить B0 и укорачивать B1, чтобы посмотреть, уменьшает ли он общее заполнение или просто выполняет заполнение (в идеале взвешенное по счетчику поездок).

4-байтовый NOP перед.loopи 31 байт перед NOPanother_funcтак что начинается в0x400160 вместо0x400140 что мы получаем от использованияjz near .target0 что приводит к короткому кодированию для B1.

Обратите внимание, что длинная кодировка для самого B0не единственный способ добиться короткого кодирования для B1, Кодирование дольше необходимого для любой из инструкций перед.target1 также мог бы добиться цели. (например, смещение 4B или немедленное, вместо 1B. Или ненужный или повторный префикс.)

К сожалению, ни один из известных мне ассемблеров не поддерживает такие отступы; только сnop. Какие методы могут быть использованы для эффективного увеличения длины инструкции на современном x86?

Часто даже не прыгает черезNOP в начале цикла, так что дополнительное заполнение потенциально ухудшает производительность (если требуется несколько NOP, или код работает на процессоре, таком как Atom или Silvermont, который действительно медленный с большим количеством префиксов, которые использовались, потому что ассемблер не был ' т тюнинг для Silvermont).

Обратите внимание, что выходные данные компилятора редко имеют переходы между функциями (обычно только для оптимизации хвостового вызова). x86 не имеет короткой кодировки дляcall, Рукописный ассм может делать все, что захочет, но код спагетти (надеюсь?) Все еще редко встречается в больших масштабах.

Я думаю, что проблема BDO может быть разбита на несколько независимых подзадач для большинства исходных файлов asm, обычно каждая функция представляет собой отдельную проблему, Это означает, что даже алгоритмы неполиномиальной сложности могут быть жизнеспособными.

Некоторые ярлыки, помогающие решить проблему, помогут: например, определить, когда определенно необходимо длинное кодирование, даже если все промежуточные ветви используют короткое кодирование. Это позволит нарушать зависимости между подзадачами, когда единственное, что их связывало, - это хвостовой вызов между двумя удаленными функциями.

Я не уверен, где на самом деле начать создавать алгоритм, чтобы найти глобально оптимальное решение. Если мы хотим рассмотреть возможность расширения других инструкций для перемещения целей ветвления, пространство поиска довольно велико. Тем не менее, я думаю, что мы должны рассматривать только ветви, которые пересекают выравнивание.

Возможные случаи:

заполнение перед целевой ветвью для обратных ветвейзаполнение перед инструкцией ветвления для прямых веток

Хорошая работа с этим может быть проще, если мы внедрим некоторые знания по оптимизации микроархитектуры в ассемблер: например, всегда старайтесь, чтобы цели ветвления начинались в начале 16B блоков insn fetch, и определенно не в самом конце. Линия кэш-памяти Intel UOP может кэшировать только UOP из одного блока 32B, поэтому границы 32B важны для кэша UOP. Размер строки L1 I $ равен 64B, а размер страницы - 4kiB. (Однако ассемблер не будет знать, какой код горячий, а какой - холодный. Наличие горячего кода, занимающего две страницы, может быть хуже, чем немного больший размер кода.)

Наличие многопользовательской инструкции в начале группы декодирования инструкций также намного лучше, чем когда-либо еще, для Intel и AMD. (Менее так для процессоров Intel с кешем UOP). Выяснение того, какой путь ЦП будет проходить в коде большую часть времени и где будут границы декодирования команд, вероятно, намного превосходит возможности ассемблера.

Другой случай, когда вы можете быстро решить, следует ли расширять кодировку перехода, - это когда, даже если все другие переходы между ним и его целевым адресом были расширены, его смещение все еще будет достаточно маленьким, чтобы позволить небольшое кодирование. j_random_hacker
5

что при отсутствии аномальных скачков, упомянутых Гарольдом в комментариях, алгоритм «начать с малого»является оптимален:

Во-первых, давайте установим, что «начать с малого» всегда производитвыполнимый решение - то есть то, которое не содержит коротких кодов слишком длинного прыжка. Алгоритм, по сути, сводится к многократному заданию вопроса: «Возможно ли это еще? и удлинение некоторого кодирования перехода, если нет, так четкоесли это заканчивается, тогда решение, которое это производит, должно быть выполнимым. Поскольку каждая итерация удлиняет некоторый скачок, и ни один скачок не удлиняется более одного раза, этот алгоритм должен в конечном итоге завершаться после не более чем итераций nJumps, поэтому решение должно быть выполнимым.

Теперь предположим противное, что алгоритм может дать субоптимальное решение X. Пусть Y - некоторое оптимальное решение. Мы можем представить решение как подмножество инструкций перехода, которые удлиняются. Мы знаем, что | X \ Y | > = 1 - то есть, что есть хотя бы 1 удлинение инструкции в X, которого нет также в Y - потому что в противном случае X было бы подмножеством Y, а так как Y является оптимальным по предположению, а X, как известно, выполнимо из этого следует, что X = Y, что означает, что сам X будет оптимальным решением, что противоречило бы нашему первоначальному предположению о X.

Из инструкций в X \ Y выберите i, который будет сначала удлинен алгоритмом «start small», и пусть Z будет подмножеством Y (и X), состоящим из всех инструкций, уже удлиненных ранее алгоритмом. к этому времени. Поскольку алгоритм «начинай с малого» решил удлинить кодировку i, должно быть, к тому моменту (т.е. после удлинения всех инструкций в Z) смещение перехода i было слишком большим для короткого кодирования. (Обратите внимание, что, хотя некоторые удлинения в Z могли вытолкнуть смещение i прыжка за пределы критической точки, это ни в коем случае не является необходимым - возможно, смещение i было выше порога с самого начала. Все, что мы можем знать, и все, что нам нужно, знаю, что смещение прыжка i превысило пороговое значение к моменту окончания обработки Z.) Но теперь оглянемся на оптимальное решение Y и отметим, чтони одно из других удлинений в Y, то есть в Y \ Z, не способно уменьшить смещение прыжка вниз, так как смещение I выше порога, но его кодированиене удлиненный на Y, Y даже неосуществим! Невозможное решение не может быть оптимальным, поэтому существование такой удлиненной инструкции i в Y противоречило бы предположению, что Y является оптимальным, что означает, что такого я не может существовать.

Похожие вопросы