O que há de novo nas técnicas de otimização do compilador nos últimos anos?

14

Estou interessado em otimizar o fluxo de dados e controlar gráficos de fluxo e, em particular, mais complexo computacionalmente. Mas também será interessante conhecer as últimas invenções no campo das otimizações de olho mágico.

optimization compilers Evgeny Gavrin
fonte
2
Na minha tese ( slides ), discuti e implementei o achatamento de gráficos de chamada no LLVM; basicamente, é uma transformação interprocedural que elimina a noção de "função" porque mescla todo o código, permitindo várias possibilidades interessantes, como movimento de código interprocedural, convenções de chamada otimizadas para sites de chamadas, execução sem pilha e assim por diante.
CAFxX 01/12/11
@CAFxX: slides travaram no Open Office. Você tem fotos on-line?
Yttrill
@Yttrill: slideshare.net/CAFxX/…
CAFxX
Obrigado, capaz de ver com isso, embora os gráficos fossem muito bons para ficarem visíveis, o texto era bom.
Yttrill

Respostas:

8

Não tenho certeza de quão inovador é, ou se é muito do lado aplicado para o seu interesse, mas Hoopl mostra como uma otimização de controle / fluxo de dados pode ser modularizada, com a propagação de fatos sobre os vértices do gráfico de controle independentes do linguagem e otimização específica.

Eles fazem referência a um algoritmo de 2002 de Lerner, Grove e Chambers que compõe otimizações simples em uma "super otimização".

Máx.
fonte
8

Suponho que a técnica de Saturação da Igualdade , como uma abordagem diferente para o problema da otimização dos pedidos de aprovação, seja relevante. Que eu saiba, no entanto, ainda não foi comprovado por uma implementação concreta em um compilador completo. As seguintes Gerações de otimizações do compilador a partir de provas também podem ser interessantes.

gasche
fonte
6

Houve um renascimento nos compiladores de otimização verificados. Além do artigo de Lerner (mencionado em um comentário anterior), você pode ver o projeto CompCert liderado por Xavier Leroy. Eles fizeram algumas coisas legais ao especificar otimizações como provas verificáveis ​​pela máquina (usando Coq ). Ainda não li os artigos, mas o projeto The Verified Software Toolchain em Princeton também parece estar produzindo resultados interessantes nessa área.

John Lasseter
fonte
1
Também estamos trabalhando em um projeto semelhante ao CompCert: CerCo ( cerco.cs.unibo.it ). Diferentemente do CompCert, nosso objetivo é produzir um compilador de preservação de custos concreto verificado para um grande subconjunto de C (o CompCert mostra apenas que as propriedades extensionais do programa de origem são preservadas pela compilação). Também estamos implementando no compilador algumas otimizações de loop moderadamente complexas, além de otimizações "leves", como a CompCert emprega, que obviamente precisam ser verificadas como preservadoras de custos.
Dominic Mulligan
5

Reconhecer que baz [i] + = force (foo [i], foo [j]) em um loop FOR duplo tem resultados independentes para (i, j) e reordenando as chamadas em uma curva de preenchimento de espaço em (i, j) para reduzir as falhas de cache.

Não é exatamente "olho mágico", mas é bom obter um comportamento inconsciente do cache para "livre".

Chad Brewbaker
fonte