SALVIA 0.5.2 的优化经历是一个“跌宕起伏”的过程。这个过程的结果很简单：

在Core 2 Duo T5800(2.0GHz x 2)上，Sponza的性能提升了60%，ComplexMesh性能提升了26%。

背景

SALVIA的整个渲染流程主要是以下几部分：

• 根据Index Buffer获得需要进行变换的顶点；
• 将顶点利用Vertex Shader进行变换；
• 将变换后的顶点，输出成若干个float4；
• 将三角形光栅化。SALVIA的光栅化是将三角形拆分成4x4的像素块若干，不满的块有掩码来处理；
• 将像素进行插值；
• 插完值后把像素送到Pixel Shader中处理一趟；
• 处理完的结果用Blend Shader塞到Back buffer里面去。

用于测试的场景：

• Sponza 26万个面，20个左右的Diffuse纹理（1024x1024）；
• PartOfSponza 约200个面，4个Diffuse纹理（1024x1024）；
• ComplexMesh 两万个面，无纹理，有个能量保守的光照。

最初的版本（V1231）中，性能的主要瓶颈在插值阶段，各种耗时林林总总占了一半以上（50% - 70%）。

相比之下其他阶段对性能的影响要么有限，要么没有多少优化空间。所以最近一周的优化，就都集中在了“插值”上。

插值算法

线性的插值算法常见的实现有两种，

第一种是拿UV插值，第二种是用ddx和ddy累积。

UV是先计算像素的u和v（基本方法是用面积比，不记得就复习一下中学几何吧），然后用插值公式：

pixel = v0 * u + v1 * v + v2 * (1-u-v)

后者的步骤是选一个主顶点，然后计算这个顶点的ddx和ddy，最后用

pixel = v0 + ddx * offset_x + ddy * offset_y

计算出相应顶点。

但是在图形学中，我们还需要对插值进行透视修正，获得在3D空间中线性的插值结果。

我们将步骤修正到透视空间：

先将v0，v1，v2弄到透视空间中，变成projected_v0, projected_v1, projected_v2

对于UV的插值是

pixel = ( projected_v0*u + projected_v1*v + projected_v2 * (1-u-v) ) / pixel_w

对于用ddx和ddy的累积公式是：

pixel = ( projected_v0 + projected_ddx * offset_x + projected_ddy * offset_y ) / pixel_w

插值算法的选择

何咏（Graphixer）大神之前也写了一个渲染器，比我快许多（大概是4-6倍），用的是UV；

gameKnife大神两个礼拜写成的渲染器，速度比我用五年写出来的半成品要快7倍，用的办法是Lerp到Scanline上，再Lerp到像素。

SALVIA采用了累积法：

struct transformed_vertex { float4 attributes[MAX_ATTRIBUTE_COUNT]; };

transformed_vertex projected_corner;

// 计算角点的坐标
projected_scanline_start = projected_v0 + projected_ddx * offset_x + projected_ddy * offset_y; 

// 像素的透视修正值
float inv_w; 

// 最终输出的4x4个像素
pixel_input px_in[4][4];

for(int i = 0; i < 4; ++i)
{
  projected_pixel = projected_scanline_start;
  for(int j = 0; j < 4; ++j)
  {
      // 透视空间转换到线性空间并输出到px_in中
      px_in[i][j] = unproject( projected_pixel );
     // 累加x方向上的值（透视空间）
      projected_pixel += projected_ddx;
  }
  // 累加y方向上的值（透视空间）
  projected_scanline_start += projected_ddy;
}

本轮优化之前对插值算法的优化尝试

注意那个MAX_ATTRIBUTE_COUNT，这个值通常比较大，在v1231中，它是32。

不过，显然我们不需要对所有的属性进行计算。敏敏在这里运用了一点小小的技巧进行了优化：只计算必要的属性。同时，为了减少分支的使用，他甚至用

template <int N>
void sub_n(out, v0, v1 )
{
    for(int i = 0; i < N; ++i) {
       out.attributes[i] = v0.attributes[i] – v1.attributes[i];
    }
}

并配合函数指针的方法，以促使编译器展开循环，减少分支。

