Анализ псевдонимов

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

Методы анализа псевдонимов обычно классифицируются по чувствительности к потоку и чувствительности к контексту. Они могут определять информацию о псевдониме или обязательном псевдониме. Термин анализ псевдонимов часто используется взаимозаменяемо с анализом точек , частным случаем.

Анализаторы псевдонимов предназначены для создания и вычисления полезной информации для понимания псевдонимов в программах.

Обзор

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

p.foo = 1 ; q.foo = 2 ; i = p.foo + 3 ;​​​​​​        

Здесь возможны три случая псевдонима:

1. Переменные p и q не могут быть псевдонимами (т.е. они никогда не указывают на одну и ту же область памяти).
2. Переменные p и q должны быть псевдонимами (т.е. они всегда указывают на одну и ту же область памяти).
3. Во время компиляции невозможно окончательно определить, являются ли p и q псевдонимами или нет.

Если p и q не могут быть псевдонимами, то i = p.foo + 3;можно изменить на i = 4. Если p и q должны быть псевдонимами, то i = p.foo + 3;можно изменить на , i = 5потому что p.foo + 3= q.foo + 3. В обоих случаях мы можем выполнить оптимизацию на основе знания псевдонима (предполагая, что никакой другой поток , обновляющий те же местоположения, не может чередоваться с текущим потоком или что модель памяти языка позволяет этим обновлениям не быть немедленно видимыми для текущего потока в отсутствие явных конструкций синхронизации ). С другой стороны, если неизвестно, являются ли p и q псевдонимами или нет, то никакая оптимизация не может быть выполнена, и для получения результата необходимо выполнить весь код. Говорят, что две ссылки на память имеют отношение «может-псевдоним», если их псевдоним неизвестен.

Выполнение анализа псевдонимов

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

Анализ псевдонимов на основе типа

Если компилируемый язык типобезопасен , проверка типов компилятора корректна, и язык не может создавать указатели, ссылающиеся на локальные переменные (например, ML , Haskell или Java ), то можно выполнить некоторые полезные оптимизации. ^[1] Существует много случаев, когда мы знаем, что два местоположения памяти должны находиться в разных классах псевдонимов:

1. Две переменные разных типов не могут находиться в одном классе псевдонимов, поскольку это свойство строго типизированных языков без ссылок на память (т. е. ссылки на области памяти не могут быть изменены напрямую), согласно которому две переменные разных типов не могут одновременно использовать одну и ту же область памяти.
2. Выделения, локальные для текущего стекового фрейма, не могут быть в том же классе псевдонимов, что и любое предыдущее выделение из другого стекового фрейма. Это так, потому что новые выделения памяти должны быть отделены от всех других выделений памяти.
3. Каждое поле записи каждого типа записи имеет свой собственный класс псевдонима, в общем, потому что дисциплина типизации обычно позволяет только записям одного типа создавать псевдонимы. Поскольку все записи типа будут храниться в памяти в идентичном формате, поле может создавать псевдонимы только для себя.
4. Аналогично, каждый массив данного типа имеет свой собственный класс-псевдоним.

При выполнении анализа псевдонимов для кода каждая загрузка и сохранение в памяти должны быть помечены ее классом. Тогда у нас есть полезное свойство, учитывая ячейки памяти и классы псевдонимов, что если then may-alias , и если then ячейки памяти не будут псевдонимами. ${\displaystyle A_{i}}$ ${\displaystyle B_{j}}$ ${\displaystyle i,j}$ ${\displaystyle i=j}$ ${\displaystyle A_{i}}$ ${\displaystyle B_{j}}$ ${\displaystyle i\neq j}$

Анализ псевдонимов на основе потока

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

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

• Анализ побега
• Анализ указателя
• Анализ формы

Ссылки

1. Диван, Амер; МакКинли, Кэтрин С.; Мосс, Дж. Элиот Б. (1998). "Анализ псевдонимов на основе типов". Труды конференции ACM SIGPLAN 1998 года по проектированию и реализации языков программирования - PLDI '98. Монреаль, Квебек, Канада: ACM Press. стр. 106–117. doi :10.1145/277650.277670. ISBN 978-0-89791-987-6. S2CID  5155574.

• Аппель, Эндрю В. (1998). Современная реализация компилятора в машинном обучении . Кембридж, Великобритания: Cambridge University Press. ISBN 0-521-60764-7.

Внешние ссылки

• Таксономия и применение анализа псевдонимов — магистерская диссертация, дающая введение в эту область.