Про супероптимизатор я, похоже, не упоминал.
http://research.swtch.com/2008/01/superoptimizer.html - краткое введение со ссылочками.
Смысл очень простой: берём на входе функцию и перебираем последовательности команд, чтобы они прошли тесты для этой функции. В команды не входят переходы, надо отметить.
Вот пример целевой функции из goals.def:
DEF_GOAL (MAXS, 2, "maxs", { r = (signed_word) v0 > (signed_word) v1 ? v0 : v1; })Максимум двух чисел со знаком.
Вот вариант x86 ассемблерного кода от супероптимизатора:
1: subl %eax,%edx
addl %edx,%eax
sbbl %ecx,%ecx
andl %edx,%ecx
subl %ecx,%eax
Вот та же функция на ассемблере Альфа:
1: r2:=cmpleu(r1,r0)
r0:=cmoveq(r2,r1)
HP Precision Architecture (у них есть флаги результата! обалдеть):
1: r2:=adc_co_sltu(r1,r0)
r0:=add_co(r2,r0)
И тп.
Даже просто посмотреть на длины последовательностей инструкций и то очень интересно.
Меня задело, что доступные супероптимизатору интеловские процессора (x86, i960) справляются за большее количество инструкций, чем другие архитектуры. ;)
А POWER/PowerPC/SPARC и тп проигрывают Альфе и PA-RISC. ;)
PS
Вдогонку.
Приём с таблицами определений (вон, наверху приведено определение целевой функции, которое разворачивается в разные куски кода при подстановке) я увидел впервые именно в GNU superoptimizer.
Смысл очень простой: берём на входе функцию и перебираем последовательности команд, чтобы они прошли тесты для этой функции. В команды не входят переходы, надо отметить.
Вот пример целевой функции из goals.def:
DEF_GOAL (MAXS, 2, "maxs", { r = (signed_word) v0 > (signed_word) v1 ? v0 : v1; })Максимум двух чисел со знаком.
Вот вариант x86 ассемблерного кода от супероптимизатора:
1: subl %eax,%edx
addl %edx,%eax
sbbl %ecx,%ecx
andl %edx,%ecx
subl %ecx,%eax
Вот та же функция на ассемблере Альфа:
1: r2:=cmpleu(r1,r0)
r0:=cmoveq(r2,r1)
HP Precision Architecture (у них есть флаги результата! обалдеть):
1: r2:=adc_co_sltu(r1,r0)
r0:=add_co(r2,r0)
И тп.
Даже просто посмотреть на длины последовательностей инструкций и то очень интересно.
Меня задело, что доступные супероптимизатору интеловские процессора (x86, i960) справляются за большее количество инструкций, чем другие архитектуры. ;)
А POWER/PowerPC/SPARC и тп проигрывают Альфе и PA-RISC. ;)
PS
Вдогонку.
Приём с таблицами определений (вон, наверху приведено определение целевой функции, которое разворачивается в разные куски кода при подстановке) я увидел впервые именно в GNU superoptimizer.