Хабрахабр

Как я попробовал сделать статический анализатор GLSL (и что пошло не так)

Однажды я готовился к Ludum Dare и сделал простую игру, где использовал пиксельные шейдеры (других в движок Phaser не завезли).

Что такое шейдеры?

Есть два вида шейдеров, в этой статье речь идет про пиксельные (они же “фрагментные”, fragment shaders), которые очень грубо можно представить в таком виде: Шейдеры — это программы на си-подобном языке GLSL, которые выполняются на видеокарте.

color = pixelShader(x, y, ...other attributes)

шейдер выполняется для каждого пикселя выводимого изображения, определяя или уточняя его цвет.
Вводную можно почитать на другой статье на хабре — https://habr.com/post/333002/ Т.е.

Потестировав, кинул ссылку другу, и получил от него вот такой скриншот с вопросом "а это нормально?"

Посмотрев внимательно код шейдера, я обнаружил ошибку в вычислениях: Нет, это было ненормально.

if (t < M) { realColor = mix(color1,color2, pow(1. - t / R1, 0.5));
}

константа R1 была меньше чем M, то в некоторых случаях в первом аргументе pow получалось число меньше нуля. Т.к. Мою видеокарту ничего не смутило, и она как-то выпуталась из этого положения (похоже, вернув из pow 0), а вот у друга она оказалась более разборчивой. Квадратный корень из отрицательного числа — штука загадочная, по крайней мере для стандарта GLSL.

От ошибок никто не застрахован, особенно таких, которые не воспроизводятся локально. И тут я задумался: а могу ли я избежать таких проблем в будущем? В то же время преобразования внутри шейдера довольно простые — умножения, деления, синусы, косинусы… Неужели нельзя отследить значения каждой переменной и убедиться, что ни при каких условиях не происходит выхода за допустимые границы значений? Юнит-тесты на GLSL не напишешь.

Что из этого получилось — можно прочитать под катом. Так я решил попробовать сделать статический анализ для GLSL.

Сразу предупрежу: какого-то законченного продукта получить не удалось, только учебный прототип.

Предварительный анализ

Посудите сами: Немного проштудировав существующие статьи на эту тему (и попутно выяснив, что тема называется Value Range Analysis), я порадовался тому, что у меня именно GLSL, а не какой-то другой язык.

  • никакой "динамики" — ссылок на функции, интерфейсов, автоматически выводимых типов и прочего
  • никакой прямой работы с памятью
  • никаких модулей, линковки, позднего связывания — исходный код шейдера доступен целиком
    для входящих значений как правило хорошо известны диапазоны
  • немного типов данных, да и те крутятся вокруг float. int/bool используются крайне редко, и за ними не так важно следить
  • if-ы и циклы используются достаточно редко (из-за проблем с производительностью). циклы если и используются, то чаще простые счетчики для прохода по массиву или повторению некоего эффекта несколько раз. Вот такого ужаса никто в GLSL писать не будет (надеюсь).

//взято из статьи - https://homepages.dcc.ufmg.br/~fernando/classes/dcc888/ementa/slides/RangeAnalysis.pdf
k = 0 while k < 100: i = 0 j = k while i < j: i = i + 1 j = j – 1 k = k + 1

Основной алгоритм сводится к следующему: В общем, с учетом ограничений GLSL задача выглядит решаемой.

  1. разобрать код шейдера и выстроить последовательность команд, меняющих значения каких-либо переменных
  2. зная начальные диапазоны для переменных, пройти по последовательности, обновляя диапазоны при их изменении
  3. если диапазон нарушает какие-то заданные границы (например, в pow может прийти отрицательное число, или в "выходной цвет" gl_FragColor в красный компонент придет что-то больше 1.), надо показать предупреждение

Используемые технологии

С одной стороны мой основной скоуп — это проверка WebGL-ных шейдеров, поэтому почему бы и не javascript — чтобы запускать все в браузере при разработке. Здесь у меня был долгий и мучительный выбор. Там тоже будут шейдеры, а вот javascript-а уже не будет. С другой стороны, я давно планирую слезть с Phaser-а и попробовать другой движок типа Unity или LibGDX.

