Анализ выхода

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

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

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

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

• 1 Оптимизация
• 2 Практические соображения
• 3 Пример (Java)
• 4 Примеры (Схема)
• 5 См. Также
• 6 Ссылки

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

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

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

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

class Main {public static void main (String args) {example (); } public static void example () {Foo foo = new Foo (); // выделяем Bar bar = new Bar (); // выделить bar.setFoo (foo); }} class Foo {} class Bar {private Foo foo; public void setFoo (Foo foo) {this.foo = foo; }}

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

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

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

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

(define (fx) (let ((p (make-vector 10000))) (fill-vector-with-good-stuff p) (gp)))

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

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

;; Читает объекты схемы, введенные пользователем. Если все они числа, ;; возвращает список, содержащий их все по порядку. Если пользователь вводит число, которое ;; не является числом, немедленно возвращается #f. (define (getnumlist) (call / cc (lambda (продолжение) (define (get-numbers) (let ((next-object (read))) (cond ((eof-object? next-object) '()) ( (number? next-object) (cons next-object (get-numbers))) (else (continue #f))))) (get-numbers))))

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

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

1. ^ T. Коцманн и Х. Мессенбек, «Escape-анализ в контексте динамической компиляции и деоптимизации», в материалах 1-й международной конференции ACM / USENIX по виртуальным средам исполнения, Нью-Йорк, Нью-Йорк, США, 2005, стр. 111–120.
2. ^Бланше, Бруно (ноябрь 2003 г.). «Анализ побега для JavaTM: теория и практика». Транзакции ACM по языкам и системам программирования. 25 (6): 713–775. doi : 10.1145 / 945885.945886. ISSN 0164-0925.
3. ^Коцманн, Томас; Mössenböck, Hanspeter (март 2007 г.). Поддержка во время выполнения оптимизаций на основе анализа побега. Международный симпозиум по генерации кода и оптимизации (CGO'07). С. 49–60. CiteSeerX 10.1.1.394.5944. doi : 10.1109 / CGO.2007.34. ISBN 978-0-7695-2764-2.
4. ^Стадлер, Лукас; Вюртингер, Томас; Mössenböck, Hanspeter (2014). «Анализ частичного выхода и скалярная замена для Java». Материалы ежегодного международного симпозиума IEEE / ACM по созданию и оптимизации кода - CGO '14. С. 165–174. doi : 10.1145 / 2581122.2544157. ISBN 9781450326704.