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函數：
float shading_pixel( ... ): COLOR0
{
float x;
// Expression for calculating x
return ddx(x);
}
在Pixel Shader運行的時候，它一次性執行2x2的一個小塊，所有的指令對于整個塊內都是同步執行的。遇到ddx(x)后，四個像素都正好執行到這里，然后把x方向上的相鄰兩個像素的局部變量x求個差，就可以得出ddx了。
這個要求在C++中很難實現。
- 不好讓C++的四個函數都在同一個地方Join；
- 我不好去獲得相鄰函數的棧上的值。
其實如果要較真，當然還是有辦法的：
- 對于Join問題，起碼有兩種方案：
- 自己搞一個Fiber Manager，直接控制代碼的棧的Switch。每個pixel都有一個Fiber，到了DDX/DDY就換到下一個Fiber執行，直到所有的Fiber都執行完畢后，計算ddx，寫入棧變量，再繼續執行；
- 直接用線程，Join，計算，然后繼續執行。
- 對于棧變量的地址問題，也有辦法：
但是這些實現，要么因為切換上下文而變得奇慢無比；要么就是完全沒有平臺移植性。想來想去，還是要讓代碼按照硬件的方式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滿足了以下幾個需求：
- Shader要返回一個函數；
- 這個函數是可重入的（因為要并發）；
- 數據能正確的從Pipeline傳入到Shader的函數中，也能正確的返回；
- 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指令。
那么這個時候，有兩個需求是要滿足的：
- 同樣的struct member一定要是鄰接在一起。
- 得根據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模型來說，動態分支有三種處理辦法。
- 跳轉執行。像CUDA 2.0以上那樣的指令集具備有一定的跳轉執行能力。編譯器可以把SIMD拆開，按照標量執行。每個都執行完了后，再繼續按照SIMD執行其他的代碼。
- 條件執行。這也是圖形硬件上最常見的執行模式。通過一個位，就可以決定GPU中的執行單元是否執行一段代碼。舉個不準確的例子，如果是個4并發的執行器，那么四個并發執行器的執行條件可以設置為1100，這樣就只有前兩個單元的數據執行，后兩個不執行了。
- 寫掩碼。這個辦法是沒有辦法的辦法。它的基本理念就是：只要不寫到內存中的執行結果，就可以認為它沒執行過。但是寫掩碼總是浪費了指令。不過好歹它還是避免了跳轉的。所以對于早期的ARM這樣沒有分支預測的精簡體系來說，一旦有分支執行起來就是死翹翹。所以它有類似于Select-Store這樣的指令，盡可能的避免分支的出現。
對于SAVLIA來說，跳轉執行和寫掩碼是兩個可能的選擇。因為寫掩碼的代碼生成起來更加輕松一些，所以目前的SALVIA的實現是寫掩碼的。在x86/x64平臺上，對于AVX以上的指令，還可以用blend。但是對于其他指令而言，基本上只能是通過跳轉實現寫掩碼。所以這部分的開銷其實很大。等到造出了自己的SSA之后，再來考慮分支執行的事情吧。
對于寫掩碼的掩碼要怎么計算，一開始我心里挺沒譜的。特別是有了，Continue和Break之后，情況就會變得復雜起來。一開始我沒法確信自己的方案是正確的。后來看了MESA的Gallinum以后，看見了Continue Mask和Break Mask兩個變量，瞬間就明白了。
具體怎么思考的不多說了，這里寫下幾個結論：
- 語言不能有Goto（有Goto會讓代碼變得非常復雜，甚至不可解）；
- 所需要的掩碼的數量會隨著循環的嵌套層數的增加而增加；
- 每個循環最多有三個掩碼：Break，Continue和Mask；
- 程序是固定的話，掩碼的數量就一定是個常量。（要不然硬件就沒法做了）
- 寫掩碼的位數只和執行單元的數量有關，和嵌套深度無關。
坂道の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經驗，有以下幾點感受：
- 測試一定要選擇盡可能低的面，這樣牽涉的代碼就盡可能少；
- 在縱向上，粒度要細。除了單個API的Test，還要有適度的交叉，不過太綜合的測試，請讓集成測試用例來完成；
- 要重視代碼覆蓋率；
- 測試面向的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的調試符號，這些一定會給我帶來許多絞盡腦汁想不明白的問題，但同時我也會學習到、實踐到許多新的知識。
我相信時間會教給我們一切。