📚 Breno Campos, Ferreira Guimarães
"Lazy Evaluation for the Lazy: Automatically Transforming Call-by-Value into Call-by-Need"
Proceedings of the 32nd ACM SIGPLAN International Conference on Compiler Construction. February 2023: 239–249

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

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

Цель авторов — научить компиляторы находить вычисления, которые предпочтительно сделать ленивыми, не используя аннотирование lazy вручную и даже поддержку ленивости со стороны языка. Для этого они реализовали внутри LLVM специальную profile-guided оптимизацию, делающую вычисление некоторых аргументов функций ленивым. Оптимизация происходит на уровне LLVM IR в SSA форме.

Статья описывает два алгоритма:
1) модификацию Value Slicing, которая строит замыкание для вычисления произвольного значения в SSA IR.
2) Lazification по информации от профилировщика заменяет call-by-value на call-by-need.

Выбор вычислений для lazification и необходимое профилирование программы описаны в более ранней статье:
Chang, Stephen. "Laziness by need." Programming Languages and Systems: 22nd European Symposium on Programming, ESOP 2013

Авторы добились роста производительности программ на C и C++ от 1% до ~10% за счет увеличения размера на ~10%; тесты включают в себя SPEC CPU 2017.

#optimization #profiling #lazy #llvm