Наборы команд переменной длины часто предоставляют несколько инструкций перехода со смещениями разного размера для оптимизации размера кода.Например, PDP-11 имеет как
0004XX BR FOO # branch always, 8 bit displacement
, так и
000167 XXXXX JMP FOO # jump relative, 16 bit displacement
для относительных прыжков.Для более свежего примера, 8086 имеет в своем распоряжении
EB XX JMP FOO # jump short, 8 bit displacement
и
E8 XX XX JMP FOO # jmp near, 16 bit displacement
.
Ассемблер не должен обременять программиста угадыванием правильного видаперейти к использованию;он должен быть в состоянии вывести как можно более короткую кодировку, чтобы все прыжки достигали своих целей.Эта оптимизация еще более важна, когда вы рассматриваете случаи, когда необходимо эмулировать скачок с большим смещением.Например, у 8086 отсутствуют условные переходы с 16-битными смещениями.Для кода, подобного этому:
74 XX JE FOO # jump if equal, 8 bit displacement
ассемблер должен выдать код, подобный этому, если FOO слишком далеко:
75 03 JNE AROUND # jump if not equal
E8 XX XX JMP FOO # jump near, 16 bit displacement
AROUND: ...
Поскольку этот код занимает более двух разкак JE, он должен испускаться только в случае крайней необходимости.
Простой способ сделать это - сначала попытаться собрать все прыжки с наименьшим возможным смещением.Если какой-либо прыжок не подходит, ассемблер выполняет еще один проход, где все прыжки, которые не соответствовали ранее, заменяются более длинными прыжками.Это повторяется, пока все прыжки не подходят.Несмотря на простоту реализации, этот алгоритм работает за время O (n²) и немного хакерский.
Существует ли лучший, предпочтительно линейный алгоритм времени для определения идеальной команды перехода?
Как указанов другом вопросе , этот начальный с малого алгоритм не обязательно является оптимальным с учетом достаточно продвинутых конструкций.Я хотел бы предположить следующие ограничения вежливости:
- условное включение кода и расширение макроса уже произошло к моменту выбора инструкций и не может зависеть от этих решений
если на размер объекта данных влияет расстояние между двумя явными или неявными метками, размер увеличивается монотонно с расстоянием.Например, допустимо написать
.space foo-bar
, если bar не встречается до foo.
- в нарушение предыдущего ограничения, директивы выравнивания могут существовать