Неправильный компилятор: оптимизация

Ранее у меня была реализована простая оптимизация, когда арифметические операции с константами вычислялись при компиляции. Она работает в пределах выражения 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 | Complex

Undefined она после объявления и до первого присваивания. Если в присваивании слева стоит переменная, а справа - константа или переменная, то для присваиваемой переменной запоминается, копией чего она является, в противном случае она помечается как Complex. Когда переменная встречается в выражении, смотрится ее "значение" и, если она содержит копию чего-то, то вместо нее подставляется это что-то. После этого выражение упрощается путем constant folding. Кроме этого контекст содержит множество переменных, измененных в текущем блоке кода. Когда встречается if с двумя блоками-ветками, то после него все измененные в ветках переменные помечаются как Complex, т.е. их значения перестают быть известными. Аналогично для цикла, только там сначала делается один проход по телу и собирается набор измененных переменных, а потом во втором проходе уже тело оптимизируется.

Вторая оптимизация идет по дереву LeoC-кода и для каждого блока в первом проходе собирает множество используемых переменных, а во втором проходе выкидывает определения и присваивания переменных, которые нигде не используются.

Вместе они добавили еще 170 строк к компилятору и, во-первых, сделали генерируемый код не таким позорным, а во-вторых, в сочетании с always-inline подходом к компиляции нерекурсивных функций позволили делать прикольные compile-time вычисления, о которых в следующем посте.

Fun with Leo: metaprogramming for free

Поскольку нерекурсивные функции в Leo раскрываются подстановкой, и лишь потом это дело типизируется и компилируется в LeoC, сам собой получился вариант лямбда-исчисления, позволяющий делать всякие штуки в compile-time. Поскольку язык лишь частично функциональный, в нем пока нет карринга и возможности возвращать функции, поэтому выглядит это не очень красиво, но терпимо. Пример:

# Church numerals
zero(f, x) = x
add1(n, f, x) = f(n(f, x))
add(a, b, f, x) = a(f, b(f, x))
mul(a, b, f, x) = a(\t -> b(f, t), x)

one(f, x) = add1(zero, f, x)
two(f, x) = add(one, one, f, x)
three(f, x) = add(one, two, f, x)
four(f, x) = add(two, two, f, x)
six(f, x) = mul(two, three, f, x)
seven(f, x) = add(four, three, f, x)
c42(f, x) = mul(six, seven, f, x)

inc(x) = x + 1
z = c42(inc, 0)
print(z)

Благодаря новым оптимизациям, все это компилируется в одну сточку LeoC: print(42). И, соответственно, одну команду ВМ.

Использовать это можно для генерации кода. Например, функция, которая в compile-time создает массив байтов и заполняет его значениями 1..n:

to_int(n) = n(inc, 0)

make(n) = do # на входе - число Черча с количеством требуемых элементов
  m = new byte[ to_int(n) ] # создать массив
  f(x) = { t = x+1; m[x] <- t; t }
  n(f, 0) # f будет вызван и подставлен n раз
  m # вернуть массив
end

ten(f,x) = add(four, six, f, x)
a = make(ten)
print(a[|a|-1])

Компилируется в такой код на LeoC:

var m_287
m_287 <- new [10]
$Mem[m_287] <-b- 1
$Mem[m_287 + 1] <-b- 2
$Mem[m_287 + 2] <-b- 3
$Mem[m_287 + 3] <-b- 4
$Mem[m_287 + 4] <-b- 5
$Mem[m_287 + 5] <-b- 6
$Mem[m_287 + 6] <-b- 7
$Mem[m_287 + 7] <-b- 8
$Mem[m_287 + 8] <-b- 9
$Mem[m_287 + 9] <-b- 10
var a
a <- m_287  
print(byte($Mem[a + 9]))