Como tentei criar um analisador estático GLSL (e o que deu errado)

Uma vez eu estava me preparando para Ludum Dare e fiz um jogo simples em que usei pixel shaders (outros não foram trazidos para o mecanismo da Phaser).

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

Após o teste, joguei o link para um amigo e recebi dele uma captura de tela com a pergunta "isso é normal?"

Não, isso não era normal. Depois de examinar atentamente o código do sombreador, encontrei um erro de cálculo:

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

Porque Como a constante R1 era menor que M, em alguns casos, o resultado no primeiro argumento de pow foi um número menor que zero. A raiz quadrada do número negativo é uma coisa misteriosa, pelo menos para o padrão GLSL. Minha placa de vídeo não estava confusa e, de alguma forma, saiu dessa posição (ao que parece, depois de devolvê-la do pow 0), mas acabou sendo mais legível para um amigo.

E então pensei: posso evitar esses problemas no futuro? Ninguém está a salvo de erros, especialmente aqueles que não são reproduzidos localmente. Você não pode escrever testes de unidade para GLSL. Ao mesmo tempo, as transformações dentro do shader são bastante simples - multiplicação, divisão, senos, cossenos ... É realmente impossível rastrear os valores de cada variável e garantir que, sob nenhuma circunstância, vá além dos limites permitidos de valores?

Então, decidi tentar fazer uma análise estática para o GLSL. O que veio a seguir - você pode lê-lo sob o corte.

Avisarei você imediatamente: não consegui nenhum produto final, apenas um protótipo educacional.

Análise preliminar

Depois de estudar alguns dos artigos existentes sobre esse tópico (e ao mesmo tempo descobrir que o tópico se chama Análise de Faixa de Valor), fiquei feliz por ter GLSL, e não outra linguagem. Julgue por si mesmo:

• sem "dinâmica" - referências a funções, interfaces, tipos inferidos automaticamente, etc.
• sem manipulação direta de memória
• sem módulos, vinculação, ligação tardia - todo o código fonte do shader está disponível
  intervalos geralmente são bem conhecidos pelos valores de entrada
• poucos tipos de dados e esses giram em torno de um flutuador. O int / bool raramente é usado e não é tão importante segui-los
• ifs e loops raramente são usados ​​(devido a problemas de desempenho). loops, se usados, geralmente são contadores simples para passar por uma matriz ou repetir um determinado efeito várias vezes. Ninguém escreverá tanto horror no GLSL (espero).

 //   - 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 

Em geral, dadas as limitações do GLSL, a tarefa parece ser solucionável. O algoritmo principal é o seguinte:

1. analise o código do sombreador e construa uma sequência de comandos que alteram os valores de quaisquer variáveis
2. conhecendo os intervalos iniciais para as variáveis, passe pela sequência, atualizando os intervalos quando eles mudam
3. se o intervalo violar qualquer limite especificado (por exemplo, um número negativo pode aparecer, ou algo maior que 1 chegará à "cor de saída" gl_FragColor no componente vermelho), será necessário mostrar um aviso

Tecnologias usadas

Aqui eu tive uma escolha longa e dolorosa. Por um lado, meu escopo principal é verificar os shaders do WebGL, então por que não o javascript para executar tudo no navegador durante o desenvolvimento. Por outro lado, planejo sair da Phaser há muito tempo e experimentar outro mecanismo como o Unity ou o LibGDX. Também haverá shaders, mas o javascript desaparecerá.

E por outro lado, a tarefa foi realizada principalmente para entretenimento. E o melhor entretenimento do mundo é o zoológico. Portanto:

1. Análise de código GLSL feita em javascript. Achei que rapidamente encontrei a biblioteca para analisar o GLSL no AST, e a interface de teste parece estar mais familiarizada com a Web. AST se transforma em uma sequência de comandos, que é enviada para ...
2. ... a segunda parte, escrita em C ++ e compilada no WebAssembly. Eu decidi da seguinte maneira: se de repente eu quero prender esse analisador em algum outro mecanismo, com uma biblioteca C ++, isso deve ser feito de maneira mais simples.

Tudo, agora você pode ir.

Brevemente sobre o modelo

O analisador mantém na memória uma lista de variáveis ​​que são encontradas no sombreador e, para cada uma, armazena o intervalo de valores possível atual (como [0,1] ou [1,∞) ).

O analisador recebe um fluxo de trabalho como este:

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

Aqui chamamos a função sin, as variáveis ​​com id = 3 e 4 são alimentadas e o resultado é gravado nas variáveis ​​1 e 2. Essa chamada corresponde ao GLSL-th:

 vec2 a = sin(b); 

Observe os argumentos vazios (marcados como "-"). No GLSL, quase todas as funções internas são sobrecarregadas para diferentes conjuntos de tipos de entrada, ou seja, há sin(float) , sin(vec2) , sin(vec3) , sin(vec4) . Por conveniência, trago todas as versões sobrecarregadas para um formulário - neste caso, sin(vec4) .

O analisador gera uma lista de alterações para cada variável, como

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

