Por que a atribuição estática-única é preferida ao estilo de passagem de continuação em muitos compiladores usados ​​pelo setor?

De acordo com a página da Wikipedia sobre atribuição estática-única (SSA) , o SSA é usado por projetos grandes e conhecidos, como LLVM, GCC, MSVC, Mono, Dalvik, SpiderMonkey e V8, enquanto a página em projetos usa o estilo de passagem de continuação (CPS) é um pouco ausente em comparação.

Eu tenho essa noção de que o CPS é preferido por compiladores e intérpretes que implementam linguagens principalmente funcionais - particularmente Haskell e Scheme parecem ter fortes inclinações em relação ao estilo do CPS devido às restrições de mutação ou necessidade de suporte continuado de primeira classe (eu acho que que o Smalltalk também precisaria disso). A principal literatura que encontrei que usa o CPS parece ser a que trabalha principalmente no Scheme ou está relacionada ao Scheme de alguma forma.

Existe alguma razão específica para o uso do SSA na indústria, além do momento de adoção? SSA e CPS têm um relacionamento próximo; isso significa que seria fácil afirmar em termos de outro, mas talvez a representação da informação seja menos compacta ou menos eficiente para o CPS.

Eu imagino que muitos implementadores de compilador para linguagens imperativas típicas simplesmente não estavam familiarizados com as técnicas de compilação baseadas em CPS e CPS. Na comunidade de programação funcional, a compilação baseada no CPS e no CPS são técnicas muito conhecidas - a última do trabalho de Guy Steele. No entanto, mesmo na comunidade de FP, a maioria dos compiladores não usa técnicas baseadas em CPS para compilação, a menos que a própria linguagem ofereça suporte a operadores de controle call/cc. Algo mais parecido com o Formulário Normal Administrativo (ANF) (às vezes também conhecido como Formulário Normal Monádico, que está intimamente relacionado por razões que ficarão claras) é usado, o qual tem uma relação ainda mais estreita com a SSA do que a CPS .

Se bem me lembro, o formulário normal administrativo recebe esse nome pelo fato de que a compilação baseada no CPS pode levar a redexes beta no código intermediário que não corresponde a nada no código-fonte. Estes foram referidos como "redexos administrativos". Isso pode ser reduzido no tempo de compilação, mas houve uma boa quantidade de pesquisas sobre a execução de uma transformação CPS que produziria código sem os redexos administrativos em primeiro lugar. O objetivo era produzir saída de forma normal, onde todos os redexes "administrativos" eram reduzidos, e essa era a origem da Forma Normal Administrativa. Não demorou muito para perceber que não havia muitos benefícios em vê-lo como um (n otimização de) um processo de duas etapas: transformação CPS, redução de redexos administrativos. Em particular, a forma normal administrativa parece um pouco com o estilo monádico, como praticado (à mão), principalmente em Haskell. A transformação CPS pode ser entendida como uma conversão para o estilo monádico, onde você está usando a mônada do CPS (portanto, existem várias maneiras de "converter" para o estilo monádico correspondentes a diferentes ordens de avaliação). Em geral, porém, você pode estar usando uma mônada bem diferente e, portanto, a conversão para o estilo monádico e, portanto, a forma normal administrativa não está realmente relacionada ao CPS em particular.

No entanto, houve alguns benefícios para a CPS versus a ANF. Em particular, houve certas otimizações que você poderia fazer no CPS com otimizações padrão, como a redução beta, que exigiam (aparentemente) regras ad-hoc para o ANF. Da perspectiva monádica, essas regras correspondem a conversões pendulares. O resultado é que agora existe uma teoria que pode explicar quais regras devem ser adicionadas e por quê. Um artigo recente fornece uma descrição (nova e) bastante clara disso (de uma perspectiva lógica) e sua seção de trabalho relacionada serve como uma breve mas decente pesquisa e referências na literatura sobre os tópicos que mencionei.

O problema com o CPS está atrelado a um de seus principais benefícios. A transformação do CPS permite implementar operadores de controle como call/ccesse, mas isso significa que toda chamada de função não local no código intermediário do CPS deve ser tratada como potencialmente executando efeitos de controle. Se o seu idioma inclui operadores de controle, é exatamente como deveria ser (embora, mesmo assim, a maioria das funções provavelmente não esteja realizando nenhuma mudança de controle). Se seu idioma não inclui operadores de controle, existem invariantes globais no uso de continuações que não são evidentes localmente. Isso significa que há otimizações que não são adequadas para executar no código CPS geral que seriam adequadas para esse uso particularmente bem-comportado do CPS. Uma maneira de isso se manifestar éa mudança na precisão dos dados e análises de fluxo de controle . (A transformação do CPS ajuda em alguns aspectos, prejudica em outros, embora os modos em que ela se deva sejam principalmente devidos à duplicação, e não ao próprio aspecto do CPS.) ¹ Você pode, é claro, adicionar regras e ajustar análises para compensar isso (ou seja, explorar os invariantes globais), mas você derrotou parcialmente um dos principais benefícios da compilação baseada no CPS, que é a de que muitas otimizações ad-hoc (aparentemente) de propósito especial se tornam casos especiais de otimização de uso geral (particularmente redução beta) )

Por fim, a menos que seu idioma tenha operadores de controle, geralmente não há muitos motivos para usar um esquema de compilação baseado em CPS. Depois de compensar os problemas que mencionei acima, você normalmente elimina os benefícios da compilação baseada no CPS e produziu algo equivalente ao não uso do CPS. Nesse ponto, o CPS está apenas criando um código intermediário com aparência complicada, sem muito benefício. Um argumento para a compilação baseada no CPS de 2007 aborda alguns desses problemas e apresenta outros benefícios usando uma forma diferente de conversão do CPS. As coisas que o artigo traz são cobertas em parte pelo artigo (2017) que mencionei antes.

¹ A equivalência entre SSA e CPS torna isso mais ou menos impossível? Não. Uma das primeiras coisas que o artigo que introduz essa equivalência afirma é que a equivalência não funciona para código CPS arbitrário , mas funciona para a saída de uma transformação CPS (que eles definem) para um idioma sem operadores de controle.

Eu não sou um especialista em compilador, então, leve o que digo com um pouco de sal. Espero que um especialista em compilador real entre em contato. Me disseram que:

• O código CPS tende a pular muito não localmente, o que arruina a localidade do cache e, portanto, o desempenho.
• O CPS requer uma coleta de lixo mais cara que a compilação convencional, que normalmente pode armazenar muitas coisas na pilha (que é mais rápida para alocar e desalocar).

Ambos conspiram para tornar o código compilado pela transformação CPS comparativamente lento.