Análise de fuga - Escape analysis

Na otimização do compilador , a análise de escape é um método para determinar o escopo dinâmico dos ponteiros  - onde no programa um ponteiro pode ser acessado. Está relacionado à análise de ponteiro e análise de forma .

Quando uma variável (ou um objeto) é alocado em uma sub - rotina , um ponteiro para a variável pode escapar para outras threads de execução ou para chamar sub-rotinas. Se uma implementação usa otimização de chamada final (geralmente necessária para linguagens funcionais ), os objetos também podem ser vistos como escapando para sub-rotinas chamadas . Se uma linguagem oferece suporte a continuações de primeira classe (como Scheme e Standard ML de New Jersey ), partes da pilha de chamadas também podem escapar.

Se uma sub-rotina aloca um objeto e retorna um ponteiro para ele, o objeto pode ser acessado de locais indeterminados no programa - o ponteiro "escapou". Os ponteiros também podem escapar se forem armazenados em variáveis ​​globais ou outras estruturas de dados que, por sua vez, escapam do procedimento atual.

A análise de escape determina todos os lugares onde um ponteiro pode ser armazenado e se o tempo de vida do ponteiro pode ser comprovado como restrito apenas ao procedimento e / ou thread atual.

Otimizações

Um compilador pode usar os resultados da análise de escape como base para otimizações:

• Convertendo alocações de heap em alocações de pilha . Se um objeto é alocado em uma sub-rotina e um ponteiro para o objeto nunca escapa, o objeto pode ser um candidato para alocação de pilha em vez de alocação de heap. Em linguagens com coleta de lixo, isso pode reduzir a frequência com que o coletor precisa ser executado.
• Elisão de sincronização . Se for descoberto que um objeto está acessível a partir de apenas um thread, as operações no objeto podem ser realizadas sem sincronização.
• Quebrando objetos ou substituição escalar . Um objeto pode ser acessado de maneiras que não requerem que o objeto exista como uma estrutura de memória sequencial. Isso pode permitir que partes (ou todos) do objeto sejam armazenados nos registros da CPU em vez de na memória.

Considerações práticas

Em linguagens de programação orientadas a objetos, compiladores dinâmicos são candidatos particularmente bons para realizar análises de escape. Na compilação estática tradicional , a substituição de método pode tornar a análise de escape impossível, pois qualquer método chamado pode ser substituído por uma versão que permite que um ponteiro escape. Os compiladores dinâmicos podem realizar análises de escape usando as informações disponíveis sobre sobrecarga e refazer a análise quando métodos relevantes são substituídos pelo carregamento de código dinâmico.

A popularidade da linguagem de programação Java tornou a análise de escape um alvo de interesse. Combinação de Java de alocação de objeto somente montão, built-in threading, a Sun HotSpot compilador dinâmico, e OpenJ9 é just-in-time compiler (JIT) cria uma plataforma candidato para otimizações de análise relacionados escape (ver análise Escape em Java ). A análise de escape é implementada no Java Standard Edition 6. Algumas JVMs suportam uma variante mais forte de análise de escape chamada análise de escape parcial, que torna possível a substituição escalar de um objeto alocado, mesmo se o objeto escapar em alguns caminhos de uma função.

Exemplo (Java)

class Main {
    public static void main(String[] args) {
        example();
    }
    public static void example() {
        Foo foo = new Foo(); //alloc
        Bar bar = new Bar(); //alloc
        bar.setFoo(foo);
    }
}

class Foo {}

class Bar {
    private Foo foo;
    public void setFoo(Foo foo) {
        this.foo = foo;
    }
}

Neste exemplo, dois objetos são criados (comentados com alloc), e um deles é fornecido como um argumento para um método de outro. O método setFoo()armazena uma referência a um objeto Foo recebido. Se o objeto Bar estivesse no heap, a referência a Foo escaparia. Mas, neste caso, um compilador pode determinar, com a análise de escape, que o próprio objeto Bar não escapa da invocação de example(). O que implica que uma referência a Foo também não pode escapar. Portanto, o compilador pode alocar com segurança os dois objetos na pilha.

Exemplos (esquema)

No exemplo a seguir, o vetor p não escapa para g , então ele pode ser alocado na pilha e então removido da pilha antes de chamar g .

(define (f x)
   (let ((p (make-vector 10000)))
      (fill-vector-with-good-stuff p)
      (g (vector-ref p 7023))))

Se, no entanto, tivéssemos

(define (f x)
   (let ((p (make-vector 10000)))
      (fill-vector-with-good-stuff p)
      (g p)))

então, p precisaria ser alocado na pilha ou (se g for conhecido pelo compilador quando f é compilado e se comportar bem) alocado na pilha de forma que possa permanecer no lugar quando g for chamado.

Se continuações forem usadas para implementar estruturas de controle semelhantes a exceções, a análise de escape pode frequentemente detectar isso para evitar ter que realmente alocar uma continuação e copiar a pilha de chamadas para ela. Por exemplo, em

;;Reads scheme objects entered by the user. If all of them are numbers,
;;returns a list containing all of them in order. If the user enters one that
;;is not a number, immediately returns #f.
(define (getnumlist)
  (call/cc (lambda (continuation)
    (define (get-numbers)
       (let ((next-object (read)))
          (cond
             ((eof-object? next-object) '())
             ((number? next-object) (cons next-object (get-numbers)))
             (else (continuation #f)))))
    (get-numbers))))

a análise de escape determinará que a continuação capturada por call / cc não escapa, então nenhuma estrutura de continuação precisa ser alocada, e invocar a continuação chamando continuation pode ser implementado desenrolando a pilha.

Veja também

• Análise de alias
• Análise de ponteiro
• Análise de forma

Referências