А лучшее на свете развлечение — это зоопарк. А с третьей стороны задача делалась в первую очередь для развлечения. Поэтому:

  1. разбор GLSL-кода сделан на javascript. Просто я довольно быстро нашел библиотеку для парсинга GLSL в AST именно на нем, да и тестовый UI вроде как привычнее делать вебовским. AST превращается в последовательность команд, которая отправляется во...
  2. … вторую часть, которая написана на C++ и компилируется в WebAssembly. Я решил так: если вдруг захочу прикрутить этот свой анализатор к какому-то еще движку, с библиотекой на C++ это должно быть сделать проще всего.

Пару слов об инструментарии

  • в качестве основной IDE я взял Visual Studio Code и в целом ей доволен. Мне надо-то немного для счастья — главное, чтобы Ctrl+Click работал и autocomplete при наборе. Обе функции прекрасно работают и в C++ и в JS части. Ну и возможность не переключать разные IDE между собой — это тоже прекрасно.
  • для компиляции C++ в WebAssembly используется инструмент cheerp (он платный, но бесплатен для open-source проектов). Я не встретил никаких проблем при его использовании, разве что оптимизировал код он довольно странно, но тут я не уверен чья это вина — самого cheerp или используемого им компилятора clang.
  • для юнит-тестов в C++ взял старый добрый gtest
  • для сборки js в bundle взял некий microbundle. Он удовлетворил моим требованиям "хочу 1 npm-пакет и пару флагов командной строки", но при этом не без проблем, увы. Скажем, watch падает при любой ошибке при парсинге входящего javascript с сообщением [Object object], что не очень помогает.

Все, теперь можно ехать.

Коротко о модели

Анализатор держит в памяти список переменных, которые встречаются в шейдере, и для каждого хранит текущий возможный диапазон значений (типа [0,1] или [1,∞) ).

Анализатор принимает на вход поток операций типа такой:

cmdId: 10
opCode: sin
arguments: [1,2,-,-,3,4,-,-]

Этот вызов соответствует GLSL-ному: Тут у нас вызывается функция sin, на вход ей подаются переменные с id = 3 и 4, а результат записывается в переменные 1 и 2.

vec2 a = sin(b);

В GLSL почти все встроенные функции перегружены для разных наборов входных типов, т.е. Обратите внимание на пустые аргументы (помечены как "-"). Для удобства я привожу все перегруженные версии к одному виду — в данном случае sin(vec4). существуют sin(float), sin(vec2), sin(vec3), sin(vec4).

На выход анализатор выдает список изменений для каждой переменной, вроде

cmdId: 10
branchId: 1
variable: 2
range: [-1,1]

Теперь можно красиво подсвечивать диапазоны значений в исходном коде. Что означает "переменная 2 в строке 10 в ветке 1 имеет диапазон от -1 до 1 включительно" (что такое ветка (branch) мы поговорим чуть позже).

Хорошее начало

Их довольно много (и еще у них до кучи перегрузок, как я писал выше), но в целом у них предсказуемые преобразования диапазонов. Когда AST-дерево уже начало худо-бедно превращаться в список команд, настала пора реализовывать стандартные функции и методы. Скажем, вот для такого примера все довольно очевидно получается:

uniform float angle; // -> (-∞,∞)
//...
float y = sin(angle); // -> [-1,1]
float ynorm = 1 + y; // -> [0,2]
gl_FragColor.r = ynorm / 2.; // -> [0,1]

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

Но что насчет второй половины — с условиями, циклами и функциями? Если покрыть побольше встроенных функций, то для половины шейдеров и такого анализа хватит.

Ветвления

Возьмем для примера такой шейдер.

uniform sampler2D uSampler;
uniform vec2 uv; // [0,1] void main() else { k = 1. - a; } gl_FragColor = vec4(1.) * k;
}

А вот какие значения может принимать k? Переменная a у нас берется из текстуры, и поэтому значение этой переменной лежит от 0 до 1.

Для ветки if получаем k = [0,2], а для ветки else k = [0,1]. Можно пойти по простому пути и "обьединить ветки" — посчитать диапазон в каждом из случаев и выдать общее. в выходной цвет gl_FragColor попадают значения больше 1. Если объединить, получается [0,2], и надо выдавать ошибку, т.к.

