Agora, o tópico de aprendizado de máquina e inteligência artificial é extremamente popular no momento, graças ao poder computacional dos computadores, idéias e algoritmos que surgiram há muito tempo podem ser implementados e melhorados significativamente. Quase todos os dias você pode ler notícias sobre novas conquistas nesta área. Além disso, o aprendizado de máquina é usado em quase todas as áreas ... e o desenvolvimento de compiladores não é exceção. No entanto, a área é bastante específica e possui características e dificuldades próprias na criação de compiladores inteligentes. Ao mesmo tempo, existem muitos estudos sobre esse assunto e eles são realizados há muito tempo, tanto no ambiente acadêmico quanto em várias empresas.
Onde exatamente está tentando aplicar métodos de aprendizado de máquina ao criar compiladores? E por que até agora os compiladores "inteligentes" não se tornaram parte da vida diária do desenvolvedor?
Opções para usar o aprendizado de máquina no desenvolvimento do compilador
Vamos começar com a primeira pergunta sobre usos específicos do aprendizado de máquina. O fato é que os compiladores modernos são sistemas complexos com um grande número de otimizações que permitem obter código de máquina mais eficiente. No entanto, algumas das otimizações e outras tarefas, como alocação de registros, são NP-completas, o que força os desenvolvedores de compiladores a usar algoritmos heurísticos. Como resultado, a maioria dos compiladores possui um grande número de sinalizadores de otimização que permitem configurar as heurísticas usadas. No LLVM, quase todas as passagens possuem várias opções ocultas que podem afetar sua operação; elas podem ser usadas usando o sinalizador –mllvm ao chamar clang ou no utilitário opt. No entanto, essa variedade de sinalizadores está oculta por trás das opções usadas com mais frequência, que contêm muitas configurações ao mesmo tempo e são geralmente chamadas de níveis de otimização. Para compiladores C / C ++, estes são conhecidos pela maioria dos tipos -O1, -O2, -O3 por otimizar o tempo de execução e -Os por otimizar o tamanho do código. Mas, infelizmente, o código ideal nem sempre é o resultado (especialistas em montadores podem reescrever o código gerado da melhor maneira), depende muito do código-fonte em uma linguagem de alto nível, arquitetura de processador, recursos de linguagem etc.
Apesar de hoje os processadores modernos terem RAM suficiente e desempenho bastante alto, ainda existem áreas em que o desempenho do aplicativo, a eficiência energética e o tamanho do código da máquina desempenham um papel fundamental. Exemplos dessas áreas incluem desenvolvimento de software para sistemas embarcados com uma quantidade limitada de RAM, processamento de sinal digital, sistemas em tempo real, etc. Portanto, nos casos em que você precisa obter código de máquina de alto desempenho para sistemas grandes o suficiente, a seleção das opções de compilação corretas que fornecem o melhor resultado é uma tarefa importante. Além disso, o problema de pior
caso de tempo de execução (
WCET ) não desapareceu quando os sistemas em tempo real precisam calcular e minimizar, se possível, o tempo de execução de uma tarefa específica na plataforma. Até agora, os programadores que trabalham com sistemas com uma quantidade limitada de RAM não podem confiar totalmente nos compiladores e, geralmente, otimizam independentemente o código de máquina gerado.
É difícil para uma pessoa prever quais otimizações darão um bom resultado e quais podem levar a regressões, pois para isso você precisa ter um bom entendimento das complexidades dos algoritmos heurísticos usados, um bom conhecimento da estrutura e passagens do compilador usado e também conhecer completamente o código do programa compilado, que O atual processo de desenvolvimento de aplicativos é impossível. Como resultado, identificar as melhores opções de compilação de um programa para uma pessoa torna-se uma tarefa de pesquisa exaustiva de várias combinações de opções e medidas de desempenho e tamanhos de código.
Além disso, há uma limitação na forma de uma unidade de compilação com a qual você pode trabalhar e para a qual pode escolher opções. Portanto, para C / C ++, esse ainda é um arquivo que pode conter muito código, o que talvez seja útil otimizar de maneiras diferentes, mas no momento isso não é possível. Portanto, um compilador “inteligente” que possa treinar e obter código otimizado para vários casos é um sonho para alguns desenvolvedores.
Pesquisa e soluções existentes
Naturalmente, o problema da seleção automatizada de opções de compilação é de interesse dos pesquisadores há muitos anos. Um dos projetos mais famosos é o desenvolvimento de G. Fursin e pesquisadores de sua equipe
MILEPOST GCC , que é uma versão do compilador gcc, capaz de selecionar passes de otimização com base em treinamento anterior na amostra de dados obtida. Neste trabalho, usamos um conjunto de 55 características para resolver o problema e um modelo bastante simples, baseado na idéia de distribuir boas soluções com base no algoritmo K dos vizinhos mais próximos. Foi esse desenvolvimento que mostrou que as passagens de otimização de ajuste podem levar a um código duas vezes mais rápido que o código obtido usando a opção de otimização máxima padrão -O3.
Existem também estudos de G. Pekhimenko e A.D. Marrom para o TPO da IBM (
Toronto Portable Optimizer ). Sua principal tarefa era selecionar valores heuristicamente selecionáveis para otimizações e o próprio conjunto de transformações de código. Para a implementação, foi utilizada a regressão logística, que possibilitou a definição de multas eficazes para um treinamento mais rápido. O classificador foi construído no Matlab. A probabilidade de uso foi calculada para cada passe e foi utilizada se fosse superior a 50%. Como resultado da característica que eles tentaram reduzir neste estudo, foi o tempo de compilação estática.
R. A Askhari participou da seleção direta de opções de compilação para todo o programa, a fim de minimizar o tempo de execução, o tempo de compilação, o tamanho do código e o consumo de energia. Para isso, foram utilizados o
Framework cTuning e o
Collective Mind Framework, desenvolvidos por G. Fursin e A. Lokhmotov (também desenvolvido no
GitHub ).
Também existem estudos de
M. Stephenson e S. Amarasinge sobre seleção de otimizações para certos algoritmos especialmente importantes (alocação de registros, PREFETCHING DE DADOS, FORMAÇÃO DE HIPERBLOCO). Para cada função, suas próprias características foram usadas de acordo. Para a solução, foi utilizado um algoritmo genético. O teste do produto desenvolvido foi realizado no Open Research Compiler (ORC).
Há também um projeto
MAGEEC (Compilador Eficiente em Energia Guiada por Máquina), cujos objetivos são um pouco diferentes. A infraestrutura desenvolvida usa o aprendizado de máquina para selecionar as otimizações necessárias para gerar o código com a máxima eficiência energética para sistemas de computação de alto desempenho. O MAGEEC foi projetado para funcionar com o gcc e o LLVM. Esse compilador faz parte do projeto maior TSERO (Total Software Energy Reporting and Optimization).
Uma pesquisa diretamente relacionada ao LLVM é o
LLVMTuner , um produto de software desenvolvido na Universidade de Illinois por I. Chen e W. Adwe. Em 2017, foi apresentado um relatório descrevendo os resultados disponíveis naquele momento. Neste trabalho, otimizamos os ciclos "quentes" individuais. Essa estrutura foi projetada para configuração automatizada de programas grandes. O LLVMTuner é executado no middleware LLVM IR, usa criação de perfil para identificar loops quentes e, em seguida, ajusta automaticamente a heurística para eles. O foco está nos ciclos de nível superior. Os ciclos selecionados e quaisquer funções de chamada são transferidos para um módulo separado, que é posteriormente submetido às otimizações necessárias. Esta solução permite obter um desempenho aprimorado em programas grandes.
Problemas existentes
No entanto, não existe um compilador amplamente utilizado que ajusta independentemente as heurísticas da otimização de passes. Qual é o problema? Como você sabe, a eficácia dos métodos de aprendizado de máquina e a qualidade dos modelos obtidos dependem da escolha correta dos recursos e da qualidade dos dados para o treinamento (apesar da existência de algoritmos menos sensíveis a dados "ruidosos"). Sem conhecer a estrutura e os algoritmos usados no compilador, não é fácil selecionar um conjunto completo e suficiente de características para o treinamento, embora existam bastante claras e lógicas, por exemplo, o tamanho do ciclo, o número de saídas do ciclo, etc. Portanto, é difícil desenvolver uma solução universal adequada para muitos compiladores de uma só vez e não é fato que geralmente seja possível. Além disso, é provável que isso não seja necessário.
Como o desenvolvimento de compiladores deve ser eficiente e viável em um tempo bastante curto, é natural que mesmo grandes empresas desenvolvam seus compiladores industriais com base em soluções prontas. As soluções mais modernas podem ser divididas em duas categorias: execução em máquinas virtuais, por exemplo, compiladores JVM - JIT e compiladores baseados no LLVM, um sistema que implementa uma máquina virtual com instruções do tipo RISC - compiladores estáticos e dinâmicos. Obviamente, ainda existem soluções próprias das empresas, mas elas estão se tornando menos competitivas devido à falta de uma grande comunidade envolvida no desenvolvimento das tecnologias usadas nelas. Como resultado, hoje muitas empresas grandes como Google, Apple, Adobe e ARM usam o LLVM para desenvolver suas próprias soluções. Obviamente, o gcc continua sendo o principal compilador para C / C ++, existem outras soluções para outros idiomas, mas de qualquer maneira, se, por exemplo, for encontrada uma solução para LLVM, isso já cobrirá uma parte decente dos compiladores atualmente existentes.
A coleção de características para treinamento também se torna um grande problema, uma vez que os compiladores de múltiplas passagens transformam fortemente a representação intermediária, e as características coletadas no estágio inicial não são muito relevantes para otimizações posteriores do compilador; essas características podem mudar com alta probabilidade. Além disso, faz sentido coletar separadamente para diferentes tipos de elementos: módulos, ciclos, blocos de base, já que as otimizações geralmente são projetadas para alterar um tipo específico de elemento, no LLVM, mesmo de acordo com esse critério, as passagens são divididas.
Mas, em primeiro lugar, surge a questão de identificar os elementos para os quais é necessário coletar características. Existem várias maneiras de calcular identificadores exclusivos que podem ser salvos durante todas as otimizações, por exemplo:
- Hash de front-end baseado em AST
- números exclusivos atribuídos na análise de front-end
- Número de 64 bits gerado com base em arcos no CFG (gráfico de fluxo de controle) usando uma soma de verificação (semelhante ao PGO (otimização guiada por perfil) no LLVM)
No entanto, é necessário salvar adequadamente esses identificadores durante as transformações, quando os elementos puderem se mesclar em um, dividir, criar novos e excluir os originais, o que não é uma tarefa fácil.
Em segundo lugar, é difícil, em princípio, avaliar os limites dos ciclos de origem, blocos de base etc. escritos no código-fonte, no IR já convertido. Por exemplo, devido à geração de código de máquina em vários estágios adotada pelo LLVM, as informações sobre as unidades base da máquina são perdidas após a geração do código com base nas instruções da máquina no AsmPrinter. E, consequentemente, as informações sobre os identificadores dos blocos de base e ciclos também são perdidas, para as quais, por exemplo, o deslocamento desde o início da função é medido, portanto, com este método, somente no estágio de geração do código da máquina o deslocamento pode ser obtido na forma do número de bytes. No entanto, nos estágios subseqüentes da geração de código de máquina ao trabalhar com fragmentos de máquina, vários alinhamentos podem ser adicionados a ele, o que altera o tamanho das instruções consideradas anteriormente, e também as instruções nop. Por esse motivo, para os blocos de base no final de grandes funções, o erro de cálculo pode ser muito grande, até uma mudança completa para outro bloco / ciclo. E embora algumas das transformações nos estágios posteriores possam ser rastreadas e levadas em consideração, isso não dará garantias para a precisão das medições, pois o tamanho das instruções pode variar até o vinculador.
Como você pode ver, mesmo a coleção de atributos com base nos quais o treinamento é necessário é bastante complicada e demorada, e que no futuro provavelmente se tornará o conjunto de informações para o modelo treinado para a tomada de decisões. E não há soluções óbvias para esses problemas, o que complica o trabalho imediato associado ao aprendizado de máquina e atrai um grande número de pessoas devido à falta de conjuntos de dados suficientes. Bem, as dificuldades típicas de encontrar soluções para problemas de aprendizado de máquina, escolher modelos, métodos, determinar o subconjunto correto de atributos com um grande número deles, etc. existe neste caso. Quase todo mundo que se deparou com o aprendizado de máquina sabe sobre eles e, talvez, algo único e específico para os compiladores não esteja aqui.
É difícil prever quando os compiladores inteligentes se espalharão. Os compiladores modernos também têm outros problemas que dificilmente serão resolvidos por esse método e que, no momento, provavelmente são mais prioritários. No entanto, os compiladores já se tornaram muito mais inteligentes do que eram no início de sua aparência, e esse processo continuará, embora possa ser um pouco mais lento do que a maioria dos desenvolvedores gostaria.