Пишем настоящий Pointer Analysis для LLVM. Часть 1: Введение или первое свидание с миром анализа программ

[eastig]

В качестве предложения.
Может имело бы смысл рассмотреть то, что уже имеется в LLVM: MemoryDependenceAnalysis Pass, MemorySSA, LoopAccessAnalysis Pass?

[safin_lenar]

Спасибо за предложение! Обзор существующих в LLVM/Clang пассов и сравнение реализаций обязательно будет.

[sborisov]

Спасибо.
Наконец, кто-то написал техническую статью про анализ программ (от которой не разит рекламой) и которую было интересно читать.
Достойно Хабра!!!

[nedved]

когда планируешь продолжить серию постов?

[safin_lenar]

Я полагаю в ближайшие две недели будет опубликована следующая статья цикла.

[panteleymonov]

>> complexComputationsOMG, а это значит, что вызов этой функции из представления программы можно смело убрать
А если вызов этой функции меняет параметры объекта влияющего на общий ход алгоритма (а вы его убрали) что тогда?
Функцию в принципе нельзя убрать если она изменяет хоть какую то ячейку памяти с «глобальным» доступом. А вот ветвление можно.

[safin_lenar]

Разумеется, вы правы. Об этом упоминается чуть дальше.

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

[panteleymonov]

Это надо сразу оговаривать, по крайней мере на 3 абзаца ниже я этого не заметил. Не очень удобно.

[safin_lenar]

Мое пояснение находится сразу за вашей цитатой, в круглых скобках.

[panteleymonov]

А, да точно спасибо.

[Saffron]

> Мы ничего не знаем про функцию offensiveFoo, поскольку она была импортирована из другого модуля трансляции, а потому вынуждены предположить, что p может указывать совершенно на что угодно!

А почему бы тогда не сливать все модули трансляции в один файл препроцессингом?

[safin_lenar]

Вы имеете в виду объединение модулей трансляции до этапа генерации промежуточного представления? Такая техника называется Single Compilation Unit, SCU и, судя по всему, сейчас почти нигде не применяется из-за плохой масштабируемости. Кроме того, используя SCU вы теряете возможность осуществлять параллельную/инкрементальную сборку программы.

Даже если вы используете объединение модулей, у вас все равно могут остаться неразрешенные внешние символы (то есть функции и глобальные переменные), например, если компилируемая программа использует библиотеки с закрытым исходным кодом.

Но вы правы в главном: объединение модулей для анализа всей программы целиком используется для осуществления оптимизаций на этапе линковки (Link Time Optimization, LTO). Обычный подход предполагает трансляцию каждого модуля компиляции во внутреннее представление (например, .class файлы для Java, .bc файлы для Clang и других LLVM-based компиляторов) и объединение таких модулей байткода в один большой модуль. После оптимизации такого большого модуля генерируется код для целевой платформы. Ничего умнее пока, насколько мне известно, придумано не было (за исключением может быть ThinLTO).

[Saffron]

> судя по всему, сейчас почти нигде не применяется из-за плохой масштабируемости.

sqlite распространяется одним большим файлом.

[VaalKIA]

Я не понял пример:

x = 1;
*p = 3;
if (x < 3) {
killTheCat();
}

Возможно, имелось ввиду x<*p? Иначе при чём здесь вообще указатель о котором столько написано?
Хотя я не отрицаю, что где-то можно было сделать p := addr(x) и тогда p^:=3 может изменять x, но это уже несколько другое и контролироваться получение адреса какой-то «не ссылочной» переменной не так уж и сложно для компилятора.

[DFooz]

в дополнение,
почему должны удалить условный переход? ведь в куче по адресу p может быть что угодно

Если, например, перед указанным фрагментом кода переменная p инициализировалась как p = new int, тогда мы должны удалить из оптимизированной программы условный переход и вызвать метод killTheCat безусловно

[Maccimo]

Потому, что в этом случае *p = 3; не может изменить значение x и выражение (x < 3) вырождается в (true).

[DantaliaN00]

Думаю, потому что получается

if (1 < 3) {killTheCat();}

соответственно, условие всегда true.

Да и по вопросу выше. p может ссылаться на x, а может и не ссылаться на него. Мы этого не узнаем до тех пор, пока не определим куда все же ведет указатель. Только после этого можно будет однозначно сказать будет ли x = 1 или же x = 3