开源光栅化渲染器SALVIA的漫长五年

SALVIA是从07年底开始开发的。历经五年，无论是设计目标，还是使用到的一些方法，都和最初差别很大。

谨以此文，纪念我在五年中作出来的各种傻逼决定。

1. 2007年9月 - 2007年12月：可笑的动机，可笑的雏形

动机与原型

SALVIA出现的原因其实很可笑。07年底的时候我正在写一篇paper，将GP-GPU的。那个时候还没有CUDA一类的东西，一切都要靠Shader来。本来我手上的显卡是一块9550的SDRAM的简版。但是论文快结束的时候，突然这卡的风扇就罢工了。然后我降频用了大概一个多月，卡也废掉了。因为没钱买新显卡，我就打算写一个比D3D REF快的软件渲染器。

07年底的时候，实现了第一版的SALVIA，当时还叫SoftArt。第一版的SALVIA其实还算不错，流水线的完整程度我到现在都还没超过，甚至包括Cpp的Vertex Shader和Pixel Shader，纹理采样、光照什么的一应俱全。在开发过程中，主要参考GL 2.0的Specification，也阅读了一些同类型软件的代码，例如Muli3D和Mesa。

一些对管线至关重要的概念，例如透视修正、固定管线上纹理采样的LoD Level、Clip都是借助于Spec和这些时间建立的。

为什么要有Shader Compiler

如果是固定管线的话，那么SALVIA做到这些特性也就足够了。但是从SALVIA一开始，我就希望让它成为一个Pure Shader的管线。固定管线的那些状态实在太烦人了。本来Cpp实现的Shading language能满足绝大部分的需要了，但是有一个特性彻底难倒了我：Pixel Shader的差分函数ddx/ddy。

这个东西的工作原理是这样的：

比方说我有一段shader函数：

?

1 2 3 4 5 6

