Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

Оптимизация [ править ]

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

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

Практические соображения [ править ]

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

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

Пример (Java) [ править ]

класс  Main  {  public  static  void  main ( String []  args )  {  example ();  }  public  static  void  example ()  {  Foo  foo  =  new  Foo ();  // выделяем  Bar  bar  =  new  Bar ();  //  панель выделения . setFoo ( foo );  } }class  Foo  {}class  Bar  {  private  Foo  foo ;  public  void  setFoo ( Foo  foo )  {  это . foo  =  foo ;  } }

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ a b Т. Коцманн и Х. Мёссенбёк, «Escape-анализ в контексте динамической компиляции и деоптимизации», в материалах 1-й международной конференции ACM / USENIX по виртуальным средам исполнения, Нью-Йорк, Нью-Йорк, США, 2005 г., стр. 111–120.
  2. Перейти ↑ Blanchet, Bruno (ноябрь 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.