不过从实际生成的汇编来看，这个部分并没有被展开到期望的形式，可能是编译器认为x86的Branch Predication性能已经足够高了吧。

这个“优化”在v1231中就已经具备了。

首轮优化：unproject函数，operator += 与 operator =

第一个Profiling是用BenchmarkPartOfSponza和Sponza跑的；unproject，operator +=和operator = 加在一起大约占用了15-20%的时间。单独的unproject

最初的实现就是普通的标量。既不要求对齐，也没有使用SIMD。

所以当然会以为用了SIMD后，优化效果会很好。于是在v1232中，中间顶点和像素输入的分配都以16字节对齐，unproj，+=和=也都使用了SSE进行了重写。

从跑分来看，PartOfSponza性能提升了20%。但是，在测试ComplexMesh和Sponza时，并未发现帧率有显著提升。

其实在进行优化之前，何咏就告诫过我，因为现代CPU的一些技术，比方说超标量啥的，四个数据宽度的SSE和标量运算相比，就只有50%的性能差距。

并且这些函数的指令已经极为简单，瓶颈也很明确的落在计算指令上。例如Unproject优化后，性能焦点就落在_mm_mul_ps上（3.7%），几无优化余地。

二轮优化：插值算法的调整

在进行第二轮优化之前同样运行了一次Profiling。因为对PartOfSponza性能基本满意，因此这次优化的目标主要在Sponza上。

排名前几位的小函数，分别是sub_n，unproj，+= 和tex2D。对sub_n例行优化后，性能没什么变化。当然，这也是意料之中的事情了。

因此，第二轮优化便着重考虑在插值算法本身上。

在优化之前，我尝试对代码成本做个粗略的评估：

在现有算法下，假设每个像素有N个需要插值的属性，则平均每个像素有

（corner）3N/16个读 + 2N/16个乘法 + 2N/16个加法 + N/16个写

（x：+=）2N个读 + N个加法 + N个写

（x：*）  N个读 + 1个标量除法 + N个乘法 + N个写

（y：+=）2N/4个读 + N/4个加法 + N/4个写

（y：=） N/4个读 + N/4个写

因为每个都是函数指针，所以这些都是优化不掉的。因此首先将一些操作合并了一下，比如把+= 和*合并以减少一下读写操作。只可惜效果也不是很明显。

第二刀就砍到算法的头上。因为累加本身是为了减少乘法的运用，但是这可能带来了多余的存取开销。

因此直接套用公式：

pixel = ( projected_v0 + projected_ddx * offset_x + projected_ddy * offset_y ) / pixel_w

这样就有：3N读，2N乘法，2N加法，N个乘法和N个写（假设寄存器够用的话）。不算Corner的计算成本，这样比较一下，就等于是3N/4个读，N/2+N个写，N/4个加法来换取2N个乘法的时间。本来以为作为IO瓶颈的应用，这样可以提高一些性能。不过结果证实这个买卖实在是很不划算，整体性能不增反减。

三轮优化：减少内存占用，柳暗花明

虽然所有的操作只针对已使用的属性，但是空间上还是浪费了许多。

考虑到内存占用较大也会导致一些性能损失，于是将MAX_ATTRIBUTE_COUNT从32下调到了8。

结果令人大跌眼镜。性能瞬间提升了20-30%之多。

再加上SSE也不知道为什么开始发力了，使用上之后性能大约又有了10-15%的提升。

我猜测可能是因为换页频率下降，以及Cache的命中率提升。不过手上没有VTune这种工具，所以也不太好验证。

四轮优化：精度敏感性下降的额外红利

在这轮优化之后，PartOfSponza出现了精度问题。因为视锥体的上下左右四个面都没有Clip，所以可能会出现非常大的三角形。这样累积的时候一旦起始点选择的不好，就会出现比较大的误差。在之前版本中，使用/fp: precise来减少这一问题出现的机会。但是因为使用了SSE，也让这个问题再难解决。因此我选用了一些办法，来改善精度问题。在大问题都修正以后，换用/fp: fast来编译整个SALVIA，最终也获得了0-10%左右的性能收益。

结论

对于运算和IO都密集的程序来说，优化真可能是牵一发而动全身的问题。比如在我的例子中，所有猜测是性能瓶颈的地方，都没有得到预想中的改善。

