В процессе генерации кода создаются блоки инструкций разных длин.
Эти блоки разделяются командами переходов разных длин.
Если обозначить длину 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 или каким-нибудь префиксом (чтобы не терять такты на команду).
Наверное, даже дополнять не нужно, не проблема короткий переход закодировать длинным способом.
Я думаю, поиски реализации будут неудачны.
Ассемблеры не оптимизируют, а транслируют, без особых претензий на оптимизацию.
Компиляторы оптимизируют, но им есть куда стремиться в плане более простых и более действенных оптимизаций, чем эта.
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>В процессе генерации кода создаются блоки инструкций разных длин. ЭФ>Эти блоки разделяются командами переходов разных длин.
В некоторых ассемблерах длинным бывает только безусловный переход.
А условный переход всегда короткий.
Поэтому, когда нужно прыгнуть далеко, прыгают близко на "трамплин",
а уж с трамплина туда, куда надо.
Не знаю как такие вещи делает сферический х86 ассемблер в вакууме, но например арм ассембер в подобных задачах не заморачивается особенной оптимизацией. Уточню — в арм ассемблере есть такая директива .ltorg которая говорит 'вот сюда можно класть константы' и есть некоторые инструкции, которые туда откладывают свои константы. Так вот если пихать эти директивы везде — компилятор просто будет пихать константу в ближайший .ltorg не глядя на то, что такая же константа уже присутствует в каком то другом .ltorg который находится в достижимой области.
Поланаю х86 ассемблер тоже не особо заморачивается поиском комбинации, дающей минимальное количество длинных джампов. Кстати такая комбинация не факт что будет оптимальна с точки зрения перфоманса, если уж так крепко заморачиваться.
Как много веселых ребят, и все делают велосипед...
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Хочу просто в лоб решение перебором, но не могу его формализовать и запрограммировать, ЭФ>потому что не знаю с чего начать.
1) У тебя есть массив комманд.
2) Часть из них — команды перехода, которые могут быть длинными или короткими.
И их не очень много — около десятка (переходы же внутри функции, а функции нынче короткие).
Длинна остальных команд не меняется.
3) Перебор — это перебор вариантов длинный/короткий переход.
Первый вариант — все команды переходов короткие (если всё работает, выход из цикла, решение найдено)
Второй вариант — первая команда длинная, остальные короткие (если работает, пишем решение, цикл продолжаем)
И так далее.
4) если удаётся найти более короткое решение, заменяем предудущее решение на лучшее.
Можно пооптимизировать порядок перебора, если очень хочется.
Например, не трогать переходы, которые точно длинные или точно короткие.
Минимальный размер кода в лоб не даст лучшую программу.
Потому что:
* Надо определиться с выравниванием циклов, скорее всего, их выгодно выровнять на границу 16, но это не точно
* Надо сделать условные переходы дружелюбными к предсказателю переходов в процессоре. По умолчанию переходы вперёд предсказываются как невыполненные, переходы назад как выполненные, при этом частота эффективных выполненных переходов ограничена
* Есть баг во многих процессорах Intel, когда инструкция перехода находится на неудачном выравнивании, её производителность резко падает https://www.intel.com/content/dam/support/us/en/documents/processors/mitigations-jump-conditional-code-erratum.pdf
Это всё мелочи (ну кроме последнего, где на некоторых конкретных бенчмарках наблюдал десятки процентов разницы), но они всё же важнее, чем минимизация размера кода/инструкций перехода.
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Известны ли вам ассемблеры, которые такую задачу? Где-нибудь есть описание решение (чтобы там описывалась не стандартная обобщённая задача дискретной оптимизации, а конкретно эта?)?
Да, ассемблеры x86, с его миллионом вариантов команд перехода, одинаковыми по смыслу но разнымы по длине, так делают.
Это делается во много проходов. Ну, например, сначала предполагаем, что все команды перехода — длинные, расставляем адреса. Потом смотрим, какие переходы можно заменить на короткие, корректируем адреса. Еще раз смотрим, возможно, программа "уплотнилась", и некоторые другие переходы тоже стало возможно "укоротить", укорачиваем, корректируем адреса. И так до тех пор, пока на очередном шаге ничего не изменилось.
Во времена MS-DOS этим больше заморачивались; каждый байт был на счету. Сейчас могут для ускорения обойтись одним проходом, второй все равно редко приносит урожай.
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Так и JMP может быть длинный, а может быть короткий. И надо автоматизированно выбрать какой будет. ЭФ>Да, можно хинты указать — FAR, NEAR, но что если они не указаны?
Содержательно, NEAR JMP может быть с однобайтовым и 4-байтовым смещением, и они могут переходить друг в друга.
FAR в NEAR и наоборот никогда автоматически не переходят, это команды с разной совершенно семантикой. Ассемблер не может знать, как ты используешь сегменты.
Здравствуйте, Sharowarsheg, Вы писали:
S>Это должно быть написано в документации. Обычная практика (по крайней мере была 10 лет назад) такая, что если влезает в short, то будет jmp short, а если нет, то будет jmp near, если явно не указан тип. И эта способность выбирать — скорее недостаток ассемблера, чем преимущество.
После того, как ты один переход затолкал в short, программа "уплотнилась", и какой-нибудь другой тоже может затолкаться в short. Поэтому в один проход это не делается.
Недостаток это скорее процессора, чем ассемблера. Там и совершенно мирные команды, такие, как ADD, MOV, ..., имеют варианты кодирования разной длины, с совершенно одинаковой семантикой. И ты не можешь руками между ними выбирать.
Эйнсток Файр:
ЭФ>Наверное обычно такую задачу не решают, а тупо дополняют команды до стандартных длин командой nop или каким-нибудь префиксом (чтобы не терять такты на команду). ЭФ>Известны ли вам ассемблеры, которые такую задачу?
Это троль, не кормите его.
Модератор-националист Kerk преследует оппонентов по политическим мотивам.
Re[2]: A Simple, Linear-Time Algorithm for x86 Jump Encoding
Здравствуйте, SergeCpp, Вы писали:
SC>A Simple, Linear-Time Algorithm for x86 Jump Encoding SC>Neil G. Dickson SC>
SC>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.
Ну в принципе, в реальной жизни очень редко бывает так, что требуется больше двух проходов. Причем второй проход уже не приносит большого урожая.
Поэтому можно или крутиться в цикле до победы, или постулировать, что мы делаем пару проходов, и на редкие неуловленные двумя проходами случаи нам наплевать. В конце концов, от ассемблера мы ждем скорости и надежности, а не крутой оптимизации.
Поэтому эта работа имеет чисто теоретический интерес. Готов поспорить, не ходя по ссылке, что это — чья-то диссертация
Здравствуйте, Эйнсток Файр, Вы писали:
Pzz>> повторять этот дополнительный проход до тех пор, пока предыдущему удалось чего-то наоптимизировать.
ЭФ>я уже объяснял, что локальный минимум в задаче оптимизации не всегда совпадает с глобальным.
В данном случае — всегда. Если изначально все переходы NEAR, то замена их на SHORT всегда улучшает и никогда не ухудшает ситуацию.
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Хочу просто в лоб решение перебором, но не могу его формализовать и запрограммировать, ЭФ>потому что не знаю с чего начать.
Начни с того, чтобы разобраться в кодировании команд x86. Скорее всего, ты этим и кончишь, и дальше не продвинешься.
Здравствуйте, alpha21264, Вы писали:
A>Можно пооптимизировать порядок перебора, если очень хочется. A>Например, не трогать переходы, которые точно длинные или точно короткие.
Обрати внимание, что каждый раз, заменяя NEAR JMP на SHORT JMP, ты не ухудшаешь ситуации для других переходов, а для некоторых можешь улучшить. Поэтому там не получается какого-то разветвленного перебора с возвратами и откатами. Просто заменяем все возможные переходы на более короткие, потом делаем еще проход до тех пор, пока очередной проход не принес результатов.
Количество проходов всегда конечное и редко большое.
Здравствуйте, Pzz, Вы писали:
Pzz>Обрати внимание, что каждый раз, заменяя NEAR JMP на SHORT JMP, ты не ухудшаешь ситуации для других переходов, а для некоторых можешь улучшить. Поэтому там не получается какого-то разветвленного перебора с возвратами и откатами. Просто заменяем все возможные переходы на более короткие, потом делаем еще проход до тех пор, пока очередной проход не принес результатов.
главное не забыть про выравнивание точек назначения переходов на границу кэш-линий (путем вставки nop или использования более длинных версий опкода), иначе удивительным образом ваш "оптимизированный" код с циклами будет дико тормозить при выполнении.
Здравствуйте, mike_rs, Вы писали:
_>главное не забыть про выравнивание точек назначения переходов на границу кэш-линий (путем вставки nop или использования более длинных версий опкода), иначе удивительным образом ваш "оптимизированный" код с циклами будет дико тормозить при выполнении.
Это обычно делает компилятор. Для этого в ассемблере предусмотрены соответствующие директивы; компилятор их вставляет, а ассемблер учитывает.
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>В процессе генерации кода создаются блоки инструкций разных длин. ЭФ>Эти блоки разделяются командами переходов разных длин. ЭФ>Если обозначить длину n-ой команды команды перехода буквой xn, ЭФ>тогда можно составить систему линейных уравений, где длина одних команд может зависить от сумм длин блоков и других команд. ЭФ>Можно поставить цель оптимизации (минимизации) суммарной длины (т.е. min Σ xn).
ЭФ>Наверное обычно такую задачу не решают, а тупо дополняют команды до стандартных длин командой nop или каким-нибудь префиксом (чтобы не терять такты на команду).
Более того, решение такой задачи не имеет смысла, т.к. конец блока добивают нопами, чтоб
новый блок кода (куда будет переход) начать с выравненного адреса.
ЭФ>Известны ли вам ассемблеры, которые такую задачу? Где-нибудь есть описание решение (чтобы там описывалась не стандартная обобщённая задача дискретной оптимизации, а конкретно эта?)?
Задача оптимальной укладки рюкзака.
Re[2]: A Simple, Linear-Time Algorithm for x86 Jump Encoding
Здравствуйте, SergeCpp, Вы писали:
SC>Здравствуйте, Эйнсток Файр.
ЭФ>>В процессе генерации кода создаются блоки инструкций разных длин. ЭФ>>Эти блоки разделяются командами переходов разных длин. SC><...> ЭФ>>Можно поставить цель оптимизации (минимизации) суммарной длины...
ЭФ>><...> Где-нибудь есть описание решения <...>?
SC>A Simple, Linear-Time Algorithm for x86 Jump Encoding SC>Neil G. Dickson SC>[q] SC>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.
Я что-то не понял, но ведь блоки кода можно _перемешать_ между собой, а не располагать строго линейно,
в том порядке как заданы. И никакой линейный алгоритм здесь невозможен. Такие задачи решаются только за полиномиальное время.
Здравствуйте, Pzz, Вы писали:
Pzz>Здравствуйте, mike_rs, Вы писали:
_>>главное не забыть про выравнивание точек назначения переходов на границу кэш-линий (путем вставки nop или использования более длинных версий опкода), иначе удивительным образом ваш "оптимизированный" код с циклами будет дико тормозить при выполнении.
Pzz>Это обычно делает компилятор. Для этого в ассемблере предусмотрены соответствующие директивы; компилятор их вставляет, а ассемблер учитывает.
компилятор переводит высокоуровневый код в представление на промежуточном языке. Там нет ни кеша, ни длин инструкций, ничего. На этом этапе возможна т.н. whole program optimization, когда выкидываются одинаковые блоки, содержащиеся в разных библиотеках, выкидывается код, который никогда не вызывается и т.п. А дальше из этого промежуточного языка ассемблер генерирует машинный код под целевую платформу с учетом всех аппаратных особенностей этой платформы (вот тут уже кеш, длина инструкций и т.п. начинает играть роль).
Здравствуйте, fk0, Вы писали:
fk0> Более того, решение такой задачи не имеет смысла, т.к. конец блока добивают нопами, чтоб fk0>новый блок кода (куда будет переход) начать с выравненного адреса.
иногда оптимальнее взять более длинный опкод для кодирования команды, чтобы не плодить лишних шагов конвейера. Я об этом выше написал.
Здравствуйте, mike_rs, Вы писали:
Pzz>>Это обычно делает компилятор. Для этого в ассемблере предусмотрены соответствующие директивы; компилятор их вставляет, а ассемблер учитывает.
_>компилятор переводит высокоуровневый код в представление на промежуточном языке. Там нет ни кеша, ни длин инструкций, ничего. На этом этапе возможна т.н. whole program optimization, когда выкидываются одинаковые блоки, содержащиеся в разных библиотеках, выкидывается код, который никогда не вызывается и т.п. А дальше из этого промежуточного языка ассемблер генерирует машинный код под целевую платформу с учетом всех аппаратных особенностей этой платформы (вот тут уже кеш, длина инструкций и т.п. начинает играть роль).
Ошибаешься. Компилятор действительно переводит код в представление на промежуточном языке, делает на этом уровне всякие разные оптимизации, а потом переводит код в представление, очень близкое к целевому ассемблеру, и делает на этом уровне архитектурно-специфические оптимизации.
Причем это представление на промежуточном языке нужно в основном потому, что позволяет многие оптимизации сделать единообразно для всех поддерживаемых платформ, а retargetable компиляторы теперь в цене, потому, что мир больше не ограничен одной архитектурой по имени x86. Если писать компилятор под какую-то одну платформу и не иметь цели поддерживать перенос на другие платформы, то этот промежуточный язык нафиг не нужен и только замедляет процесс компиляции.
На выходе у компилятора, за редким исключением, текст на ассемблере, который отдельно прогоняется через ассемблер с целью получения объектного файла. Из этого подхода есть исключения (скажем, микрософтовский компилятор сразу рождает объектный файл), но в основном это работает именно так.
Что до whole program optimisation, ее невозможно делать до линковки. Как это сейчас устроено, я подробно не изучал, возможно, это делает линкер (что неудобно, потому что линкер из простой программы сразу становится очень сложным), возможно, линкер сочиняет подробный отчет о том, как программа, после первого прохода, выглядит целиком, потом ее составные части перекомпилируются, с учетом этого отчета, и уже перелинковываются начисто.
Здравствуйте, Pzz, Вы писали:
Pzz>Обрати внимание, что каждый раз, заменяя NEAR JMP на SHORT JMP, ты не ухудшаешь ситуации для других переходов, а для некоторых можешь улучшить...
Здравствуйте, Pzz, Вы писали: Pzz>Что до whole program optimisation, ее невозможно делать до линковки. Как это сейчас устроено, я подробно не изучал, возможно, это делает линкер (что неудобно, потому что линкер из простой программы сразу становится очень сложным),
Именно так и делается. Для LTCG компилятор вместо бинаря порождает OBJ файлы с IL-представлением. А линкер после сборки всей программы скармливает её в бэк-енд. Сам по себе он не особо то и усложняется, т.к. back-end — это динамически подгружаемая библиотека. Принципиальной разницы, вызывать ли её из "компилятора" или из "линкера", нету.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
