Неправильный компилятор: оптимизация
Ранее у меня была реализована простая оптимизация, когда арифметические операции с константами вычислялись при компиляции. Она работает в пределах выражения LeoC, чего раньше вполне хватало. В ходе прошлого рефакторинга код верхнего уровня компилятора (Leo -> LeoC) сильно сократился, потому что в ряде мест (циклы, присваивания) набор сочетаний частных случаев был заменен более универсальным кодом. Это привело к генерации менее оптимального результата, в частности, стало генериться много подобного кода LeoC:
bound_12 = 19
i_13 = 0
end_13 = bound_12 + 1
while i_13 < end_12 ...Поэтому вчера добавил еще пару простых оптимизаций: copy propagation и удаление неиспользуемых переменных и вычислений. Первая заключается в том, чтобы пройтись по дереву сгенеренного LeoC-кода и для каждой встреченной переменной запоминать ее "значение":
type var_value = Undefined | Copy of rvalue | ComplexUndefined она после объявления и до первого присваивания. Если в присваивании слева стоит переменная, а справа - константа или переменная, то для присваиваемой переменной запоминается, копией чего она является, в противном случае она помечается как Complex. Когда переменная встречается в выражении, смотрится ее "значение" и, если она содержит копию чего-то, то вместо нее подставляется это что-то. После этого выражение упрощается путем constant folding. Кроме этого контекст содержит множество переменных, измененных в текущем блоке кода. Когда встречается if с двумя блоками-ветками, то после него все измененные в ветках переменные помечаются как Complex, т.е. их значения перестают быть известными. Аналогично для цикла, только там сначала делается один проход по телу и собирается набор измененных переменных, а потом во втором проходе уже тело оптимизируется.
Вторая оптимизация идет по дереву LeoC-кода и для каждого блока в первом проходе собирает множество используемых переменных, а во втором проходе выкидывает определения и присваивания переменных, которые нигде не используются.
Вместе они добавили еще 170 строк к компилятору и, во-первых, сделали генерируемый код не таким позорным, а во-вторых, в сочетании с always-inline подходом к компиляции нерекурсивных функций позволили делать прикольные compile-time вычисления, о которых в следующем посте.
bound_12 = 19
i_13 = 0
end_13 = bound_12 + 1
while i_13 < end_12 ...Поэтому вчера добавил еще пару простых оптимизаций: copy propagation и удаление неиспользуемых переменных и вычислений. Первая заключается в том, чтобы пройтись по дереву сгенеренного LeoC-кода и для каждой встреченной переменной запоминать ее "значение":
type var_value = Undefined | Copy of rvalue | ComplexUndefined она после объявления и до первого присваивания. Если в присваивании слева стоит переменная, а справа - константа или переменная, то для присваиваемой переменной запоминается, копией чего она является, в противном случае она помечается как Complex. Когда переменная встречается в выражении, смотрится ее "значение" и, если она содержит копию чего-то, то вместо нее подставляется это что-то. После этого выражение упрощается путем constant folding. Кроме этого контекст содержит множество переменных, измененных в текущем блоке кода. Когда встречается if с двумя блоками-ветками, то после него все измененные в ветках переменные помечаются как Complex, т.е. их значения перестают быть известными. Аналогично для цикла, только там сначала делается один проход по телу и собирается набор измененных переменных, а потом во втором проходе уже тело оптимизируется.
Вторая оптимизация идет по дереву LeoC-кода и для каждого блока в первом проходе собирает множество используемых переменных, а во втором проходе выкидывает определения и присваивания переменных, которые нигде не используются.
Вместе они добавили еще 170 строк к компилятору и, во-первых, сделали генерируемый код не таким позорным, а во-вторых, в сочетании с always-inline подходом к компиляции нерекурсивных функций позволили делать прикольные compile-time вычисления, о которых в следующем посте.