如何學寫一個編譯器後端？

不通過llvm做後端（不要告訴我看llvm的源代碼）。想學習一下如寄存器分配演算法等後端的優化技巧，該從哪本書讀起和如何下手？

如果光看演算法，很多書都有，當然書籍只能入門。
鯨書都有，只是內容太舊了。橡書也有，但是太淺了。
所以還是推薦看論文吧。

編譯器後端主要有三塊，指令選擇，指令調度，寄存器分配。
1. 指令選擇有很多論文，有一篇綜述興緻的，summary of instruction selection(https://arxiv.org/ftp/arxiv/papers/1306/1306.4898.pdf) 講述了macro expanding；tree covering 包括LR自動代碼生成器，基於burg系統的重寫系統；dag覆蓋，llvm後端用的就是這種方式，所有的匹配模板都在td文件中定義。

論文：Burg—Fast Optimal Instruction Selection and Tree Parsing

Code_generation_using_tree_matching_and_dynamic_programming,

A Study on Generating an Efficient Bottom-up Tree Rewrite Machine for JBurg（這個是Java版的Burg移植）。

2. 指令調度，這塊一般是集中在基本塊上做局部的調度，基本的思路就是採用拓撲排序。llvm中的實現就是基於dag圖的，將輸入的已經完成指令選擇的selectionDag變換為scheduleDAG，具體看論文深入。

(1). http://www.cl.cam.ac.uk/teaching/2005/OptComp/slides/lecture14.pdf

(2). http://lamp.epfl.ch/files/content/sites/lamp/files/teaching/advanced-compiler-construction/spring-2015/slides/acc15_13_instruction-scheduling.pdf

(3). http://infolab.stanford.edu/~ullman/dragon/w06/lectures/inst-sched.pdf

(4). 這個是LLVM dev的討論帖，如何開始學習指令調度。[llvm-dev] How to get started with instruction scheduling? Advice needed.

3. 寄存器分配，這塊最老的演算法是基於圖著色的，gcc裡面採用了這種方法，llvm1.0中在sparc機器下有個基於圖著色的分配器。目前應用較多的是基於線性掃描的演算法，hotspot c1裡面使用了這個，llvm3.0之前也是這個演算法。還有llvm中的基於貪婪方式的寄存器分配器，這是默認的分配器，還有一個基於bpqp的分配器。詳細了解可以看我的回答，http://www.zhihu.com/question/29355187/answer/99413526，https://zhuanlan.zhihu.com/p/24554029。

我很想知道為什麼不通過LLVM做後端呢？不通過LLVM做後端，我感覺你是在走歧路啊...即使你想學習寄存器分配演算法，通過LLVM做後端，也不會阻止你學啊，比如LLVM本身就有Basic / Greedy / Fast / PBQP幾種寄存器分配演算法，你也可以在這框架下加入自己的寄存器分配演算法，然後比較，這樣可以讓你在學一個的時候就把其它的因素排除掉。

至於書籍，輪子哥說的書挺好的，但是我更推薦你直接看一些大學的課件，比如CMU的Optimization for Modern Architectures，然後再逐步出發。