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

В оптимизации компилятора 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)

класс   Main   { 
     public   static   void   main  (  String  []   args  )   { 
         example  (); 
      } 
     public   static   void   Пример  ()   { 
         Foo   foo   =   new   Foo  ();    //выделить 
         бар   bar   =   новый   бар  ();    // 
         панель  выделения .   установитьFoo  (  фу  ); 
      } 
 } 

 Класс   Foo   {} 

 класс   Bar   { 
     частное   Foo   foo  ; 
      общественный   недействительный   setFoo  (  Foo   foo  )   { 
         this  .   Фу   =   Фу  ; 
      } 
 } 

В этом примере создаются два объекта (комментируются с помощью 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   (  вектор-ref   p   7023  )))) 

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

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

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

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

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

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

См. также

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