Как эффективно реализовать замыкания в LLVM IR? - PullRequest
Новая
       40

Как эффективно реализовать замыкания в LLVM IR?

23 голосов
/ 03 января 2012

Я начал добавлять замыкания (лямбды) в мой язык, который использует LLVM в качестве бэкэнда.Я реализовал их для простых случаев, когда их всегда можно встроить, т. Е. Код для самого определения замыкания не нужно генерировать, поскольку он встроен там, где он используется.

Но как сгенерировать код для замыканияв случае, если замыкание не всегда встроено (например, оно передается другой функции, которая не встроена).Предпочтительно, чтобы сайты вызовов не заботились о том, передаются ли им обычные функции или замыкания, и будут ли они вызываться как обычные функции.

Я мог бы сгенерировать функцию с синтетическим именем, но для этого нужно было бы использовать среду ссылокв качестве дополнительного аргумента, и эта функция не может быть просто передана другой функции, которая не знает о необходимом дополнительном аргументе.

Я подумал об одном возможном решении, использующем батутные присадки LLVM, который "вырезает"один параметр из функции, возвращающий указатель на функцию батута, которая принимает на один параметр меньше.В этом случае, если функция, сгенерированная для замыкания, взяла в качестве первого параметра среду ссылки, я мог бы удалить ее и вернуть функцию, которая принимает ровно столько параметров, сколько фактически объявляет замыкание.Это звучит выполнимо?Эффективное?Есть ли лучшие решения?

Пример кода: 

def applyFunctionTo(value: Int, f: (Int) -> Int) = f(value)

def main() = {
  val m := 4;
  val n := 5;
  val lambda := { (x: Int) => x + m + n };
  applyFunctionTo(3, lambda)
}

Теперь давайте представим, что это не будет встроено в def main() = 3 + 4 + 5 и что applyFunctionTo возможно будет скомпилировано отдельнои мы не можем изменить сайт вызова там.С батутом, я думаю, что сгенерированный код будет примерно таким (выражается в псевдокоде, * означает указатель): 

def main$lambda$1(env: {m: Int, n: Int}*, x: Int) = x + env.m + env.n
def main() = {
  m = 4
  n = 5
  env* = allocate-space-for {Int, Int}
  env = {m, n}
  tramp* = create-trampoline-for(main$lambda$1*, env*)
  return applyFunctionTo(3, tramp*)
  // release memory for env and trampoline if the lambda didn't escape
}

Кажется ли это правильным?

Ответы [ 2 ]

8 голосов
/ 03 января 2012

Звучит выполнимо и эффективно.

Альтернативный способ, который не требует батутов, состоит в том, чтобы определить тип замыкания как пару указателей на функции и указатель на среду, то есть указатель стека.В соглашении о вызовах C дополнительные аргументы игнорируются, поэтому, если вы предоставляете среду в качестве последнего аргумента, вы даже можете использовать (function_ptr, null) в качестве обратного вызова для обычной функции.

1 голос
/ 09 января 2012

Глупая идея заключается в том, что для каждого замыкания вы генерируете локальную структуру потока для хранения требуемых данных (может быть просто указатель на локальную структуру или несколько указателей).

Создатель замыканияотвечает за установку переменных TLS и «сохранение» своего состояния (для разрешения рекурсивного вызова).

Затем пользователь вызывает функцию в обычном режиме, она выполняется и использует environemnt.

После вызова создатель замыкания «восстанавливает» исходные значения в переменные TLS.

...