Почему алгоритм «начать с малого» для смещения ветвей не оптимален?

[вопрос выделен жирным шрифтом внизу]

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

Ответы на вопрос(2)

Ваш ответ на вопрос