我如何尝试制作GLSL静态分析器（以及出了什么问题）

有一次，我为Ludum Dare做准备，并做了一个简单的游戏，其中我使用了像素着色器（其他未带入Phaser引擎）。

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

经过测试后，我将链接扔给了一个朋友，并从他那里收到了这样的屏幕截图，其中包含“这很正常吗？”

不，那是不正常的。 仔细查看着色器代码后，我发现了一个计算错误：

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

因为 由于常数R1小于M，因此在某些情况下，pow的第一个参数的结果为小于零的数字。 至少对于GLSL标准而言，负数的平方根是一个神秘的东西。 我的视频卡并没有感到困惑，它以某种方式脱离了这个位置（似乎是从0号战俘归还的），但是对于朋友来说，它更容易辨认。

然后我想：将来可以避免此类问题吗？ 没有人会犯错误，尤其是那些不在本地复制的错误。 您无法编写GLSL的单元测试。 同时，着色器内部的转换非常简单-乘法，除法，正弦，余弦...真的不可能跟踪每个变量的值并确保在任何情况下都不会超出值的允许范围吗？

因此，我决定尝试对GLSL进行静态分析。 它产生了什么-您可以在裁减下阅读它。

我会立即警告您：我没有任何成品，只有教育原型。

初步分析

在研究了有关该主题的一些现有文章（并同时发现该主题称为“值范围分析”）后，我很高兴自己拥有GLSL，而不是其他某种语言。 自己判断：

• 没有“动力学”-引用函数，接口，自动推断的类型等。
• 没有直接的内存处理
• 没有模块，链接，后期绑定-着色器的完整源代码可用
  输入值的范围通常是众所周知的
• 很少的数据类型，而那些围绕浮点数。 int / bool很少使用，遵循它们并不重要
• 很少使用ifs和loops（由于性能问题）。 循环（如果使用）通常是简单的计数器，可以遍历数组或多次重复某种效果。 没有人会在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. 如果范围超出任何给定的边界（例如，可能会出现负数，或者红色组件中的“输出颜色” gl_FragColor大于1），则需要显示警告

二手技术

在这里，我有一个漫长而痛苦的选择。 一方面，我的主要工作范围是检查WebGL着色器，所以为什么不使用javascript在开发过程中在浏览器中运行所有内容。 另一方面，我很长时间以来一直在计划脱离Phaser，并尝试使用另一个引擎，例如Unity或LibGDX。 也将有着色器，但是javascript将消失。

第三，任务主要是为了娱乐。 动物园是世界上最好的娱乐场所。 因此：

1. 用javascript完成GLSL代码解析。 只是我很快就找到了用于在AST中解析GLSL的库，并且测试用户界面似乎对基于Web的情况更加熟悉。 AST变成一系列命令，发送给...
2. ...第二部分，用C ++编写并编译成WebAssembly。 我是这样决定的：如果我突然想将此分析器固定到其他引擎上，则使用C ++库，这应该最简单地完成。

一切，现在您可以走了。

简要介绍一下模型

分析器将在着色器中找到的变量列表保存在内存中，并为每个变量存储当前可能的值范围（例如[0,1]或[1,∞) ）。

分析仪将收到如下工作流程：

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

在这里，我们称为sin函数，将id = 3和4的变量馈入该函数，并将结果写入变量1和2。此调用对应于GLSL-th：

 vec2 a = sin(b); 

请注意空参数（标记为“-”）。 在GLSL中，几乎所有内置函数都针对不同的输入类型集（即 有sin(float) ， sin(vec2) ， sin(vec3) ， sin(vec4) 。 为了方便起见，我将所有重载版本都采用一种形式-在本例中为sin(vec4) 。

分析器输出每个变量的更改列表，例如

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

这意味着“分支1的第10行中的变量2的范围为-1到1（含1和1）（我们稍后将讨论分支）。 现在，您可以精美地突出显示源代码中的值范围。

好的开始

当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() { 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来自纹理，因此该变量的值介于0到1之间。但是k可以取什么值？

您可以通过简单的方法“合并分支机构”-计算每种情况下的范围并给出总数。 对于if分支，我们得到k = [0,2] ，对于else分支，我们得到k = [0,1] 。 如果合并，结果为[0,2] ，并且需要给出一个错误，因为 大于1的值属于gl_FragColor的输出颜色。

但是，这显然是虚假警报，对于静态分析仪而言，没有什么比虚假警报更糟糕的-如果在“狼”的第一声哭声之后没有关闭，则肯定会在第十声响之后关闭。

因此，我们需要分别处理两个分支，并且在两个分支中，我们都需要弄清楚变量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; } 

因此，当分析仪遇到某个特定条件时，该条件根据范围而表现不同，它将为每种情况创建分支（分支）。 在每种情况下，他都会优化源变量的范围，并进一步向下移动命令列表。

值得说明的是，这种情况下的分支与if-else构造无关。 当变量的范围分为多个子范围时，将创建分支，并且原因可能是可选的条件语句。 例如，step函数还创建分支。 下一个GLSL着色器与上一个相同，但不使用分支（顺便说一句，在性能方面更好）。

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

如果<0.5，则步进函数应返回0，否则返回1。 因此，也将在此处创建分支-与前面的示例类似。