Однако это явный false alarm, а для статического анализатора нет ничего хуже ложных срабатываний — если его не отключат после первого крика "волки", то после десятого точно.

Вот как это может выглядеть: Значит, нам нужно обрабатывать обе ветки порознь, причем в обеих ветках мы должны уточнить диапазон переменной a (хотя формально его никто не менял).

Ветка 1:

if (a < 0.5) { //a = [0, 0.5) k = a * 2.; //k = [0, 1) gl_FragColor = vec4(1.) * k;
}

Ветка 2:

if (a >= 0.5) { //a = [0.5, 1] k = 1. - a; //k = [0, 0.5] gl_FragColor = vec4(1.) * k;
}

В каждом случае он уточняет диапазон исходной переменной и движется дальше по списку команд. Таким образом, когда анализатор встречает некое условие, которое по-разному себя вести в зависимости от диапазона, то он создает ветки (branches — бранчи) для каждого из случаев.

Ветки создаются при разбиении диапазона какой-то переменной на под-диапазоны, и причиной может стать необязательно условный оператор. Стоит уточнить, что ветки в данном случае не связаны с конструкцией if-else. Следующий GLSL-шейдер делает то же самое, что предыдущий, только не использует ветвление (что, кстати, лучше в плане производительности). Например, функция step тоже создает ветки.

float a = texture2D(uSampler, uv).a;
float k = mix(a * 2., 1. - a, step(0.5, a));
gl_FragColor = vec4(1.) * k;

5 и 1 в противном случае. Функция step должна вернуть 0 если a < 0. Поэтому здесь тоже будут созданы ветки — аналогичные предыдущему примеру.

Уточнение других переменных

Рассмотрим чуть видоизмененный предыдущий пример:

float a = texture2D(uSampler, uv).a; // -> [0,1]
float b = a - 0.5; // -> [-0.5, 0.5]
if (b < 0.) { k = a * 2.; // k,a -> ?
} else { k = 1. - a;
}

То есть внутри каждой ветки будет корректное значение диапазона b, но совершенно ненужное, и оригинальное значение диапазона a, совершенно некорректное. Здесь нюанс в следующем: ветвление происходит по переменной b, а вычисления происходят с переменной a.

Если запомнить эту информацию, то при ветвлении анализатор может пройтись по всем исходным переменным и уточнить их диапазон, выполнив обратное вычисление. Однако анализатор видел, что диапазон b был получен вычислением из a.

Функции и циклы

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

формально GLSL полностью поддерживает си-подобный цикл for. С циклами все посложнее, т.к. Однако чаще всего циклы используются в простейшем варианте, вот таком:

for (int i = 0; i < 12; i++) {}

вставить тело цикла 12 раз друг за другом. Такие циклы несложно "развернуть", т.е. В итоге, подумав, я решил пока что поддержать только такой вариант.

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

Всплывшие проблемы

Проблема #1: сложность или невозможность уточнения

И эта задача решаема, когда участвуют операции типа сложения/вычитания. Выше мы рассматривали случаи, когда при уточнения значения по одной переменной мы делали выводы о значениях другой переменной. Например такое условие: Но, скажем, как быть с тригонометрией?

float a = getSomeValue();
if (sin(a) > 0.) { //Чему тут считать равным a?
}

Получается бесконечный набор диапазонов с шагом пи, с которым потом работать будет очень неудобно. Как посчитать диапазон a внутри if?

А еще может быть такая ситуация:

float a = getSomeValue(); // [-10,10]
float b = getAnotherValue(); //[-20, 30]
float k = a + b;
if (k > 0) { //a? b?
}

А, значит, возможны ложные срабатывания. Уточнить диапазоны a и b в общем случае будет нереально.

Проблема #2: Зависимые диапазоны

Рассмотрим такой пример:

uniform float value //-> [0,1]; void main() { float val2 = value - 1.; gl_FragColor = vec4(value - val2);
}

Для начала анализатор считает диапазон переменной val2 — и он ожидаемо оказывается [0,1] - 1 == [-1, 0]