倒是在内存占用这个地方无心插柳，才得以柳暗花明，而且还让别的优化方案体现了价值。所以如果你不像qiaojie大牛那样对x86了如指掌，还是要习惯于从多方面猜测，例如内存占用，对齐或紧缩，计算强度，访存密度，并行度等多个角度进行设想并用实践去验证。尽管可能会遇到很多挫折，但是，只要是直觉上有优化的余地，一般都可以找到合适的方案。

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

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函数：

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月：黎明前的黑暗

Shader的文法

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中的规则

Rule ::= Token SubRule0 [OptionalSubRule1]

在Cpp中最简单可以表示成

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月份，我费了点功夫，把V2的Spirit折腾到SALVIA的前端上。Parser也有所变化：前一版的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。

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

这一切原因，都是因为Boost.Spirit对于Parser Tree，是用了完全静态的分析树结构。每条规则的返回值都会是完全不同的类型。这直接导致类型数量极为庞大，代码膨胀的厉害。

于是11年的寒假我花了5天的时间重新山寨了一个文法分析器的产生器，并做到DSL几乎完全和Spirit一致。只不过Parser Tree不再是静态类型；模板的用量也减轻了很多。

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都做了Unit test：Parser，Semantic，CodeGen和JIT。

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

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

三周后，发布了第一个有Vertex Shader的Demo

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

Pixel Shader：需求与设计

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

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

struct pixel_input
{
  float data;
};

pixel_input pixel_block[4];

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

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很复杂呢，比方说下面这样：

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的情况下，我就彻底没有办法了。这个问题一直延续到现在，如果我不动手去Debug LLVM的话，就只能等他们什么时候想起来修复这个问题了。

SIMD执行模型下分支的处理

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

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

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

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经常变化，包括Stage的接口。这时候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. 2012年1月及以后：现在与未来

新特性，新思考

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

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

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

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

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

出错处理和错误提示，是编译器开发过程中重要而繁琐的部分。

诊断信息的格式因编译器和IDE而不同。

SALVIA将采用Visual Studio的格式，即 文件 + 行列 + 类别（等级） + 编号 + 出错信息。例如：

d:\programming\salvia\sasl\test\cgllvm_test\function_test_basic.cpp(16): error C2061: syntax error : identifier 'te'

因此在出错分析的时候，也需要提供如上的一些信息。

2. 诊断信息Diagnostic Item

在以上信息中，文件名和行列号可以在词法分析的时候获得，我们将它作为属性附加在Token中。

类别和编号，对于同一个编译器而言是相对固定的，尽管我们可以用ID来表示，但是它并不直观，编译器检查也较少。与参数匹配时，也比较容易出错。

SASL中的诊断信息将每个错误都使用一个类型来表达：

class diagnostic_item
{
};


class unrecognized_identifier: public diagnostic_item
{
public:
    unrecognized_identifier& token( token_t tok );
    
private:
    static int level;
    static int id;
    static std::string description_template;
    
private:
    std::string ident;
    size_t      row, col;
    // Other properties
};

这样的好处在于可以用Combinator的风格来撰写错误信息。例如这样：

diagnostic_chat.report<unrecognized_identifier>().token( err_tok );

并且由于编译器的保证也比较不容易写错。

但是这种写法也有一个很关键的问题，需要为每个错误都定义一个类，工作量很大。SASL对这一问题的处理，自然是传统的大杀器：运用脚本进行生成。

Clang使用了它内置的代码生成工具td来完成生成的工作。

3. 诊断信息管理器Diagnostic Chat

Chat是诊断信息的管理工具。它主要要完成以下需求：添加和清理诊断信息，以及在诊断信息的添加清理时提供回调操作。

后者是很有用的，尤其是在调试编译器的时候。你得分清楚究竟是真正的程序错误呢，还是编译器出了错。

Diagnostic Chat的原型如下：

class diagnostic_chat
{
public:
    template <typename T> T& report();
    void add_report_diagnostic_handler( DiagnosticHandlerT handler );
};

同时，我们也将Treat Warning As Error，Error Count，Disable Warning，Stop compiling when error occurs等状态和功能所需要的支持添加到Chat中。

