Анализ побега - Escape analysis

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

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

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

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

Оптимизация

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

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

Практические соображения

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

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

Пример (Java)

учебный класс Главный {  общественный статический пустота главный(Нить[] аргументы) {    пример();  }  общественный статический пустота пример() {    Фу фу = новый Фу(); // выделить    Бар бар = новый Бар(); // выделить    бар.setFoo(фу);  }}учебный класс Фу {}учебный класс Бар {  частный Фу фу;  общественный пустота setFoo(Фу фу) {    это.фу = фу;  }}

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

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

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

(определять (ж Икс)   (позволять ((п (make-vector 10000)))      (заполнить вектор хорошим материалом п)      (грамм (вектор-ссылка п 7023))))

Но если бы у нас было

(определять (ж Икс)   (позволять ((п (make-vector 10000)))      (заполнить вектор хорошим материалом п)      (грамм п)))

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

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

;; Читает объекты схемы, введенные пользователем. Если все они числа,;; возвращает список, содержащий их все по порядку. Если пользователь вводит тот, который;; не является числом, сразу возвращает #f.(определять (getnumlist)  (вызов / cc (лямбда (продолжение)    (определять (цифры)       (позволять ((следующий объект (читать)))          (cond             ((эоф-объект? следующий объект) '())             ((номер? следующий объект) (минусы следующий объект (цифры)))             (еще (продолжение #f)))))    (цифры))))

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

Смотрите также

Рекомендации

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