В процессе генерации кода создаются блоки инструкций разных длин.
Эти блоки разделяются командами переходов разных длин.
Если обозначить длину n-ой команды команды перехода буквой xn,
тогда можно составить систему линейных уравений, где длина одних команд может зависить от сумм длин блоков и других команд.
Можно поставить цель оптимизации (минимизации) суммарной длины (т.е. min Σ xn).
Наверное обычно такую задачу не решают, а тупо дополняют команды до стандартных длин командой nop или каким-нибудь префиксом (чтобы не терять такты на команду).
Известны ли вам ассемблеры, которые такую задачу? Где-нибудь есть описание решение (чтобы там описывалась не стандартная обобщённая задача дискретной оптимизации, а конкретно эта?)?
Ассемблер не решает задачи оптимизации.
Ассемблер решает задачу точного и однозначного перевода того, что написано буквами, в соответствующие байты.
Если ассемблер переводит не точно, однозначно, и именно то, что написано в исходнике, то это плохой, негодный ассемблер.
ЭФ>Известны ли вам ассемблеры, которые такую задачу?
У меня препод в институте был такой же догматичный дурак. Мол "знание принципов освобождает от знания частных деталей". Но иногда надо на вещи смотреть реально, а не через призму догм.
Неверно, что одна мнемоника всегда генерирует один и тот же код. Например MOV может генерировать разные коды в зависимости от операндов и режимов адресации. (Он настаивал на том, что каждая мнемоника однозначно определяет сгенерированный код)
Так и JMP может быть длинный, а может быть короткий. И надо автоматизированно выбрать какой будет.
Да, можно хинты указать — FAR, NEAR, но что если они не указаны?
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>В процессе генерации кода создаются блоки инструкций разных длин. ЭФ>Эти блоки разделяются командами переходов разных длин. ЭФ>тогда можно составить систему линейных уравений, где длина одних команд может зависить от сумм длин блоков и других команд. ЭФ>Можно поставить цель оптимизации (минимизации) суммарной длины (т.е. min Σ xn). ЭФ>Наверное обычно такую задачу не решают, а тупо дополняют команды до стандартных длин командой nop или каким-нибудь префиксом (чтобы не терять такты на команду). ЭФ>Известны ли вам ассемблеры, которые такую задачу? Где-нибудь есть описание решение (чтобы там описывалась не стандартная обобщённая задача дискретной оптимизации, а конкретно эта?)?
Ассемблер может решить эту задачу элементарно — несколькими проходами.
Например старый RASM имел 3 прохода. Первый — исключительно для того, чтобы определить в каком сегменте находятся данные (CSEG, DSEG/ESEG, SSEG) и правильно учесть длину префиксов. Лишних длинных переходов не получалось.
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Раз на раз не приходится. Могут быть такие граничные (специально сконструированные) случаи, что три прохода не помогут.
Ну, проходов может быть много
В ассемблере, которым я пользуюсь все просто — на команду перехода может быть выдано предупреждение (скорее, замечание) с текстом "можно короче". Тогда, если хочется идеального кода, берешь и JMP руками исправляешь на JMPS
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Так и JMP может быть длинный, а может быть короткий. И надо автоматизированно выбрать какой будет. ЭФ>Да, можно хинты указать — FAR, NEAR, но что если они не указаны?
Это должно быть написано в документации. Обычная практика (по крайней мере была 10 лет назад) такая, что если влезает в short, то будет jmp short, а если нет, то будет jmp near, если явно не указан тип. И эта способность выбирать — скорее недостаток ассемблера, чем преимущество.
Всё равно не поможет (понятно, что редко). Потому что в задаче оптимизации могут быть локальные экстремумы.
Вообще говоря, я в шоке от того, что нужно сильно потрудиться, чтобы объяснить в чём проблема, думал что здесь меня лучше поймут. А вижу только "а-ха-ха, да это ерунда, я что-то слышал такое".
S> Обычная практика ... что если влезает в short, то будет jmp short, а если нет, то будет jmp near ... эта способность выбирать
Т.е. ты повторил/подтвердил всё то, что было написано в стартовом посте. Не предложил решения. И высказал личное мнение, что мол "вопрос не стоит твоего внимания".
Ну, спасибо за мнение.
Здравствуйте, Эйнсток Файр.
ЭФ>В процессе генерации кода создаются блоки инструкций разных длин. ЭФ>Эти блоки разделяются командами переходов разных длин.
<...> ЭФ>Можно поставить цель оптимизации (минимизации) суммарной длины...
ЭФ><...> Где-нибудь есть описание решения <...>?
A Simple, Linear-Time Algorithm for x86 Jump Encoding
Neil G. Dickson
The problem of space-optimal jump encoding in the x86 instruction set, also known as branch displacement optimization, is described, and a linear-time algorithm is given that uses no complicated data structures, no recursion, and no randomization. The only assumption is that there are no array declarations whose size depends on the negative of the size of a section of code (Hyde 2006), which is reasonable for real code.
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Наверное обычно такую задачу не решают, а тупо дополняют команды до стандартных длин командой nop или каким-нибудь префиксом (чтобы не терять такты на команду).
А можно просто воткнуть самые короткие подходящие команды перехода, а потом сделать еще один проход по уже сгенерированному коду, и повторять этот дополнительный проход до тех пор, пока предыдущему удалось чего-то наоптимизировать. Поскольку реально ситуация, когда переход удалось укоротить, довольно редкая, то дополнительных проходов будет немного.
ЭФ>Известны ли вам ассемблеры, которые такую задачу? Где-нибудь есть описание решение (чтобы там описывалась не стандартная обобщённая задача дискретной оптимизации, а конкретно эта?)?
Турбо-ассемблер еще в 90-е умел это делать. Хуже того, его еще было трудно уговорить этого не делать. Подозреваю, что все более-менее "взрослые" ассемблеры это умеют.
In fact, there have been some mathematical proofs that show that this problem is "NP-Complete", which means that the only way to guarantee you've got an optimal solution is to try all possible combinations of short and long displacements in the object file and select the (or one of the) combination(s) that is the shortest.
А в работе по ссылке вводится допущение.
Собственно, во второй работе тоже ссылаются на существование доказательства.
Которое приводится где-то тут: https://dl.acm.org/doi/10.1145/359460.359474
Но у них там особый случай использования памяти (сегментами), и поэтому:
The resulting algorithm, therefore, will not return the least fixed point, as it
might have too many long jumps.
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Наверное обычно такую задачу не решают, а тупо дополняют команды до стандартных длин командой nop или каким-нибудь префиксом (чтобы не терять такты на команду).
Насчёт "не терять такты" — нифига не понял
ЭФ>Известны ли вам ассемблеры, которые такую задачу?
Такую задачу что?
ЭФ>Где-нибудь есть описание решение (чтобы там описывалась не стандартная обобщённая задача дискретной оптимизации, а конкретно эта?)?
Никто особо не парится. Если переход назад — то всё вообще просто, если вперёд — вставляем длинную инструкцию, ассемблим дальше, дошли до метки перехода — проверили, нельзя ли использовать версию покороче. Если можно — используем, корректируя по необходимости остальные ветки/метки
Не вижу где. У меня всё сходится.
1) Я хочу иметь код, который решает задачу точно, поэтому мне не подходят алгоритмы из gcc и этой pdf-ки с линейной сложностью
2) мне наплевать, что у NP-полного высокая сложность (потому что можно не всегда его запускать через параметр командной строки)
3) Я не хочу тратить годы, разрабатывая что-то особохитровыдуманное, как в статье с Хабра
Хочу просто в лоб решение перебором, но не могу его формализовать и запрограммировать,
потому что не знаю с чего начать.
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Хочу просто в лоб решение перебором, но не могу его формализовать и запрограммировать, ЭФ>потому что не знаю с чего начать.
А в чём у тебя проблема?
Сначала определяешь все переходы, которые заведомо будут короткими или заведомо будут длинными. Остаётся некоторое число переходов, которые могут быть как короткими, так и длинными, в зависимости друг от друга.
После этого просто перебираешь все варианты. Из них отбираешь тот, который приводит к самому короткому конечному коду.
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Наверное обычно такую задачу не решают, а тупо дополняют команды до стандартных длин командой nop или каким-нибудь префиксом (чтобы не терять такты на команду).
Наверное, даже дополнять не нужно, не проблема короткий переход закодировать длинным способом.
Я думаю, поиски реализации будут неудачны.
Ассемблеры не оптимизируют, а транслируют, без особых претензий на оптимизацию.
Компиляторы оптимизируют, но им есть куда стремиться в плане более простых и более действенных оптимизаций, чем эта.
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>В процессе генерации кода создаются блоки инструкций разных длин. ЭФ>Эти блоки разделяются командами переходов разных длин.
В некоторых ассемблерах длинным бывает только безусловный переход.
А условный переход всегда короткий.
Поэтому, когда нужно прыгнуть далеко, прыгают близко на "трамплин",
а уж с трамплина туда, куда надо.
