Почему алгоритм «начать с малого» для смещения ветвей не оптимален?
[вопрос выделен жирным шрифтом внизу]
Когда ассемблер генерирует двоичную кодировку, он должен решить, сделать ли каждую ветку длинной или короткой, если короткая лучше, если это возможно. Эта часть ассемблера называетсяалгоритм оптимизации смещения ветвей (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 или существуетреалистический случай, когда он не обеспечивает минимальный размер кодирования для всех ветвей?