Не знаю как такие вещи делает сферический х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 или каким-нибудь префиксом (чтобы не терять такты на команду). ЭФ>Известны ли вам ассемблеры, которые такую задачу?
Это троль, не кормите его.
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, ты не ухудшаешь ситуации для других переходов, а для некоторых можешь улучшить...
