Hongzheng Chen Blog
程序综合与编译
Feb 1st, 2020 0程序综合(synthesis)和程序编译(compilation)常常会被混淆。我们大多数人熟知的是编译，比如将C++代码编译为x86汇编；而在FPGA中我们更多会采用综合一词，比如高层次综合、逻辑综合、物理综合等等。两者工作似乎都是将一种语言翻译为另一种语言，但事实上仔细分析一下还是有很多区别。
粗略地来讲，编译器仅仅做了一个翻译的功能，即高级语言只是描述了要做什么(what)任务（传统的C/C++/Java等编程语言大多是命令式编程）；而综合器做的事情则更多，它还需要去探索怎么(how)去执行这个任务，涉及到程序的改写。
区别两者一个很重要的特征在于有无搜索(search)的过程。编译器通常是将一个预定义的调度(schedule)进行转换，而综合器则是根据程序的描述找到一个最优的调度来满足需求。不过事实上，很多现代的编译器都已经具备有自动优化(autotuning)的功能，比如TVM，因此编译与综合的界限其实在逐渐模糊。
另外，程序综合也很像机器学习。仔细思考一下现在的机器学习，其实也是一个程序到程序的映射，或者说我们一开始写的就是元程序(metaprogram)。大多机器学习算法都包括训练(training)和推断(inference)两个过程，训练实际上就是读入源程序然后进行优化/综合的过程，把其中未确定的参数给确定下来，进而得到最终的程序/模型；而推断则是利用训练好的确定的程序运行得到结果。
如上图，红叉是传统编译确定性的写法，你写什么就得到什么程序；而红叉之外的是搜索空间，满足你的spec可能有非常多程序，都落在灰圈中，而要在灰圈的程序中找到最好的一个，这是综合。
那么到底什么是程序综合？
Program Synthes is correspond to a class of techniques that are able to generate a program from a collection of artifacts that establish semantic and syntactic requirements for the generated code.1
用更加通俗易懂的话来说，我现在要盖房子，综合器只告诉你一个设计图纸/目标，至于怎么盖你自己想；而编译器会十分细致入微，告诉你第一步先造地基，第二步往上盖，第三步怎样怎样。
现在的程序综合研究主要关注以下几个方面：
- 从高层描述中自动生成算法
- 将综合技术应用在广泛的问题上面，比如Excel的自动填充[FlashFill]、代码自动打分等
- 逆向工程，低层实现转为高层等价表示，如将Java转为SQL
而高层次综合(HLS)同样是给出是什么(what)，然后综合器告知应该怎么做。HLS和传统编译的区别可见该文。
像TVM、Halide、GraphIt、Taichi这些新生代的DSL，他们正是将综合的概念融入编译，分离出算法和调度(schedule)。 算法对应的即传统的编译，而调度正是所谓的spec，是可以探索的，是可以交由综合器自由发挥的。
这也解释了为什么现在编译和综合的概念越来越模糊，因为编译更多融入了综合的概念，而综合也在往编译方面发展。 我们现在已经是软件2.0时代，而有种说法是我们已经进入到编译3.0时代2，如今的编译器加入了搜索的元素（启发式/机器学习都可以），使得编译出来的程序性能更高，也更大程度解放程序员疯狂调参的过程。
总的来说，“条条大路通罗马”，综合器告诉你最好的一条，编译器只让你走其中一条。
参考资料
-
Armando Solar-Lezama (MIT), Introduction to Program Synthesis - Lecture 1, 2018 ↩
-
编译1.0实现汇编到高级编程语言的抽象，这是我们现在本科编译原理教的东西，语法分析、词法分析、代码生成等等都是上个世纪编译器刚出来时的产物。编译2.0分离出编译器的前中后三个部分，诞生出了LLVM，前端接各种语言，有成熟的parser；中端做平台无关优化；后端做平台特定优化和codegen。衍生出的高级编译原理、静态程序分析等都是这个世纪初的成果。 ↩