Почему статическое одиночное назначение предпочтительнее стиля передачи продолжения во многих используемых в отрасли компиляторах?

Согласно странице Википедии о статическом одиночном назначении (SSA) , SSA используется крупными и известными проектами, такими как LLVM, GCC, MSVC, Mono, Dalvik, SpiderMonkey и V8, в то время как страница с проектами использует стиль прохождения продолжения. (CPS) немного не хватает в сравнении.

У меня есть представление, что CPS предпочитают компиляторы и интерпретаторы, которые реализуют в основном функциональные языки - в частности, Haskell и Scheme, похоже, сильно склонны к стилю CPS из-за ограничений на мутацию или необходимости первоклассной поддержки продолжения (я думаю что Smalltalk, возможно, будет нуждаться в этом также). Основная литература, с которой я столкнулся, которая использует CPS, кажется, является той, которая в основном работает над Схемой или связана со Схемой в некотором отношении.

Есть ли какая-то особая причина, по которой SSA используется в промышленности, помимо импульса принятия? SSA и CPS имеют тесные отношения; это означает, что было бы легко заявить либо с точки зрения другого, но, возможно, представление информации будет менее компактным или менее эффективным для CPS.

Я полагаю, что многие разработчики компиляторов для типичных императивных языков просто не были знакомы с методами компиляции CPS и CPS. В сообществе функционального программирования как CPS, так и компиляция на основе CPS являются очень хорошо известными методами - последними из работ Гая Стила. Тем не менее, даже в сообществе FP большинство компиляторов не используют методы компиляции, основанные на CPS, если только сам язык не поддерживает подобные управляющие операторы call/cc. Используется нечто более похожее на административную нормальную форму (ANF) (иногда ее также называют монадической нормальной формой, которая тесно связана по причинам, которые станут ясны), которая имеет более тесные отношения с SSA, чем CPS .

Если я правильно помню, административная нормальная форма получила свое название от того факта, что компиляция на основе CPS может привести к бета-переопределениям в промежуточном коде, которые не соответствуют чему-либо в исходном коде. Их называли «административными переопределениями». Они могут быть уменьшены во время компиляции, но было проведено большое количество исследований по выполнению CPS-преобразования, которое в первую очередь выводило бы код без административных переопределений. Тогда цель состояла в том, чтобы произвести выходные данные в нормальной форме, где все «административные» переопределения были сокращены, и это было источником административной нормальной формы. Не потребовалось много времени, чтобы понять, что не было особой пользы, чтобы рассматривать это как (n оптимизацию) двухэтапного процесса: преобразование CPS, сокращение административных переопределений. Особенно, административная нормальная форма выглядит скорее как монадический стиль, как это практикуется (вручную), особенно в Haskell. Преобразование CPS можно понимать как преобразование в монадический стиль, когда вы просто используете монаду CPS (так что на самом деле существует несколько способов «преобразовать» в монадный стиль, соответствующий различным порядкам оценки). В целом, тем не менее, вы можете использовать совершенно другую монаду, и поэтому преобразование в монадный стиль и, следовательно, административную нормальную форму на самом деле не имеет отношения к CPS.

Тем не менее, у CPS были некоторые преимущества по сравнению с ANF. В частности, были определенные оптимизации, которые вы могли бы выполнить в CPS только с помощью стандартных оптимизаций, таких как уменьшение бета-версии, которые требовали (казалось бы) специальных правил для ANF. С монадической точки зрения эти правила соответствуют коммутирующим преобразованиям. В результате появилась теория, которая может объяснить, какие правила следует добавить и почему. Недавняя статья дает (новое и) довольно четкое описание этого (с логической точки зрения) и связанный с ним раздел работы служит краткой , но приличном обследования и ссылки в литературу по темам , которые я упоминаю.

Проблема с CPS связана с одним из его основных преимуществ. Преобразование CPS позволяет реализовывать управляющие операторы подобно call/cc, но это означает, что каждый нелокальный вызов функции в промежуточном коде CPS должен рассматриваться как потенциально выполняющий управляющие эффекты. Если ваш язык включает управляющие операторы, то это так и должно быть (хотя даже тогда большинство функций, вероятно, не выполняют никаких управляющих махинаций). Если ваш язык не включает управляющие операторы, то существуют глобальные инварианты использования продолжений, которые не очевидны локально. Это означает, что есть оптимизация, которая нецелесообразна для выполнения общего кода CPS, что было бы неплохо для этого особенно хорошо используемого CPS. Один из способов это проявляется визменение точности данных и анализ потоков управления . (Преобразование CPS помогает в некоторых отношениях, в других - вредно, хотя в большинстве случаев это объясняется дублированием, а не самим аспектом CPS.) ¹ Конечно, можно добавить правила и скорректировать анализ, чтобы компенсировать это (т. Е. Использовать глобальные инварианты), но затем вы частично победили одно из главных преимуществ компиляции на основе CPS, а именно то, что многие (казалось бы) специальные специализированные оптимизации становятся частными случаями оптимизации общего назначения (особенно бета-сокращения) ).

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

¹ Разве эквивалентность между SSA и CPS не делает это более или менее невозможным? Нет. Одна из первых вещей, в которой вводятся эти состояния эквивалентности, заключается в том, что эквивалентность не работает для произвольного кода CPS, но она работает для вывода преобразования CPS (которое они определяют) для языка без управляющих операторов.

Я не эксперт по компилятору, так что примите то, что я говорю, с долей соли, я надеюсь, что настоящий эксперт по компилятору примет участие. Мне сказали, что:

• Код CPSed имеет тенденцию многократно перемещаться не локально, что разрушает локальность кэша и, следовательно, производительность.
• CPS требует более дорогой сборки мусора, чем обычная компиляция, которая обычно может хранить много вещей в стеке (который быстрее распределяется и освобождается).

Оба стремятся сделать код, скомпилированный с помощью CPS-преобразования, сравнительно медленным.