O que significa "a variável 2 na linha 10 na ramificação 1 tem um intervalo de -1 a 1 inclusive" (falaremos sobre ramificação um pouco mais tarde). Agora você pode destacar lindamente os intervalos de valores no código-fonte.

Bom começo

Quando a árvore AST já começou a se transformar em uma lista de comandos, é hora de implementar funções e métodos padrão. Existem muitos deles (e eles também têm muitas sobrecargas, como escrevi acima), mas em geral eles têm transformações previsíveis de alcance. Digamos que, para esse exemplo, tudo ocorra de maneira bastante óbvia:

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

O canal vermelho da cor de saída está dentro da faixa aceitável, não há erros.

Se você cobrir mais funções integradas, para metade dos shaders, essa análise será suficiente. Mas e a segunda metade - com condições, loops e funções?

Ramos

Tomemos, por exemplo, um sombreador.

 uniform sampler2D uSampler; uniform vec2 uv; // [0,1] void main() { float a = texture2D(uSampler, uv).a; // -> [0,1] float k; // -> ? if (a < 0.5) { k = a * 2.; } else { k = 1. - a; } gl_FragColor = vec4(1.) * k; } 

A variável a é retirada da textura e, portanto, o valor dessa variável é de 0 a 1. Mas que valores k pode levar?

Você pode seguir o caminho simples e "unir os galhos" - calcule o intervalo em cada um dos casos e forneça o total. Para o ramo if, obtemos k = [0,2] e para o ramo else, k = [0,1] . Se você combinar, o resultado será [0,2] e você precisará dar um erro, porque valores maiores que 1 caem na cor de saída de gl_FragColor .

No entanto, esse é um alarme falso claro e, para um analisador estático, não há nada pior que alarmes falsos - se ele não for desligado após o primeiro grito de "lobo", depois do décimo, com certeza.

Portanto, precisamos processar os dois ramos separadamente, e em ambos os ramos precisamos esclarecer o intervalo da variável a (embora formalmente não tenha sido alterado). Aqui está o que pode parecer:

Ramo 1:

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

Ramo 2:

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

Assim, quando o analisador encontra uma determinada condição que se comporta de maneira diferente, dependendo do intervalo, ele cria ramificações (brunches) para cada um dos casos. Em cada caso, ele refina o intervalo da variável de origem e desce a lista de comandos.

Vale esclarecer que as ramificações nesse caso não estão relacionadas à construção if-else. As ramificações são criadas quando um intervalo de uma variável é dividido em subintervalos e a causa pode ser uma instrução condicional opcional. Por exemplo, a função step também cria ramificações. O próximo sombreador GLSL faz o mesmo que o anterior, mas não usa ramificação (que, a propósito, é melhor em termos de desempenho).

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

A função step deve retornar 0 se <0,5 e 1, caso contrário. Portanto, ramificações também serão criadas aqui - semelhante ao exemplo anterior.

Refinamento de outras variáveis

Considere um exemplo anterior ligeiramente modificado:

 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; } 

Aqui a nuance é a seguinte: a ramificação ocorre com relação à variável b cálculos ocorrem com a variável a . Ou seja, dentro de cada ramificação, haverá um valor correto do intervalo b , mas completamente desnecessário, e o valor original do intervalo a , completamente incorreto.

No entanto, o analisador viu que o intervalo b era obtido calculando a partir de a . Se você se lembrar dessas informações, ao ramificar, o analisador pode passar por todas as variáveis ​​de origem e refinar seu intervalo executando o cálculo inverso.

Funções e Loops

O GLSL não possui métodos virtuais, ponteiros de função ou chamadas recursivas, portanto, cada chamada de função é única. Portanto, é mais fácil inserir o corpo da função no local da chamada (em linha, em outras palavras). Isso será totalmente consistente com a sequência de comandos.

É mais complicado com ciclos, porque formalmente, o GLSL suporta totalmente o loop for do tipo C. No entanto, na maioria das vezes, os loops são usados ​​da forma mais simples, assim:

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

Esses ciclos são fáceis de "implantar", ou seja, insira o corpo do loop 12 vezes um após o outro. Como resultado, tendo pensado, decidi até agora apoiar apenas essa opção.

A vantagem dessa abordagem é que os comandos podem ser emitidos em um fluxo para o analisador sem exigir que ele memorize quaisquer fragmentos (como corpos de funções ou loops) para reutilização adicional.

Problemas de pop-up

Problema # 1: dificuldade ou incapacidade de esclarecer

