首先，挑这个头图没有什么特殊的意义，是今天我自己去 riding 了😂
然后，阐述一下此文产生的动机吧。
我几乎想用“遗恨”这个词来表达此刻的心情，可以说本次比赛，我们队伍就是输在了优化上。而我个人认为，我们队伍此次在中端优化上完成得不够好，一方面是因为人手不足，在工作量暴大的基础上我实在是分身乏术，没能完成足够的优化，另一方面就是调研不够，写优化时东一榔头西一棒槌，过于依赖学长们的经验，没有从理论的角度研究好各种类型优化的性质、类型、搭配顺序，在最少的时间内做最多最有效的优化。比如：我们完全可以用处理效果平平的全局变量局部化和局部数组全局化的时间，去完成一个效果极佳的归纳变量强度削弱，或者把本次比赛我最大的遗憾——别名分析（我屡次提到的别名分析其实也包括了大家总是说的数组 SSA）给写完。光从别人的优化经验上看，又缺乏理论基础，很难尖锐有力地挑选出效率高的优化。
因而，本文就是我关于优化趟的一些调研结论。在这里放上两张总结得还行的图（来自《深入理解 java 虚拟机》一书），以激发读者阅读兴趣
（你在说什么）
在另一篇博文“中端优化概述”中，我大概阐述了中端优化技术的几个主要分类，但事实上，中端优化需要按照一定的顺序执行，甚至需要执行多次，才能完成比较好的优化效果，这就涉及到一个叫“优化趟”，或者说“优化遍”的概念，英文名称是 Pass。
从名称可以看出，这应当是一个完整而具有流水性质的流程，并且可以被重复执行。它与整个中端优化的基本结构大致如下图：
事实上，理论上需要重复执行的部分主要发生在标量优化。但由于数据流分析的过程往往具有分析性质，在标量优化对中间代码进行过重写之后，代码的数据依赖关系很有可能会发生变化，为保证正确性需要再次进行分析，所以在实际场景中，是整个珊瑚红色圆框内的流程在反复执行，因此我才将其也划入了优化趟的范畴。下面就从数据流分析和标量优化两部分进行讲解。
数据流分析
数据流分析的意义是分析信息（把常量化简与传播在这里进行也未尝不可），收集定位优化时机所需要的信息，推断值在程序运行时的流动过程，并保证优化的安全性与正确性。
这步分析能为我们带来很多宝贵的东西，比如重要的静态单赋值形式、基本块的前驱后继关系、循环信息、支配树……等等，缺少了它们，我们无法确定在程序的何处修改代码能够提高性能，也无法证明在这些位置对代码进行重写与修改是安全的。
通常来说，数据流分析有以下几个流程：
- 构造静态单赋值形式（对应优化：Mem2Reg）
- 全程序分析
- 计算支配性关系（对应优化：分析并构造当前函数的支配树 / 循环信息）
- 讨论图的可归约性（Optional）
- 完成常量传播，尽可能用常量代替指令中的变量（Optional）
- 完成常量化简，合并程序中的所有常数计算指令（Optional）
为程序提供静态分析的可能是很重要的。静态单赋值的具体意义可以通过搜索本博的历史博文得到，总之，在简单的情况下，静态分析可以生成精确的结果，此时编译器能够确切地知道在代码执行时到底将发生什么，如果编译器能够推导出精确信息，那么它可以将表达式或者函数的运行时求值操作替换为对结果立即数的加载操作，另一方面，也规避了具有歧义的内存引用。
一般来说，我们专注于使用迭代算法来分析数据流，构造简单的静态单赋值形式和流图结构。这里我就不对具体的算法进行展开了，如果你想要回到开头的那两张图，那么这一部分大致可以对应 编译器策略 那一块儿。
标量优化
这一部分是笔者的工作重点，所以可能会多费些笔墨。此处涉及的中端优化通过应用重写代码的变换来改进生成代码的质量，由于是专注于单个控制线程下的代码优化，因此被称为标量优化。它包括很多与机器无关的变换，可以解决编译后代码中的各种低效性，往往涉及消除冗余、代码变换、调度指令这种操作。
动机
进行过数据流分析后，优化编译器应当使用分析的结果将代码重写为一种更高效或者更有效的形式，这种改进可以用很多方法度量，包括运行时间减少、代码长度变短、执行期间处理器能耗变低等等，优化器应当是健壮的，能够使得很大的输入程序集得到类似的性能，且输入的小改动不会导致性能出现较大的变动。
优化器主要通过两个机制实现这些目标：
- 消除由编程语言的抽象引入的不必要开销
- 将结果程序的需求与目标机上可用的软硬件资源相匹配
广义上，变换可以分为与机器无关的和与机器相关的两类，后者的意义是依赖于目标处理器相关知识的变换。例如，冗余消除被认为是机器无关的，而利用向量处理器上的“分散 - 聚集”硬件实现字符串复制操作的优化是与机器相关的。在这里，我们主要讨论与机器无关的优化。
优化趟概述
正如文章开头的图绘制的那样，大多数优化器都被构建成为一系列的处理趟，每趟以 IR 形式的代码作为其输入，都生成 IR 代码的一个重写后的版本作为其输出，这种结构将实现划分为若干个小片段，从而避免了大型单块程序引起的部分复杂性，简化了开发、测试和维护的过程。多次运行某些趟往往是有利可图的。
优化序列的构造
对特定变换及应用这些变换的次序的选择，对优化器的有效性有重大影响，不同的变换之间还可能发生相互作用，因此优化序列的不同构建方法可能增强或者削弱优化的效果，即使优化文件的种类一模一样。经典的优化编译器会提供 -O, -O1, -O2 等优化级别，它们其实就对应着不同的优化变换序列。
优化文献描述了数百种用于改进 IR 程序的不同算法，编译器编写者必须从这些变换中选择一个合适的子集来实现并应用到代码上。鉴于论文的作者往往都主张自己的变换，因此编译器编写者需要领会自己的编译器转换的应用程序中会出现哪些低效性，以及这些低效性对应用程序有何影响。给定一组需要解决的具体缺陷，编译器编写者接下来才可以去选择处理这些缺陷的具体变换，并缜密地按照优先次序列出它们。
独立于具体的优化场景，有一些基础优化是几乎所有编译器都需要完成的，在这里，给出它们的优化趟序列如下，经过实践的验证，这个基础优化趟已经非常成熟：
消除无用和不可达代码
编译器可以发现无用或者不可达的操作，消除它们，因而产生更快速、更短的代码。这里涉及的优化是（过程间 & 过程内）死代码删除和分支优化。
移动代码
将指令移动到更合适的位置上，使之用更少的时间执行，却能产生同样的效果。再运行一遍优化趟的话，甚至还能帮助缩短代码的长度。这里涉及的优化是代码提升。
特化计算
围绕某个操作的上下文来特化其操作，比如将乘法重写为移位。这样可以减小通用代码序列的代价。
消除冗余计算
证明某个值已经计算过，重用早先的值，通常重用的代价远远小于重新计算。显然，值编号技术可以捕获这种效应。
为其他变换制造时机
用特定的方式重写代码，为其他变换揭示新的时机。这里的经典例子是函数内联替换和循环展开。
这一组优化序列涵盖了编译器能够达到的大多数与机器无关的效应。事实上，许多变换可以提供多达一类的效果，比如既消除冗余计算又特化计算的值编号技术。
选择合适的优化序列
任何给定变换的有效性都取决于几种因素，由此导致了优化序列问题的出现，同时，我们也能在其中一窥优化序列的选择标准。
-
该变换针对的时机在代码中出现了吗？
如果没有，那么变换是无法改进代码的。
-
此前的某个变换是否隐藏或掩盖了当前变换所需的时机？
比如，LVN 中对代数恒等式的优化可能可以将乘法指令转换成一个移位操作，将一个可交换操作替换为一个更快速的非可交换操作。此后，任何需要交换性以实现其改进的变换，可能都会因此前应用的 LVN 而损失某些优化时机，此时，孰先孰后就不言而喻了。
-
是否有其他变换已经消除了当前变换所针对的低效性？
不同变换的效果可能是彼此重叠且各具特异性的，比如 GVN 实现了全局常量传播的效果，而循环展开实现了类似超级块复制的效果。编译器编写者可能需要加入两个变换，以实现二者不重叠的那部分效果。
变换之间的相互作用使得我们难以预测应用任何单一变换或变换序列带来的改进，因此，潜在优化序列的空间是很大的。比如，如果编译器从 15 种变换组成的变换池种选择一个长度为 10 的变换序列，则可能产生 种可能的序列，编译器很难全方位地探索如此巨大的变换序列空间。因而，编译器在搜索好的（生成的结果在最好的 5% 结果以内的序列）变换序列时，将采用启发式技术对搜索空间的较小部分进行抽样。通常，这些技术分为 3 类：
- 改编遗传算法，使之充当某种形式的智能搜索；
- 随机化搜索算法；
- 统计机器学习技术。
因此，总结而言，困扰了我们许久的编译器优化序列选择问题实际上是编译技术界的一大挑战。
这里，给出一个激进优化编译器的优化序列示意图，以供参考：
五项基本优化涉及的具体算法解析就不在本文中叙述了，视情况看看要不要再开博文吧，我感觉像是消除不可用代码之类的优化比较基础，中文互联网上也已经有很多资源（嚼着人家上世纪六七十年代的东西，哈哈），不太想写了，只不过优化技术的个中乐趣，仍然广袤无垠，或许后面会写一些综述性质的论文笔记，要是脑子够用，也写写算法。
调研途中，笔者感觉编译优化真的是一片充满了浪漫色彩的领域，国峻写过，“在开放的生活环境中，想象和创作是不断处处在发生的，它的传递与生息能够展现出人的另一个模样，而这过程中所使人意识到的对抗与协调，也许正是人容身的亭子。”其感略同。
参考：
- Engineer a Compiler, Second Edition
豆瓣评论：“Keith Cooper人非常好，书也写得不错，酷爱穿花衬衫。”
- MUCHNICK SS. Advanced compiler design and implementation[M]. San Francisco, Calif: Morgan Kaufmann Publishers, 1997.