Оптимизатор SPF
By Azamadt SmaguloffprofiT. Sunday, April 13, 2008 9:00:26 AM
Поставим вопросы касающиеся оптимизации форта в список, от вопросов общего характера до более конкретных:
- Как вообще можно оптимизировать форт (или стековые языки вообще)? Какие подходы используются для этого? Каковы характерные особенности форт-программ с точки зрения оптимизации?
- Какие методы оптимизации используют существующие форт-системы? Каким образом они оцениваются (т.е.: "где бенчмарк?")?
- Как работает оптимизатор SPF?
- Оптимизация основанная на шаблонах машинного кода ("если последние столько-то байт скомпилированного кода выглядят так-то и так-то -- делать то-то и то-то"). Именно эти шаблоны и реакции на них составляют подавляющую часть 100 с лишним килобайт оптимизатора (файл src/macroopt.f ). Пример типичного подобного правила см. у автора: Forth.Wiki: Оптимизирующий компилятор.
- Оптимизация условных переходов, например типичная комбинация 10 > IF ... THEN падает не в последовательность действий: укладка на стек литерала 10, сравнение двух вехних значений и запись результата на стек и затем проверки флага с условным переходом а в две машинные команды:
lib/ext/disasm.f<br /> <span style='color:#000084; font-weight:bold; '>:NONAME </span><span style='color:#000084; font-weight:bold; '>DUP </span><span style='color:#008c00; '>10 </span><span style='color:#000084; font-weight:bold; '>> </span><span style='color:#800000; '>IF </span><span style='color:#008c00; '>1 </span><span style='color:#000084; font-weight:bold; '>. </span><span style='color:#800000; '>THEN</span><span style='color:#000084; font-weight:bold; '> ;</span> REST
Вывод:<span style='color:#000084; font-weight:bold; '>cmp</span> eax, # A<br /> <span style='color:#000084; font-weight:bold; '>jle </span><span style='color:#800000; '>@@1</span><br /> ...<br /> <span style='color:#800000; '>@@1:</span><br />
Похожим образом обрабатываются другие типичные комбинации 2DUP = IF ... THEN и им подобные:lib/ext/disasm.f<br /> <span style='color:#000084; font-weight:bold; '>:NONAME </span><span style='color:#000084; font-weight:bold; '>2DUP </span><span style='color:#000084; font-weight:bold; '>= </span><span style='color:#800000; '>IF </span><span style='color:#008c00; '>1 </span><span style='color:#000084; font-weight:bold; '>. </span><span style='color:#800000; '>THEN</span><span style='color:#000084; font-weight:bold; '> ;</span> REST<br />
Вывод:<span style='color:#000084; font-weight:bold; '>cmp</span> eax, <span style='color:#008c00; '>0</span> [ebp] <span style='color:#000084; font-weight:bold; '>jne </span><span style='color:#800000; '>@@1</span><br /> ...<br /> <span style='color:#800000; '>@@1:</span>
Оптимизируются последовательности логических операций (0= здесь аналогичен отрицанию, поэтому последовательность 0< 0= означает "больше или равно нулю" ):lib/ext/disasm.f<br /> <span style='color:#000084; font-weight:bold; '>:NONAME </span><span style='color:#000084; font-weight:bold; '>DUP</span> 0< <span style='color:#000084; font-weight:bold; '>0= </span><span style='color:#800000; '>IF </span><span style='color:#008c00; '>1 </span><span style='color:#000084; font-weight:bold; '>. </span><span style='color:#800000; '>THEN</span><span style='color:#000084; font-weight:bold; '> ;</span> REST
Вывод:<span style='color:#000084; font-weight:bold; '>or</span> eax, eax<br /> <span style='color:#000084; font-weight:bold; '>jl </span><span style='color:#800000; '>@@1</span><br /> ...<br /> <span style='color:#800000; '>@@1:</span>
- Компиляция слов порождаемых словами CREATE, VARIABLE, VALUE, USER. При компиляции переменных или констант, вместо записи простого вызова DOES-действия порождённого слова, запускается процедура специальной обработки которая разворачивает вызов в аналогичную последовательность машинного кода. Например:
lib/ext/disasm.f<br /> <span style='color:#008c00; '>10 </span><span style='color:#000084; font-weight:bold; '>CONSTANT </span><span style='color:#000084; font-weight:bold; '>c</span><br /> <span style='color:#000084; font-weight:bold; '>:NONAME</span> c<span style='color:#000084; font-weight:bold; '> ;</span> REST<br /> <br /> <span style='color:#008c00; '>10 </span><span style='color:#000084; font-weight:bold; '>VALUE </span><span style='color:#000084; font-weight:bold; '>vl</span><br /> <span style='color:#000084; font-weight:bold; '>:NONAME</span> vl<span style='color:#000084; font-weight:bold; '> ;</span> REST<br /> <br /> <span style='color:#000084; font-weight:bold; '>VARIABLE </span><span style='color:#000084; font-weight:bold; '>vr</span><br /> <span style='color:#000084; font-weight:bold; '>:NONAME</span> vr <span style='color:#000084; font-weight:bold; '>@</span><span style='color:#000084; font-weight:bold; '> ;</span> REST
Вывод:<span style='color:#000084; font-weight:bold; '>mov</span> <span style='color:#008c00; '>-4</span> [ebp] , eax<br /> <span style='color:#000084; font-weight:bold; '>mov</span> eax , # A<br /> <span style='color:#000084; font-weight:bold; '>lea</span> ebp , <span style='color:#008c00; '>-4</span> [ebp}<br /> <span style='color:#000084; font-weight:bold; '>ret</span><br /> <br /> <span style='color:#000084; font-weight:bold; '>mov</span> <span style='color:#008c00; '>-4</span> [ebp] , eax<br /> <span style='color:#000084; font-weight:bold; '>mov</span> eax , <span style='color:#008c00; '>572410</span> ( vl+<span style='color:#008c00; '>5</span> )<br /> <span style='color:#000084; font-weight:bold; '>lea</span> ebp , <span style='color:#008c00; '>-4</span> [ebp]<br /> <span style='color:#000084; font-weight:bold; '>ret</span><br /> <br /> <span style='color:#000084; font-weight:bold; '>mov</span> <span style='color:#008c00; '>-4</span> [ebp] , eax<br /> <span style='color:#000084; font-weight:bold; '>mov</span> eax , 57243C ( vr+<span style='color:#008c00; '>5</span> )<br /> <span style='color:#000084; font-weight:bold; '>lea</span> ebp , <span style='color:#008c00; '>-4</span> [ebp]<br /> <span style='color:#000084; font-weight:bold; '>ret</span>
- Статистика форт-слов собранная по большой базе рабочих исходников -- forth.org.ru/~day/stat.html.
- Тест-производительности форт-систем (целочисленные операции, пересылка памяти, сортировки и т.д.): www.mpeforth.com/arena/benchmrk.fth
- Заметка на Forth.Wiki автора оптимизатора SPF: Оптимизирующий компилятор.
- MPE VFX Forth -- быстрая коммерческая форт-система.
- SwiftForth -- быстрая коммерческая форт-система.
- iForth -- быстрая коммерческая форт-система (к сожалению получить её копию можно только по почте).







Anonymous # Monday, April 21, 2008 3:19:05 AM
Azamadt SmaguloffprofiT # Monday, April 21, 2008 1:30:39 PM
(вообще-то эта ссылка была в каком-то из черновиков)
Anonymous # Thursday, April 24, 2008 3:21:55 AM
Anonymous # Thursday, July 31, 2008 11:32:49 PM
Azamadt SmaguloffprofiT # Friday, August 1, 2008 12:26:49 PM
Ех.
exs # Saturday, August 2, 2008 6:31:24 PM
Azamadt SmaguloffprofiT # Saturday, August 2, 2008 6:47:43 PM