Acima, examinamos os casos em que, ao refinar os valores de uma variável, tiramos conclusões sobre os valores de outra variável. E esse problema é resolvido quando operações como adição / subtração estão envolvidas. Mas, digamos, o que fazer com a trigonometria? Por exemplo, essa condição:

 float a = getSomeValue(); if (sin(a) > 0.) { //    a? } 

Como calcular o alcance de a interior se? Acontece um conjunto interminável de intervalos com etapas pi, o que será muito inconveniente para trabalhar.

E pode haver uma situação assim:

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

Esclarecer os intervalos b no caso geral não será realista. E, portanto, são possíveis falsos positivos.

Problema # 2: intervalos dependentes

Considere este exemplo:

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

Para começar, o analisador considera o intervalo da variável val2 - e espera-se que seja [0,1] - 1 == [-1, 0]

No entanto, considerando o value - val2 , o analisador não leva em consideração que o val2 foi obtido a partir do value e trabalha com intervalos como se fossem independentes um do outro. Obtém [0,1] - [-1,0] = [0,2] e relata um erro. Embora, na realidade, ele devesse ter uma constante 1.

Solução possível: armazenar para cada variável não apenas o histórico dos intervalos, mas também toda a “árvore genealógica” - de quais variáveis ​​eram dependentes, de quais operações e assim por diante. Outra coisa é que "desdobrar" esse pedigree não será fácil.

Problema nº 3: intervalos implicitamente dependentes

Aqui está um exemplo:

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

Aqui, o analisador assume que o intervalo k = [-1,1] + [-1,1] = [-2,2] . O que está errado, porque sin(a) + cos(a) para qualquer a está no intervalo [-√2, √2] .

O resultado da computação do sin(a) formalmente não depende do resultado da computação do cos(a) . No entanto, eles dependem do mesmo intervalo de a .

Resumo e Conclusões

Como se viu, fazer uma análise da faixa de valor mesmo para uma linguagem tão simples e altamente especializada como GLSL não é uma tarefa fácil. A cobertura dos recursos de idioma ainda pode ser reforçada: o suporte a matrizes, matrizes e todas as operações integradas é uma tarefa puramente técnica que requer apenas demorado. Mas como resolver situações com dependências entre variáveis ​​- a questão ainda não está clara para mim. Sem resolver esses problemas, os falsos positivos são inevitáveis, cujo ruído pode superar os benefícios da análise estática.

Considerando o que descobri, não estou particularmente surpreso com a ausência de algumas ferramentas conhecidas para análise de faixa de valor em outros idiomas - há claramente mais problemas neles do que no relativamente simples GLSL. Ao mesmo tempo, você pode escrever pelo menos testes de unidade em outros idiomas, mas aqui não pode fazê-lo.

Uma solução alternativa pode ser a compilação de outras línguas no GLSL - aqui recentemente houve um artigo sobre a compilação a partir do kotlin . Em seguida, você pode escrever testes de unidade para o código-fonte e cobrir todas as condições de contorno. Ou faça um "analisador dinâmico" que execute os mesmos dados que passam para o shader através do código kotlin original e avise sobre possíveis problemas.

Então, neste ponto, parei. A biblioteca, infelizmente, não funcionou, mas talvez esse protótipo seja útil para alguém.

Repositório no github, para revisão:

• https://github.com/AlexeyGrishin/glsl-value-range-analysis

Para tentar:

• https://alexeygrishin.imtqy.com/glsl-value-range-analysis/html/

Bônus: recursos de montagem na Web com diferentes sinalizadores do compilador

Inicialmente, fiz o analisador sem usar o stdlib - da maneira antiga, com matrizes e ponteiros. Naquela época, eu estava muito preocupado com o tamanho do arquivo wasm de saída, queria que ele fosse pequeno. Mas a partir de algum ponto, comecei a sentir desconforto e, portanto, decidi transferir tudo para o stdlib - indicadores inteligentes, coleções normais, isso é tudo.

Dessa forma, tive a oportunidade de comparar os resultados da montagem de duas versões da biblioteca - com e sem stdlib. Bem, veja também como o cheerp bom / ruim (e o clang usado por ele) otimiza o código.

Portanto, compilei as duas versões com diferentes conjuntos de sinalizadores de otimização ( -O0 , -O1 , -O2 , -O3 , -Os e -Oz ) e, para algumas dessas versões, medi a velocidade de análise de 3.000 operações com 1.000 ramificações. Concordo, não é o maior exemplo, mas o IMHO é suficiente para uma análise comparativa.

O que aconteceu de acordo com o tamanho do arquivo wasm:

Surpreendentemente, a opção de tamanho com a otimização "zero" é melhor do que quase todas as outras. Vou assumir que no O3 uma linha agressiva de tudo no mundo, que infla o binário. A versão esperada sem o stdlib é mais compacta, mas não tanto que suportar tal humilhação privar-se do prazer de trabalhar com coleções convenientes.

Pela velocidade de execução:

Agora posso ver que -O3 não -O3 em vão comendo pão, quando comparado com -O0 . Ao mesmo tempo, a diferença entre as versões com e sem stdlib está praticamente ausente (fiz 10 medições, acho que com um número maior a diferença desapareceria por completo).

Vale destacar dois pontos:

• O gráfico mostra os valores médios de 10 execuções consecutivas da análise, mas em todos os testes a primeira análise durou 2 vezes mais que o restante (ou seja, 120 ms, e as próximas já estavam em torno de 60 ms). Provavelmente houve alguma inicialização do WebAssembly.
• Com a bandeira -O3 , peguei alguns bugs terrivelmente estranhos que não peguei em outras bandeiras. Por exemplo, as funções min e max começaram a funcionar da mesma maneira - como min.

Conclusão

Obrigado a todos pela atenção.
Deixe os valores de suas variáveis ​​nunca ultrapassarem os limites.
E aqui está você.