¿Por qué el algoritmo de "inicio pequeño" para el desplazamiento de rama no es óptimo?
[pregunta en negrita en la parte inferior]
Cuando un ensamblador genera una codificación binaria, debe decidir si hacer que cada rama sea larga o corta, lo mejor será corto, si es posible. Esta parte del ensamblador se llamaAlgoritmo de optimización de desplazamiento de rama (BDO). Un enfoque típico es que el ensamblador hacetodas las codificaciones de ramificación son cortas (si son inferiores a algún umbral), entonces aumentan iterativamente cualquier salto de ramificación a longs que no alcanzan. Esto, por supuesto, puede hacer que otras ramas se conviertan en saltos largos. Por lo tanto, el ensamblador debe seguir pasando por la lista de salto hasta que no se requiera un aumento de tamaño. Este enfoque de tiempo cuadrático parece ser un algoritmo óptimo para mí, pero supuestamente BDO es NP completo y este enfoque no es realmente óptimo.
Randall Hyde proporcionó un contraejemplo:
.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
Al agregar la parte entre paréntesis "[cerca de ptr]" y forzar una codificación de 5 bytes, el binario en realidad termina siendo más corto porque la matriz asignada es más pequeña por el doble de la cantidad de salto. Por lo tanto, al acortar la codificación de salto, el código final es en realidad más largo.
Esto me parece un caso extremadamente patológico, y no es realmente relevante porque las codificaciones de ramificación son aún más pequeñas, es solo este extraño efecto secundario en una parte no ramificada del programa, lo que hace que el binario se agrande. Como las propias codificaciones de ramificación son aún más pequeñas, realmente no considero que sea un contraejemplo válido para el algoritmo de "inicio pequeño".
¿Puedo considerar el algoritmo start-small como un algoritmo BDO óptimo o existe unrealista caso en el que no proporciona un tamaño de codificación mínimo para todas las ramas?