所以，Chat除了提供管理之外，也要具有相应的诊断信息的统计功能。

4. 过滤器Diagnostic Filter

Filter主要配合IDE使用，从Chat中取出符合条件的诊断信息。Error Count和Disable Warnings等功能也可以通过它来完成。

5. Formatter

Formatter用于将DiagnosticItems中的信息转换成人可读的字符串。目前SASL只打算支持Visual Studio的格式，但是相信支持GCC的格式以更好的和Eclipse等第三方IDE集成并不困难。

在C#里面，我们可以用“We need ‘{0}’ not ‘{1}’.”这样的方式来分离description template并延期的产生格式化的字符串。但是在C++中，这种做法并不容易。C的sprintf很难具有延期、渐增的绑定模板的特定，对自定义类型的字符串化的支持也不足，类型安全也比较差；而stream的话，也会面临着将好端端的格式化字符串割裂的问题。SASL使用了boost.format，从一定程度上搞定了这两个问题，从而像C#一样，使用格式化字符串的功能。

这是自2010年8月份以来， SALVIA Milestone 1.0之后最重要的发布！

0.3开始，SALVIA正式支持了Pixel Shader。

自2008年中开始的Shader设计与实现工作基本完成。

未来一年内，SALVIA的工作将集中以下几点：

1. 在Shader编译器的完善上，比如友善的语法和语义错误提示。
2. 提升与管线的集成度，进而充分提升性能。
3. 编译器和编译器生成代码的优化，提高Shader的编译速度和运行速度。
4. 新的图形特性，如各向异性过滤等。

随着SALVIA整体的逐渐成熟，我们也希望有其他的朋友能来参与和支持这个项目，一同进步。

如果您希望参与到这个项目中，请mail联系我：wuye9036 __at__ gmail dota com.

项目主页： http://code.google.com/p/softart/

更新列表如下：

0.2.2 - 0.2.5 (Feb 24, 2012)

• 版本名称发生变化，从原先的Milestone X fix Y的命名方式正式更新为与主版本相同的版本号序列。
• 取消了对DirectX的强制依赖。
• 添加了对Visual C++ Express的支持
• Pixel Shader 进一步增强：

• 对Rasterizer进行了进一步的优化
• 修正了以下问题：

项目主页：http://code.google.com/p/softart/

新的编译步骤如下：

1. 下载最新的CMake并安装。

2. 下载Python 2.7并安装。

3. 下载boost 1.44或更新的版本，解压到某个目录下。

4. Clone或下载SALVIA代码包，执行根目录下的build_all.py文件。第一次运行的时候会生成一个project.py，编辑project.py设置相应属性，包括boost代码目录，编译器，configuration等。

5. 再次运行build_all.py，编译程序。

• 参数为结构体的
• 返回值为结构体

• 返回值为单个浮点
• 返回值为向量（_m128 / <4 x float>）
• 参数为向量（_m128 / <4xfloat>）

• 使用Module::getOrInsertFunction( intrinsic_name, intrinsic_function_type )。它会自动识别intrinsic的名称并创建function或者是intrinsic。指令需要使用全名。例如 llvm.x86.sse.sqrt.ps.
• 或者使用Ilvm::Intrinsic::getDeclaration( id ) 来创建。这个id可以在intrinsics.gen中找到。

本文将讨论如何在LLVM上生成正确的内存对齐和调用协议的代码。

在这里为了方便和标准起见，假定应用LLVM的语言的Extending和Embedding的对象都是C。

调用协议

先来讨论调用协议。调用协议用于保证调用方和被调用方在二进制/汇编一级上是相容的。合适的调用协议可以帮助构造出以下代码：

// Callee Signature of LLVM code
void __cdecl foo( int a, float b, float4 c);

// C caller
typedef void (__cdecl* fn_ptr)(int, float, float4)
fn_ptr p = static_cast<fn_ptr>( get_jit_function("foo") );
p(1, 1.0, vec);

一般来说调用协议包括参数传递和返回值传递和堆栈平衡三个部分。在x86平台上的C/C++编译器中常见的调用协议有cdecl, fastcall和stdcall。具体的协议内容请参见MSDN。