Получает [0,1] - [-1,0] = [0,2], и рапортует об ошибке. Однако затем, считая value - val2, анализатор не учитывает, что val2 был получен из value, и работает с диапазонами так, будто бы они независимы друг от друга. Хотя в реальности он должен был получить константу 1.

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

Проблема #3: Диапазоны, зависимые неявно

Вот пример:

float k = sin(a) + cos(a);

Что неверно, т.к. Здесь анализатор предположит, что диапазон k = [-1,1] + [-1,1] = [-2,2]. sin(a) + cos(a) для любых a лежит в диапазоне [-√2, √2].

Однако они зависят от одного и того же диапазона a. Результат вычисления sin(a) формально никак не зависит от результата вычисления cos(a).

Итоги и выводы

Покрытие фич языка еще можно усилить: поддержка массивов, матриц и всех встроенных операций — задача чисто техническая, просто требующая затрат по времени. Как оказалось, сделать value range analysis даже для такого простого и узкоспециализированного языка, как GLSL — задача непростая. Без решения этих проблем неизбежны ложные срабатывания, шум от которых может в итоге перевесить пользу от статического анализа. А вот как решать ситуации с зависимостями между переменными — вопрос пока для меня неясный.

При этом на других языках можно хотя бы юнит-тесты писать, а тут — никак. С учетом того, с чем я столкнулся, я не особо удивлен отсутствию каких-то известных инструментов для value range analysis в других языках — в них проблем явно больше, чем в относительно простом GLSL.

Тогда можно писать юнит-тесты на исходный код и покрывать все граничные условия. Альтернативным решением может стать компиляция из других языков в GLSL — вот тут недавно была статья про компиляцию из kotlin. Или сделать “динамический анализатор”, который будет прогонять те же данные, что идут в шейдер, через оригинальный код на kotlin и предупреждать о возможных проблемах.

Библиотеки увы не получилось, но может быть кому-то этот прототип пригодится. Так что на этом этапе я остановился.

Репозиторий на github, для ознакомления:

Попробовать:

Бонус: особенности сборки webassembly с разными флагами компилятора

На тот момент я сильно переживал за размер выходного wasm-файла, хотелось чтобы он был маленьким. Изначально я делал анализатор без использования stdlib — по старинке, с массивами и указателями. Но начиная с некоторого момента я начал испытывать дискомфорт и потому решил перевести все на stdlib — умные указатели, нормальные коллекции, вот это все.

Ну и еще посмотреть, насколько хорошо/плохо cheerp (и используемый им clang) оптимизирует код. Соответственно я получил возможность сравнить результаты сборки двух версий библиотеки — с stdlib и без нее.

Согласен, не самый большой пример, но для сравнительного анализа имхо достаточно. Поэтому я скомпилировал обе версии с разными наборами флагов оптимизации (-O0, -O1, -O2, -O3, -Os и -Oz), и для некоторых из этих версий сделал замеры скорости анализа 3000 операций с 1000 ветвлениями.

Что получилось по размеру wasm файла:

Я предположу, что в O3 имеет место агрессивный инлайн всего на свете, что и раздувает бинарник. Удивительно, но по размеру вариант с "нулевой" оптимизацией получается лучше, чем почти все остальные. Ожидаемо версия без stdlib получилась покомпактнее, но не настолько, чтобы терпеть такие унижения лишать себя удовольствия работы с удобными коллекциями.

По скорости выполнения:

При этом разница между версиями с stdlib и без нее практически отсутствует (я делал по 10 замеров, думаю на большем числе разница вообще исчезла бы). Теперь мне видно, что -O3 не зря ест свой хлеб, если сравнивать с -O0.

Стоит отметить 2 момента:

  • На графике представлены средние значения из 10 последовательных запусков анализа, однако на всех тестах самый первый анализ длился в 2 раза дольше остальных (т.е., скажем, 120мс, а следующие уже в районе 60мс). Вероятно происходила какая-то инициализация WebAssembly.
  • С флагом -O3 я отхватывал какие-то ужасно странные баги, которых не ловил для других флагов. Например, функции min и max внезапно начинали работать одинаково — как min.

Заключение

Всем спасибо за внимание.
Пусть значения ваших переменных никогда не выходят за отведенные рамки.
А вот вы — выходите.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть