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

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

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

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

Обзор

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

п.фу = 1;q.фу = 2;я = п.фу + 3;

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

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

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

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

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

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

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

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

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

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

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

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

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

использованная литература

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

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

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

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