Введение
Анализ псевдонимов — это техника в теории компиляторов, используемая для определения, может ли к одному и тому же месту в памяти быть осуществлён доступ несколькими способами. Два указателя называются псевдонимами, если они указывают на одно и то же местоположение. Методы анализа псевдонимов обычно классифицируются по чувствительности к потоку управления и чувствительности к контексту. Они могут определять информацию о возможном или обязательном наличии псевдонимов. Термин «анализ псевдонимов» часто используется как синоним «анализа указателей», являющегося частным случаем. Анализаторы псевдонимов предназначены для получения и вычисления полезной информации, необходимой для понимания псевдонимов в программах.
Выполнение анализа псевдонимов
В анализе псевдонимов мы делим память программы на классы псевдонимов. Классы псевдонимов – это непересекающиеся множества ячеек памяти, которые не могут быть псевдонимами друг другу. Для целей данного обсуждения предполагается, что рассматриваемые оптимизации выполняются на низкоуровневом промежуточном представлении программы. Это означает, что программа была скомпилирована в двоичные операции, переходы, перемещения между регистрами, перемещения из регистров в память, перемещения из памяти в регистры, ветвления и вызовы/возвраты функций.
Анализ псевдонимов на основе типа
Если язык, который компилируется, является типобезопасным, проверка типов компилятором корректна, и в языке отсутствует возможность создания указателей, ссылающихся на локальные переменные (например, ML, Haskell или Java), то можно выполнить некоторые полезные оптимизации. Существует множество случаев, когда мы знаем, что два участка памяти должны относиться к разным классам псевдонимов: две переменные разных типов не могут находиться в одном и том же классе псевдонимов, поскольку это свойство строго типизированных языков, не допускающих прямых ссылок на память (то есть ссылки на участки памяти нельзя изменять напрямую). Локальные выделения памяти текущего стекового фрейма не могут находиться в одном классе псевдонимов с любыми предыдущими выделениями из другого стекового фрейма. Это связано с тем, что новые выделения памяти должны быть непересекающимися со всеми остальными выделениями памяти. Каждое поле записи каждого типа записи, как правило, имеет свой собственный класс псевдонимов, поскольку дисциплина типизации обычно разрешает псевдонимы только для записей одного и того же типа. Поскольку все записи данного типа будут храниться в памяти в идентичном формате, поле может иметь псевдоним только для самого себя. Аналогично, каждый массив заданного типа имеет свой собственный класс псевдонимов. При выполнении анализа псевдонимов кода каждая операция загрузки и сохранения в память должна быть помечена своим классом. В этом случае мы получаем полезное свойство: если , то может быть псевдонимом , а если , то эти участки памяти не будут псевдонимами.
Two variables of different types cannot be in the same alias class since it is a property of strongly typed, memory reference free (i. e., references to memory locations cannot be changed directly) languages that two variables of different types cannot share the same memory location simultaneously. Allocations local to the current stack frame cannot be in the same alias class as any previous allocation from another stack frame. This is the case because new memory allocations must be disjoint from all other memory allocations. Each record field of each record type has its own alias class, in general, because the typing discipline usually only allows for records of the same type to alias. Since all records of a type will be stored in an identical format in memory, a field can only alias to itself. Similarly, each array of a given type has its own alias class. When performing alias analysis for code, every load and store to memory needs to be labeled with its class. We then have the useful property, given memory locations and with alias classes, that if then may alias , and if then the memory locations will not alias.
Анализ псевдонимов на основе потоков
Анализ, основанный на потоке данных, может применяться к программам на языках со ссылками или приведением типов. Анализ на основе потока данных может использоваться вместо анализа на основе типов или в дополнение к нему. В анализе на основе потока данных создаются новые классы псевдонимов для каждого выделения памяти, а также для каждой глобальной и локальной переменной, адрес которой был использован. Ссылки могут указывать на несколько значений в разное время и, следовательно, могут принадлежать к нескольким классам псевдонимов. Это означает, что каждое место в памяти имеет набор классов псевдонимов, а не один единственный класс псевдонимов.