Análise de alias - Alias analysis

A análise de alias é uma técnica na teoria do compilador , usada para determinar se um local de armazenamento pode ser acessado de mais de uma maneira. Diz- se que dois ponteiros têm um alias se eles apontam para o mesmo local.

As técnicas de análise de alias são geralmente classificadas por sensibilidade ao fluxo e sensibilidade ao contexto. Eles podem determinar informações de may-alias ou must-alias. O termo análise de alias é freqüentemente usado de forma intercambiável com análise de pontos para , um caso específico.

Os analisadores de alias pretendem criar e calcular informações úteis para entender o aliasing em programas.

Visão geral

Em geral, a análise de alias determina se referências de memória separadas apontam ou não para a mesma área da memória. Isso permite que o compilador determine quais variáveis ​​no programa serão afetadas por uma instrução. Por exemplo, considere a seguinte seção de código que acessa membros de estruturas: 

p.foo = 1;
q.foo = 2;
i = p.foo + 3;

Existem três casos de alias possíveis aqui:

  1. As variáveis ​​peq não podem ser alteradas (isto é, elas nunca apontam para o mesmo local de memória).
  2. As variáveis ​​p e q devem ser apelidadas (ou seja, elas sempre apontam para o mesmo local de memória).
  3. Não pode ser determinado conclusivamente em tempo de compilação se p e q alias ou não.

Se p e q não puderem ser alias, então i = p.foo + 3; pode ser alterado para i = 4 . Se p e q devem ser alias, então i = p.foo + 3; pode ser alterado para i = 5 porque p.foo + 3 = q.foo + 3 . Em ambos os casos, somos capazes de realizar otimizações a partir do conhecimento do alias (assumindo que nenhum outro encadeamento atualizando os mesmos locais pode intercalar com o encadeamento atual, ou que o modelo de memória de linguagem permite que essas atualizações não sejam imediatamente visíveis para o encadeamento atual em ausência de construções de sincronização explícitas ). Por outro lado, se não se sabe se p e q alias ou não, nenhuma otimização pode ser realizada e todo o código deve ser executado para obter o resultado. Diz-se que duas referências de memória têm uma relação may-alias se seu aliasing for desconhecido.

Executando análise de alias

Na análise de alias, dividimos a memória do programa em classes de alias . As classes de alias são conjuntos separados de locais que não podem ser substituídos entre si. Para a discussão aqui, assume-se que as otimizações feitas aqui ocorrem em uma representação intermediária de baixo nível do programa. Isso quer dizer que o programa foi compilado em operações binárias, salta, move-se entre registradores, move-se dos registradores para a memória, move-se da memória para os registradores, ramificações e chamadas / retornos de função.

Análise de alias baseada em tipo

Se a linguagem que está sendo compilada é segura para o tipo , o verificador de tipo do compilador está correto e a linguagem não tem a capacidade de criar ponteiros referenciando variáveis ​​locais (como ML , Haskell ou Java ), então algumas otimizações úteis podem ser feitas. Existem muitos casos em que sabemos que dois locais de memória devem estar em classes de alias diferentes:

  1. Duas variáveis ​​de tipos diferentes não podem estar na mesma classe de alias, pois é uma propriedade de linguagens fortemente tipadas e sem referência de memória (ou seja, as referências a locais de memória não podem ser alteradas diretamente) em que duas variáveis ​​de tipos diferentes não podem compartilhar o mesmo local de memória simultaneamente.
  2. As alocações locais para o quadro de pilha atual não podem estar na mesma classe de alias de qualquer alocação anterior de outro quadro de pilha. Este é o caso porque as novas alocações de memória devem ser separadas de todas as outras alocações de memória.
  3. Cada campo de registro de cada tipo de registro possui sua própria classe de alias, em geral, pois a disciplina de digitação geralmente permite apenas registros do mesmo tipo para alias. Uma vez que todos os registros de um tipo serão armazenados em um formato idêntico na memória, um campo só pode ser apelido para si mesmo.
  4. Da mesma forma, cada array de um determinado tipo tem sua própria classe de alias.

Ao realizar a análise de alias para código, cada carregamento e armazenamento na memória precisa ser rotulado com sua classe. Temos então a propriedade útil, dadas as localizações de memória e com classes de alias, que se então pode-alias , e se então as localizações de memória não terão alias.

Análise de alias baseada em fluxo

Análise baseada em fluxo, pode ser aplicada a programas em uma linguagem com referências ou modelagem. A análise baseada em fluxo pode ser usada no lugar de ou para complementar a análise baseada em tipo. Na análise baseada em fluxo, novas classes de alias são criadas para cada alocação de memória e para cada variável global e local cujo endereço foi usado. As referências podem apontar para mais de um valor ao longo do tempo e, portanto, podem estar em mais de uma classe de alias. Isso significa que cada local de memória possui um conjunto de classes de alias em vez de uma única classe de alias.

Veja também

Referências

  • Appel, Andrew W. (1998). Implementação de compiladores modernos em ML . Cambridge, Reino Unido: Cambridge University Press. ISBN   0-521-60764-7 .

links externos