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

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

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

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

Содержание

• 1 Обзор
• 2 Выполнение анализа псевдонимов
  • 2.1 Анализ псевдонимов на основе типов
  • 2.2 Анализ псевдонимов на основе потоков
• 3 См. Также
• 4 Ссылки
• 5 Внешние ссылки

Обзор

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

p.foo = 1; q.foo = 2; я = 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. Две переменные разных типов не могут быть в одном классе псевдонимов, поскольку это свойство строго типизированной, свободной от ссылок на память (т. Е. Ссылок в ячейки памяти не могут быть изменены напрямую) языки, в которых две переменные разных типов не могут использовать одну и ту же ячейку памяти одновременно.
2. Выделения, локальные для текущего кадра стека, не могут быть в том же классе псевдонимов, что и любое предыдущее выделение из другого стека Рамка. Это так, потому что новые распределения памяти должны быть отделены от всех других распределений памяти.
3. Каждое поле записи каждого типа записи имеет свой собственный класс псевдонима, как правило, потому что дисциплина типизации обычно допускает только записи того же типа для псевдонима. Поскольку все записи типа будут храниться в памяти в идентичном формате, поле может быть псевдонимом только самому себе.
4. Точно так же каждый массив данного типа имеет свой собственный класс псевдонима.

При выполнении псевдонима При анализе кода каждая загрузка и сохранение в памяти должны быть помечены своим классом. Затем у нас есть полезное свойство, учитывая ячейки памяти $A\; i\; \{\backslash \; displaystyle\; A\_\; \{i\}\}$и $B\; j\; \{\backslash \; displaystyle\; B\_\; \{j\}\}$с $i,\; j\; \{\backslash \; displaystyle\; i,\; j\}$классы псевдонимов, если $i\; =\; j\; \{\backslash \; displaystyle\; i\; =\; j\}$, то $A\; i\; \{\; \backslash \; displaystyle\; A\_\; \{i\}\}$may-alias $B\; j\; \{\backslash \; displaystyle\; B\_\; \{j\}\}$, а если $i\; \ne \; j\; \{\backslash \; displaystyle\; i\; \backslash \; neq\; j\}$тогда ячейки памяти не будут псевдонимами.

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

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

См. Также

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

Ссылки

• Эндрю В. Аппель (1998). Реализация современного компилятора в ML. Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-60764-7.

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

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