在C++中还有一类特殊的调用协议thiscall，用于调用对象的成员函数。但是这一类调用协议不同的平台，不同的编译器实现皆有不同，既无书面标准，也无事实标准，再加上virtual call等复杂的情况存在，并不适合用于做跨语言的调用。

对于x64平台而言，在windows下和linux下分别有两种调用协议。

先来看x86。由于x86在cdecl和fastcall上是有着跨平台的标准的，因此LLVM对它的支持是比较完整的。程序只要在创建Function的时候指定Call Convention即可。

但是对于x64，LLVM的支持便不是那么完善。以windows为例，windows的x64调用协议要求以rcx，rdx，r8，r9寄存器传递前四个不大于64bit的参数，其余参数放在栈上。如果参数大于64bit，则要求传递它的指针。浮点使用xmm0-3来传递。但是对于LLVM而言，一旦参数大于64bit，它便会将整个对象而不是指针压到栈上传递。因此在遇到x64时，需要小心处理API部分的调用协议。

在这里，我们需要将所有超过64bit的结构体处理成指针（或者拷贝后处理成指针）传递。

同时，LLVM提供了readonly和byval两个参数属性（Attribute）来确保参数的值语义。前者意味着传入的指针所指向的值是不被修改的，（类似于T const*），而后者会对传入的指针做一份内存拷贝，确保写值不被传递出函数（类似于值拷贝）。这样，LLVM生成的函数便可以MSVC生成的x64代码正确调用了。

内存对齐

与移动平台的体系结构相比，x86对内存对齐的条件算是相当宽松的了。大部分的指令对内存对齐基本上是没有特殊要求的。只有一些SIMD的指令会对内存对齐有所限定，例如movaps。

为了方便后端生成SIMD代码，LLVM提供了vector类型，例如vector<float, 1>。在代码生成的时候，vector会编译成最有可能的SIMD类型。因此在x86平台上，vector<float, 1-4>都被处理成类似于__m128的类型，更长的vector则被拆分成多个__m128类型。

这实际上意味着，所有的vector都应该遵循16Bytes对齐的原则。

考虑到我们的需求，类似于struct{ float[3]; }这样的结构，如果能表示为vector<float, 3>显然适合一些数学运算，例如shuffle，逐元素的add，sub，mul，同时LLVM指令的选择也更加灵活。但是显然，这个结构体有两个条件是不满足的：16字节对齐和16字节的大小（movups和movaps都是一次取16字节）。这会造成边界下读写的内存越界。因此非常可惜，这些数据必须表示为struct{ float ,float, float }。在读取的时候，也会生成正确的指令：movss。

那么，对于一般的非对齐的vec4应用vector<float,4>行不行呢？

答案是，很困难。对于LLVM而言，他们在设计的时候就没有过多的考虑vector在非对齐时候的应用。尽管load和store都能够指定alignment以生成非对齐的内存操作（例如movups）并且确实会起效，但是由于代码优化、临时存取等特性的存在，导致一些非load和store的内存操作仍然是要求对齐的（例如生成了addaps xmm, [addr]）。此时仍然有可能为非对齐的数据生成了内存对齐的指令。

因此综合权衡，SASL在API界面上使用了struct{float x,y,z,w;} 这样的ABI来表示数据，在代码生成时，会首先将struct的数据转换成vector，然后再执行其它的操作，兼顾ABI与SIMD；同时对于Intrinsic，由于并不暴露给Host，所以它们仍然尽可能使用Vector，便于LLVM进行优化。

• http://code.google.com/p/softart

源码下载地址：

• Zip格式：https://bitbucket.org/wuye9036/salvia/get/tip.tar.bz2
• Mercurial地址1：https://bitbucket.org/wuye9036/salvia
• Mercurial地址2：https://code.google.com/p/softart/

• Milestone 1.1 Fix 1

• 添加了了新的Demo：Sponza
• Wavefront Obj添加了32位索引的支持。
• 修复了 Wavefront Obj 错误的顶点共享的问题。
• 修复了 Mip-map 计算错误的问题。
• 修复了对多边形错误剔除的问题。

• 下载地址

Demo截图：