float shading_pixel( ... ): COLOR0 {       float x;      // Expression for calculating x      return ddx(x); }

在Pixel Shader运行的时候，它是一次性执行2x2的一个小块，所有的指令对于整个块内都是同步执行的。然后遇到ddx(x)后，四个像素都正好执行到这里，然后把x方向上的相邻两个像素的局部变量x求个差，就可以得出ddx了。

这个要求让我在C++中很难实现。

1. 不好让C++的四个函数都在同一个地方Join；
2. 我不好去获得相邻函数的栈上的值。

其实如果要较真，当然还是有办法的：

1. 对于Join问题，起码有两种方案：
   • 自己搞一个Fiber Manager，直接控制代码的栈的Switch。每个pixel都有一个Fiber，到了DDX/DDY就换到下一个Fiber执行，直到所有的Fiber都执行完毕后，计算ddx，写入栈变量，再继续执行；
   • 直接用线程，Join，计算，然后继续执行。
2. 对于栈变量的地址问题，也有办法：
   • 在切换线程的时候直接保存临时变量的地址。

但是这些实现，要么因为切换上下文而变得奇慢无比；要么就是完全没有平台移植性。想来想去，还是要让代码按照硬件的方式SIMD执行。

所以我最终横下一条心：要为它做Shading Language Compiler。然后开始了漫长的Compiler开发。后来我看团长那个《漫无止境的八月》的时候，简直就是对着镜子照自己的傻逼。于是我更黑团长了。

2. 2008年初 - 2009年12月：黎明前的黑暗

Shaer的文法

08年到09年我都在外面实习，一周上六天班，一天得干上十个多小时。到2008年7月份，我都一直在看编译原理和成熟的语法库。但是底子薄，看起来还是很吃力的。到了8月份，开始设计Shader的EBNF。设计语言，不外乎是三个方面：应用场景、语法和库的支持。尽管有现成的HLSL和GLSL作参考，但是对于我从0开始设计语言来说，这些语言的语法和语义都过于复杂了。我需要让我的语言特性慢慢的添加进来。

考虑到HLSL和C比较接近，C的文法参考资料有很多，于是我选择了从C开始裁剪语法。但是文法这个东西，并不简简单单是树状的结构，树上的任何一个语法节点，都可能会引用到其它的文法规则。因此修改了一条规则后，你会发现它可能会和其它规则冲突了，二义了。于是裁剪计划完蛋了。

当然，如果我现在来设计语法，肯定会和陈汉子一样，直接从Use Case就能把EBNF写出来，再稍微规范一下，一门不那么复杂的语言就成了。当然像C++这种变态语言，这样做是做不出来的。但是当时的我显然不具备那样的能力。所以磕磕绊绊，从七月份开始，裁剪了一些语法特性之后的语言到了八月份才出了个千疮百孔的方案。

神：Boost.Spirit

作为完全不懂编译器的矬货，设计语言一定要和编译器的开发放在一起才能有点收获。我用过Flex/Bison，用过ANTLR。但是当时我对编译器特别的陌生，组织Build的能力也比较弱，因此它们的繁琐和难于调试给我带来了很大的困扰。但是在当时我对模板、元编程和Boost就已经相当熟悉了，无论是开发、阅读代码还是Debug都能轻松应付，所以我挑了半天，选了Boost.Spirit。

Boost.Spirit是个很奇葩的东西。它想在C++里面提供一个类似于EBNF，可以定义语法分析规则的方言。要让C++看起来像一个方言，当然是要使用神出鬼没的操作符重载。当然，即便是修饰后的语法，看起来也还是会有点怪怪的。EBNF中的规则

?

1	Rule ::= Token SubRule0 [OptionalSubRule1]

在Cpp中最简单可以表示成

?

1	rule = token >> subrule0 >> optional(OptionalSubRule1)

虽然看起来有点丑陋，但是它已经完全满足一个DSL的要求了：直观的面向解决方案。

不过如果牵涉到实现细节，在C++里面，要写一个又简单、又可用Parser Generator，那几乎是不可能完成的任务。起码对于Combinator-based Parser来说，它够简单，但是没有CPS的支持会令错误恢复这一类的周遭设计变得极为可怕；如果Rule只是grammar definition，不牵涉到任何Parser的构造，那解析这个definition的复杂度和调试难度又不亚于ANTLR或者Yacc这样有单独脚本的工具。所以这项工作，还是交给Haskell这样的语言来完成吧。

扯远了。不过通过Spirit，通过设计编译器，通过折腾文法，起码我对Compiler和Cpp的理解都递进了一大步。再加上08年全年都在做GUI相关的东西，也让我对编译器的理解有所加深。

09年下半年我一直都比较动荡，不过到年底总算是安定了下来。

3. 2009年12月—2010年2月：长征的开始

后端与前端

09年12月份的时候，Boost升级了，Spirit也到了V2。到了2月份，我费了点功夫，把Spirit升级上来。前一版的Parser还比较草率，这一版的Parser我几乎是完全按照Spirit的Demo中的方案进行的。此时我也开始尝试着撰写语义分析。怎么做函数重载都是在那个时候开始点的技能树。当然当时的技能树完全是歪的。为了执行生成的代码，我设计了半个虚拟机，然后还准备写点教程。但是我思前想后，对于Shader这样一秒钟要调用10M次的函数，无论如何虚拟机都是不合适的。

所以我就开始筹备自己的后端。要求就是一个字：快。那个时候，陈汉子正在学怎么写x86的JIT。但是我的语言到x86有很长的路要走。怎么去分配寄存器，怎么把类型转换到x86的Native，怎么选择指令，我都是一知半解的。凭我当时的知识，这一定是不可能完成的。

于是在阅读完Intel Architecture手册和优化指南后，我决定去找一个合用的后端。但是我考虑过很多可选的办法，例如生成C++的Code然后编译成DLL；使用Tiny C（TCC）；或者是JIT。但是它们缺点都是很明显的。编译成DLL必须要自己裁剪一个GCC出来；Tiny C的效率并不是很好；JIT很复杂（起码在那个时候是这样）。不过2月份的时候，敏敏还是谁指点了我一下，说你可以去看看LLVM。然后我去一看，牛逼，就是我要的东西！然后我就开始学LLVM。LLVM的IR很好学，一个下午就搞了个Hello world。

这个时候，minmin也在SALVIA上实现了Half-Space的光栅化算法。

那个时候我踌躇满志，意气风发，三月赶英，五月超美。

可没想着就这么掉坑里面去了。

4. 2010年2月—2011年新年：苦难的行军

苦难：复杂的问题

主体大人真是神，五个字就概括了我2010年一年的努力。

• minmin做的SALVIA的Half-Space算法并不比我朴素的Top-Bottom的光栅化强；
• 纹理上的优化尽管使用了SSE但是仍然改进有限；
• Shader编译器本身的编译时间由于Spirit的存在而实在漫长；
• Shader编译器和Pipeline如何关联又无从下手；
• LLVM的集成也因为前端而有所耽搁，另外因为各种错误层出不穷，让整个开发进度变得龟速。

所以整个一年中，SALVIA的开发就是写写停停，停停写写，可以说08年初的锐气，已经消磨的差不多了。到了8月份的时候，我毕业了，新工作也基本上确定和熟悉了，我就和minmin说，从现在开始我写半年报吧，讲述一下半年来的进展。于是便有了第一篇项目简报。

行军：些微的进展

也正是从那个时候，我决定要把SALVIA作为一款实验品来对待，用上所有我不会的或者新学的东西。单元测试，CMake工具链，为Shader设计的Pipeline，语义分析和后端的原型都在那一年加入了SALVIA。虽然从实现上它们已经与现在相距甚远，但是起码一切都还是往好的方向发展。

另外对于我来说，08年到09年期间在实习的时候积累的教训开始慢慢的酝酿和发酵，敏捷也逐渐成为了我开发过程中的主要指南。

基本上，那个时候积累了很多必要的经验和教训。当然绝大多数是教训。

5. 2011年2月—2011年6月：新Shader的起点

坑神：Boost.Spirit的灭亡

在11年的春节期间，我终于无法忍受Spirit的麻烦了：

• 一段400行不到的代码，在我的机器上需要编译30分钟；
• Object File需要占用1.9G的硬盘；
• Mangling name轻松超过4K字符的限制；
• 轻易撑爆obj文件的symbol table，需要用/bigobj才能够编译通过；
• 甚至在编译的时候会轻易的让32位的MSVC CL out of memory。

这一切原因，都是因为Boost.Spirit对于Parser Tree，是用了完全静态的分析树结构。每条规则的返回值都会是完全不同的类型。

要知道，以上这些还是应用了Spirit指南中的编译速度优化方案之后的结果。

于是11年的寒假我花了5天的时间重新山寨了一个Spirit。Parser Tree不再是静态类型；模板的用量也减轻了很多。而且在DSL上几乎完全和Spirit一致。

Shader的阶段性成果

到了四月份的时候，Shading Language Semantic/System Value已经在语法上支持了，语义上也能分析出哪些变量是System Value，哪些变量是Uniform的。并且通过生成特殊的函数签名，Shader满足了以下几个需求：

1. Shader要返回一个函数；
2. 这个函数是可重入的（因为要并发）；
3. 数据能正确的从Pipeline传入到Shader的函数中，也能正确的返回；
4. Shader中对于Pipeline数据引用要能正确的生成地址。

到了11年6月份的时候，终于把Shader全线贯通。虽然很多Operator和Instrinsic还不支持，但是起码有了个可以看的Demo。

第一个版本与发布前的完善工作

LLVM用上了；VS完整了，PS也有了个雏形；预处理器什么的都有了。

Unit Test也已经成型。之前将为每个Stage都做了Unittest：Parser，Semantic，CodeGen和JIT。但是这样做有很多的缺陷。

某种意义上来说，这几个月来在后端上顺利进展，让我多少有点得意忘形。再加上梁总的帮助，SoftArt这个名字改成SALVIA，LOGO也有了，我在部门内部做的一些Introduction也帮助我梳理了思路。于是从4月份开始，我就筹备着要把SALVIA正式发布出去。

11年6月1号，SALVIA Milestone 1.0 发布。有Change Log，有Binary Demo，有Snapshot。

不过我的第一个VS Demo，是在三周之后才发布的。

6. 2011年7月—2012年1月：坂道の1.0

Pixel Shader：需求与设计

在Milestone 1.0发布后，我开始做Pixel Shader的特性。本以为半年之内就能搞定，发个1.0扬眉吐气一下。但是实践证明，我真是他妈的太盲目乐观了。

我先来说一说Pixel Shader的特点和需求。比方说我有四个pixel，每个pixel都是一个float。

?

1 2 3 4 5 6

struct pixel_input {    float data; };   pixel_input pixel_block[4];

然后我要计算一下，这个data加上1.0之后是多少。我前面说过，我要让指令看起来是四个像素同一时刻执行的，那么显然我生成的代码就会类似于这样：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

struct pixel_input {    float data; };   struct pixel_output {    float data; };   void shading_pixel(pixel_input* in_data, pixel_output* out_data) {       // TMP = IN_DATA.DATA + 1.0       float tmp0 = in_data[0].data + 1.0;       float tmp1 = in_data[1].data + 1.0;       float tmp2 = in_data[2].data + 1.0;       float tmp3 = in_data[3].data + 1.0;        // OUT_DATA.DATA = TMP      out_data[0].data = tmp0;      out_data[1].data = tmp1;      out_data[2].data = tmp2;      out_data[3].data = tmp3; }

Pixel Shader：优化与问题

显然这里是可以优化的：将四条指令并作一条SIMD指令。

那么这个时候，有两个需求是要满足的：

1. 同样的struct member一定要是邻接在一起。
2. 得根据SIMD的要求数据对齐。

只有一个域当然好办。如果struct很复杂呢，比方说下面这样：

?

1 2 3 4 5 6 7 8 9 10 11

struct {     float ;     float2;     int3;     struct     {         float2[3];         float ;     }; };

那就会衍生出各种问题：

• 那要不要把每个域都展平呢？
• 展平到什么程度？
• 让每个Builtin Type Member相邻，还是让每个Float/Int相邻？
• 那遇到动态寻址，怎么办？
• 展平后的代码，与VS中的代码能通用吗？

每个方案都一定能完成，每个方案都有明显的缺陷。最初我是想尝试四个像素完全独立的办法，这样实现起来最方便。但是出于对性能的追求，我又想做展平的。展平的方案做到一半，发现太复杂了。

坑神II：LLVM

此外，还有几个非常严重的问题，发生在LLVM上。

一个是ABI。一个符合C Calling Convention的LLVM函数，它对堆栈的理解与VS完全不同，特别是参数传入或者返回Struct的时候。这样，直接用LLVM的函数Export出来后，让VC去Call它就一定会失败。为了解决它，我花了近两周的时间，设计了一个Proxy，让函数避免用Struct来传递，一切数据，除了和寄存器同样大小的float和int，其余数据都通过指针来做。同时，我需要将一些函数注入到LLVM中，比方说纹理采样，ABI同样是个祸患。为了让Code Gen正确的识别函数是LLVM的调用协议还是我自己定制的调用协议，并产生正确的代码。我做了各种奇葩和傻逼的方案。有一些方案被废弃了，但是主要的Idea，仍然沿用到现在。

一个是临时变量（包括Spiller）的对齐。在Linux/GCC上，栈顶和栈基指针一定是16字节对齐的。如果编译器需要分配一个临时变量，那么它只要通过ESP - 0x10*n就能获得一个对齐的地址。但是在VC中，x86下完全没有这样的限制（除非函数中使用了__m128，这个时候在进入Frame之后会有一个SUB/AND的指令把栈顶搞到16字节对齐。）。但LLVM生成的所有代码，又是基于GCC的假设。SALVIA生成的局部变量，还可以控制地址，但是对于编译器临时生成的变量来说，就完全不可控了。在3.1之后因为引入了AVX，需要32字节对齐，这个问题就更加变本加厉了。在x86上，我还可以通过嵌入汇编，来强制调整栈帧。但是在x64上，又启动了AVX的情况下，我就彻底没有办法了。

SIMD执行模型下分支的处理

Pixel Shader的执行模型是SIMD的，这要求每个像素上同一时刻都执行相同的指令。如果没有分支，那自然是简单无比。一旦有了分支就打破了这个约定。在DX9.0b及之前，这当然没问题。

但是Shader Model 3.0正式支持Dynamic Branch开始，这个问题就凸现出来了：分支要怎么处理？

对于Pixel Shader来说，会面临三种分支：静态分支，准静态分支（这个名字是我瞎起的）和动态分支。

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

float branches( uniform float udata, float vdata: POSITION): COLOR0 {     const float zero = 0.0;     if (zero < 1.0)     {       // Static branch     }       if (udata)     {        // Semi-Static Branch (我自己造的)     }         if (vdata)     {       // Dynamic Branch     } }

我们来分情况讨论一下：

• 对于静态分支来说，因为确定分支的是一个常量，那么显然在编译阶段就能够知道分支执行与否，直接生成对应的代码就可以了。
• 对于uniform作为判断条件的分支来说，在shader编译的时候，并不知道这个分支是否会执行。但是呢，Uniform会在Shader执行前设置，和代码执行相比，Uniform设置的比例非常低。这个时候我们可以先讲代码编译成中间表达，这个中间表达会知道一个变量是不是Uniform的。在Uniform设置好后，Shader真正执行前，把Uniform替换成那个值，也就是把Uniform当做常量，对Shader再编译一次，得到真正的执行指令。所以在指令执行的时候，准静态分支就和静态分支完全相同了。
• 最后一个，动态分支。如果判断条件就是动态的，那没办法，如果要支持SM3.0，就必须要能支持它。同时对于不同的Pixel，都可能有不同的分支。这对于SIMD来说，才是真正的难题。

实际上，我们真正要解决的，就是动态分支。

对于SIMD模型来说，动态分支有三种处理办法。

1. 跳转执行。像CUDA 2.0以上那样的指令集具备有一定的跳转执行能力。编译器可以把SIMD拆开，按照标量执行。每个都执行完了后，再继续按照SIMD执行其他的代码。
2. 条件执行。这也是图形硬件上最常见的执行模式。通过一个位，就可以让GPU中的执行单元执行或者放弃执行一段代码。举个不准确的例子，如果是个4并发的执行器，那么四个并发执行器的执行条件可以设置为1100，这样就只有前两个单元的数据执行，后两个不执行了。
3. 写掩码。这个办法是没有办法的办法。它的基本理念就是：只要不写到内存中的执行结果，就可以认为它没执行过。但是写掩码总是浪费了指令。不过好歹它还是避免了跳转的。所以对于早期的ARM这样没有分支预测的精简体系来说，一旦有分支执行起来就是死翘翘。所以它有类似于Select-Store这样的指令，尽可能的避免分支的出现。

对于SAVLIA来说，跳转执行和写掩码是两个可能的选择。因为写掩码的代码生成起来更加轻松一些，所以目前的SALVIA的实现是写掩码的。在x86/x64平台上，对于AVX以上的指令，还可以用blend。但是对于其他指令而言，基本上只能是通过跳转实现写掩码。所以这部分的开销其实很大。等到造出了自己的SSA之后，再来考虑分支执行的事情吧。

对于写掩码的掩码要怎么计算，一开始我心里挺没谱的。特别是有了，Continue和Break之后，情况就会变得复杂起来。一开始我没法确信自己的方案是正确的。后来看了MESA的Gallinum以后，看见了Continue Mask和Break Mask两个变量，瞬间就明白了。

具体怎么思考的不多说了，这里写下几个结论：

1. 语言不能有Goto（有Goto会让代码变得非常复杂，甚至不可解）；
2. 所需要的掩码的数量会随着循环的嵌套层数的增加而增加；
3. 每个循环最多有三个掩码：Break，Continue和Mask；
4. 程序是固定的话，掩码的数量就一定是个常量。（要不然硬件就没法做了）
5. 写掩码的位数只和执行单元的数量有关，和嵌套深度无关。

坂道のTest

尽管遇到了各种难处，但是很多方案还是顺利的做出来了。方案和方案之间差异很大，要想顺利移植，必须要有Test。

之前也说过，一开始我的Test是按照Parser，Semantic，Code Gen，JIT分开做的。但是呢，这样一来，不同Stage之间的Test复用性非常高。而且因为Stage经常变化，一旦变化了API，Test就完蛋了。Test本身也很枯燥（变量名都不好起），所以Test重写起来难过的要死。

于是我重新审视了一下需求。发现我最终只关心JIT编译出来的函数的运行结果，其实并不关心中间的过程。而且随着我对编译过程理解的逐步变化，Compiler Stages几乎每隔两个月就要进行比较大的修正。测试的量稍微大一点，就没有办法维护Test Case了。并且，对于单条语句或者非常短的函数来说，从词法到最终JIT出来的函数所覆盖的编译器代码非常之少，可能3-4个函数，代码就出来了。即便有问题，对比过去的版本轻松就能分析出来。再加上大量的Assertion，诊断起来更加容易。

因此，在这几个月中我完全重写了Test Case：让JIT的测试粒度更低，测试更丰富；取消所有的中间Level的测试。于是新的测试回归起来非常容易，出了问题也很好找到。在Test Case写完后，正好看到Martin Fowler喷过度TDD的问题，真是感同身受。

测试需要吗？当然需要。但是选择合适的Level，做合适的测试是非常重要的。结合之前实习的时候的Unit Test经验，有以下几点感受：

1. 测试一定要选择尽可能低的面，这样牵涉的代码就尽可能少；
2. 在纵向上，粒度要细。除了单个API的Test，还要有适度的交叉，不过太综合的测试，请让集成测试用例来完成；
3. 要重视代码覆盖率；
4. 选择API要尽量稳定。天天变得API会让你彻底失去写Test的信心。API越稳定，在它上面出现问题的机会就越多，你写的测试也越多。

坡长路远，小步快走

在完成了Test的改造后，终于有了一个合适的发布前评估。所以到了11年11月后，发布的速度就明显变快了许多。实际上快速的发布对于做一个长期项目来说非常重要。这也和敏捷的想法不谋而合。不管是从品质控制上、还是进度追踪上，或者是说对开发者自信心的增强，都需要有短平快的开发周期。11年也正好是Autodesk推行敏捷的一年。同事里面有很多的人反应说敏捷会导致软件品质的下降，短期目标会导致过于追逐眼前利益。

但是从我的经验来看，对于个人，敏捷要短平快。对于团队，敏捷要从长计议。不是所有的iteration都需要开发新特性，必须要保留足够的Iteration来完成重构，整理，设计方案的反省和讨论。对于以年为单位的长周期产品来说，可以每个季度有3-5天的时间，每个人都提出对框架的改进计划；每年有两周的时间，完成框架的重构和修正。更小的重构，可以安排的更加短小的时间。

6. 2011年7月及以后：现在与未来

新特性，新思考

从7月份开始到现在，Demo，优化，特性的完善；以及一些新特性的思考。

总的来说，这一年半的时间里面，很多工作已经不像早先几年做的那么吃力，但是仍然在很多的点上有所斩获。

• 整个编译器后端，包括基本的分析和优化都已经有所了解，LLVM也熟悉了许多；
• 对Shader相关的API的了解也不再懵懵懂懂；
• 对于语言机制的研究，加上陈汉子时不时抛来的一些思维发散题令我对语言有了更深入的认识；
• 认识了RFX，在短短几周就帮助我在阅读V8和LLVM时积累的一些知识转化成了有用的理解。

在2012年底为SALVIA进行了局部的重新设计，也是“学”与“习”的新一轮“习”。新的SSA及Shader优化、JIT化的管线、对性能有要求的新前端、瞄准DX11以上Shader Model Features，这些一定会给我带来许多绞尽脑汁想不明白的问题，但同时我也会学习到、实践到许多新的知识。

我相信时间会教给我们一切。