细化其他变量

考虑稍作修改的先前示例：

 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计算得出a 。 如果您记住此信息，则在分支时，分析器可以遍历所有源变量并通过执行逆计算来优化其范围。

功能和循环

GLSL没有虚拟方法，函数指针，甚至没有递归调用，因此每个函数调用都是唯一的。 因此，最简单的方法是在调用位置（换句话说，内联）插入函数的主体。 这将与命令顺序完全一致。

周期更加复杂，因为 正式地，GLSL完全支持类似C的for循环。 但是，循环通常以最简单的形式使用，如下所示：

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

这样的周期很容易“部署”，即 一个接一个地插入循环主体12次。 结果，经过深思熟虑，我决定到目前为止仅支持这种选择。

这种方法的优点是可以在流中向分析器发出命令，而无需记住任何片段（例如函数体或循环）以供进一步复用。

弹出问题

问题＃1：难以或无法澄清

上面，我们研究了在细化一个变量的值时得出关于另一个变量的值的结论的情况。 并且当涉及诸如加/减的操作时，该问题得以解决。 但是，例如，三角学怎么办？ 例如，这样的条件：

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

如果如何计算内部范围？ 事实证明，使用pi步长会产生无限范围的范围，因此使用起来非常不便。

可能有这种情况：

 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]

但是，考虑到value - val2 ，分析器不会考虑val2是从value获得的，而是使用范围，就好像它们彼此独立。 获得[0,1] - [-1,0] = [0,2]并报告错误。 尽管实际上他应该有一个常数1。

可能的解决方案：不仅为每个变量存储范围的历史记录，而且还存储整个“家族树”-哪些变量依赖于哪个操作，哪些操作等等。 另一件事是“展示”这个血统并不容易。

问题3：隐式依赖范围

这是一个例子：

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

在此，分析仪将假设范围k = [-1,1] + [-1,1] = [-2,2] 。 这是错误的，因为 任何a sin(a) + cos(a)在[-√2, √2]范围内。

正式计算sin(a)的结果不依赖于计算cos(a) 。 但是，它们取决于的相同范围。

总结与结论

事实证明，即使对于像GLSL这样的简单而高度专业化的语言进行值范围分析也不是一件容易的事。 语言功能的覆盖范围仍然可以加强：支持数组，矩阵和所有内置操作是一项纯粹的技术任务，仅需要耗时。 但是，如何解决变量之间具有依赖性的情况-我仍然不清楚这个问题。 如果不解决这些问题，肯定的错误肯定是不可避免的，由此产生的噪音最终可能超过静态分析的好处。

考虑到我遇到的问题，对于没有其他语言进行价值范围分析的知名工具，我并不感到特别惊讶-与相对简单的GLSL相比，它们显然存在更多的问题。 同时，您至少可以用其他语言编写单元测试，但是在这里您不能这样做。

另一种解决方案可能是将其他语言编译成GLSL-最近有一篇关于kotlin编译的文章 。 然后，您可以为源代码编写单元测试，并涵盖所有边界条件。 或制作一个“动态分析器”，该分析器将运行通过原始kotlin代码输入到着色器的相同数据，并警告可能的问题。

所以在这一点上我停了下来。 遗憾的是，该库无法正常工作，但是此原型可能对某人有用。

github上的存储库，以供审查：

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

尝试：

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

奖励：具有不同编译器标志的Webassembly功能

最初，我是在不使用stdlib的情况下进行分析器的-带有数组和指针的老式方法。 当时我非常担心输出wasm文件的大小，我希望它很小。 但是从某点开始，我开始感到不舒服，因此决定将所有内容转移到stdlib-智能指针，普通集合，仅此而已。

因此，我有机会比较两个版本的库的汇编结果-有和没有stdlib。 好吧，还请看一下削切效果好坏（以及它所使用的叮当声）如何优化代码。

因此，我用不同的优化标志集（ -O0 ， -Oz ， -O2 ， -O3 ， -Os和-Oz ）编译了两个版本，对于其中一些版本，我测量了1,000个分支的3,000个操作的分析速度。 我同意，不是最大的例子，但是恕我直言就足以进行比较分析。

根据wasm文件的大小发生了什么：

令人惊讶的是，带有“零”优化的大小选项几乎比其他所有选项都更好。 我将假设O3一个攻击性的内联函数，它膨胀了二进制文件。 没有stdlib的预期版本更紧凑，但没有那么多 忍受这种屈辱 使您无法享受使用便捷收藏的乐趣。

通过执行速度：

现在，与-O0相比，我可以看到-O3没有白白吃面包。 同时，几乎没有带stdlib的版本之间的差异（我进行了10次测量，我认为使用更大的数字，差异将完全消失）。

值得注意两点：

• 该图显示了连续10次分析的平均值，但是，在所有测试中，第一个分析的持续时间是其余分析的2倍（即120毫秒，下一个已经约为60毫秒）。 WebAssembly可能已初始化。
• 使用-O3标志，我捕获了一些其他标志没有捕捉到的非常奇怪的错误。 例如，min和max函数突然开始以相同的方式工作-如min。

结论

谢谢大家的关注。
让变量的值永远不会超出范围。
然后你去。