Анализ побега

В оптимизации компилятора escape -анализ — это метод определения динамической области действия указателей — где в программе можно получить доступ к указателю. Это связано с анализом указателей и анализом формы .

Когда переменная (или объект) выделяется в подпрограмме , указатель на переменную может перейти в другие потоки выполнения или на вызов подпрограмм. Если реализация использует оптимизацию хвостового вызова (обычно требуется для функциональных языков ), объекты также могут рассматриваться как переходящие в вызываемые подпрограммы. Если язык поддерживает первоклассные продолжения (как это делают Scheme и Standard ML в Нью-Джерси ), части стека вызовов также могут ускользнуть.

Если подпрограмма выделяет объект и возвращает на него указатель, доступ к объекту можно получить из неопределенных мест программы – указатель «ускользнул». Указатели также могут экранироваться, если они хранятся в глобальных переменных или других структурах данных, которые, в свою очередь, экранируют текущую процедуру.

Escape-анализ определяет все места, где может храниться указатель, и можно ли доказать, что время жизни указателя ограничено только текущей процедурой и/или потоком.

Оптимизации

Компилятор может использовать результаты escape-анализа как основу для оптимизации:

• Преобразование распределения кучи в распределение стека . Если объект выделяется в подпрограмме и указатель на объект никогда не ускользает, объект может быть кандидатом на размещение в стеке, а не в куче. В языках со сборкой мусора это может сократить частоту запуска сборщика.
• Устранение синхронизации . Если обнаруживается, что объект доступен только из одного потока, операции над объектом можно выполнять без синхронизации.
• Разрушение объектов или скалярная замена . Доступ к объекту может осуществляться способами, не требующими существования объекта как последовательной структуры памяти. Это может позволить хранить части (или весь) объекта в регистрах ЦП, а не в памяти.

соображения

В объектно-ориентированных языках программирования динамические компиляторы являются особенно хорошими кандидатами для выполнения escape-анализа. В традиционной статической компиляции переопределение метода может сделать невозможным escape-анализ, поскольку любой вызванный метод может быть переопределен версией, которая позволяет экранировать указатель. Динамические компиляторы могут выполнять escape-анализ, используя доступную информацию о перегрузке, и повторять анализ, когда соответствующие методы переопределяются динамической загрузкой кода.

Популярность языка программирования Java сделала escape-анализ объектом интереса. Комбинация Java-распределения объектов только в куче, встроенной многопоточности, динамического компилятора Sun HotSpot и OpenJ9 JIT- компилятора создает платформу-кандидат для оптимизации, связанной с escape-анализом (см. Escape-анализ в Java ). Escape-анализ реализован в Java Standard Edition 6. Некоторые JVM поддерживают более сильный вариант escape-анализа, называемый частичным escape-анализом , который делает возможной скалярную замену выделенного объекта, даже если объект ускользает в некоторых путях функции.

Пример (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;
    }
}

В этом примере создаются два объекта (комментируются с помощью alloc), и один из них передается в качестве аргумента методу другого. Метод setFoo() хранит ссылку на полученный объект Foo. Если бы объект Bar находился в куче, ссылка на Foo ускользнула бы. Но в этом случае компилятор может определить с помощью escape-анализа, что сам объект Bar не избегает вызова example(). В результате ссылка на Foo также не может выйти из строя, и компилятор может безопасно разместить оба объекта в стеке.

Примеры (Схема)

В следующем примере вектор p не переходит в g , поэтому его можно выделить в стеке, а затем удалить из стека перед вызовом g .

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

Если бы, однако, мы имели

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

тогда либо p нужно будет разместить в куче, либо (если g известен компилятору при компиляции f и ведет себя хорошо) разместить в стеке таким образом, чтобы он мог оставаться на месте при g вызове .

Если продолжения используются для реализации структур управления, подобных исключениям, escape-анализ часто может обнаружить это, чтобы избежать необходимости фактического выделения продолжения и копирования в него стека вызовов. Например, в

;;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))))

escape-анализ определит, что продолжение, захваченное вызовом /cc, не экранируется, поэтому не требуется выделять структуру продолжения, а вызов продолжения путем вызова продолжения можно реализовать путем разматывания стека.

См. также

• Анализ псевдонимов
• Анализ указателя
• Анализ формы