18 即时编译器的中间表达形式
在上一章中，我利用了程序控制流图以及伪代码，来展示即时编译器中基于profile的优化。不过，这并非实际的优化过程。
1. 中间表达形式（IR）
在编译原理课程中，我们通常将编译器分为前端和后端。其中，前端会对所输入的程序进行词法分析、语法分析、语义分析，然后生成中间表达形式，也就是IR（Intermediate Representation ）。后端会对IR进行优化，然后生成目标代码。
如果不考虑解释执行的话，从Java源代码到最终的机器码实际上经过了两轮编译：Java编译器将Java源代码编译成Java字节码，而即时编译器则将Java字节码编译成机器码。
对于即时编译器来说，所输入的Java字节码剥离了很多高级的Java语法，而且其采用的基于栈的计算模型非常容易建模。因此，即时编译器并不需要重新进行词法分析、语法分析以及语义分析，而是直接将Java字节码作为一种IR。
不过，Java字节码本身并不适合直接作为可供优化的IR。这是因为现代编译器一般采用静态单赋值（Static Single Assignment，SSA）IR。这种IR的特点是每个变量只能被赋值一次，而且只有当变量被赋值之后才能使用。
举个例子（来源），上面这段代码所对应的SSA形式伪代码是下面这段：
在源代码中，我们可以轻易地发现第一个对y的赋值是冗余的，但是编译器不能。传统的编译器需要借助数据流分析（具体的优化叫reaching definition），从后至前依次确认哪些变量的值被覆盖（kill）掉。
不过，如果借助了SSA IR，编译器则可以通过查找赋值了但是没有使用的变量，来识别冗余赋值。
除此之外，SSA IR对其他优化方式也有很大的帮助，例如常量折叠（constant folding）、常量传播（constant propagation）、强度削减（strength reduction）以及死代码删除（dead code elimination）等。
示例：
x1=4*1024经过常量折叠后变为x1=4096
x1=4; y1=x1经过常量传播后变为x1=4; y1=4
y1=x1*3经过强度削减后变为y1=(x1<<1)+x1
if(2>1){y1=1;}else{y2=1;}经过死代码删除后变为y1=1
部分同学可能会手动进行上述优化，以期望能够达到更高的运行效率。实际上，对于这些简单的优化，编译器会代为执行，以便程序员专注于代码的可读性。
SSA IR会带来一个问题，那便是不同执行路径可能会对同一变量设置不同的值。例如下面这段代码if语句的两个分支中，变量y分别被赋值为0或1，并且在接下来的代码中读取y的值。此时，根据不同的执行路径，所读取到的值也很有可能不同。
为了解决这个问题，我们需要引入一个Phi函数的概念，能够根据不同的执行路径选择不同的值。于是，上面这段代码便可以转换为下面这段SSA伪代码。这里的Phi函数将根据前面两个分支分别选择y1、y2的值，并赋值给y3。
总之，即时编译器会将Java字节码转换成SSA IR。更确切的说，是一张包含控制流和数据流的IR图，每个字节码对应其中的若干个节点（注意，有些字节码并没有对应的IR节点）。然后，即时编译器在IR图上面进行优化。
我们可以将每一种优化看成一个独立的图算法，它接收一个IR图，并输出经过转换后的IR图。整个编译器优化过程便是一个个优化串联起来的。
2. Sea-of-nodes
HotSpot里的C2采用的是一种名为Sea-of-Nodes的SSA IR。它的最大特点，便是去除了变量的概念，直接采用变量所指向的值，来进行运算。
在上面这段SSA伪代码中，我们使用了多个变量名x1、x2、y1和y2。这在Sea-of-Nodes将不复存在。
取而代之的则是对应的值，比如说Phi(y1, y2)变成Phi(0, 1)，后者本身也是一个值，被其他IR节点所依赖。正因如此，常量传播在Sea-of-Nodes中变成了一个no-op。
Graal的IR同样也是Sea-of-Nodes类型的，并且可以认为是C2 IR的精简版本。由于Graal的IR系统更加容易理解，而且工具支持相对来说也比较全、比较新，所以下面我将围绕着Graal的IR系统来讲解。
尽管IR系统不同，C2和Graal所实现的优化大同小异。对于那小部分不同的地方，它们也在不停地相互“借鉴”。所以你无须担心不通用的问题。
为了方便你理解今天的内容，我将利用IR可视化工具Ideal Graph Visualizer（IGV），来展示具体的IR图。（这里Ideal是C2中IR的名字。）
public static int foo(int count) {
int sum = 0;
for (int i = 0; i < count; i++) {
sum += i;
}
return sum;
}
上面这段代码所对应的IR图如下所示：
IR图
这里面，0号Start节点是方法入口，21号Return节点是方法出口。红色加粗线条为控制流，蓝色线条为数据流，而其他颜色的线条则是特殊的控制流或数据流。被控制流边所连接的是固定节点，其他的皆属于浮动节点。若干个顺序执行的节点将被包含在同一个基本块之中，如图中的B0、B1等。
基本块直接的控制流关系
基本块是仅有一个入口和一个出口的指令序列（IR节点序列）。一个基本块的出口可以和若干个基本块的入口相连接，反之亦然。
在我们的例子中，B0和B2的出口与B1的入口连接，代表在执行完B0或B2后可以跳转至B1，并继续执行B1中的内容。而B1的出口则与B2和B3的入口连接。
可以看到，上面的IR图已经没有sum或者i这样的变量名了，取而代之的是一个个的值，例如源程序中的i<count被转换为10号<节点，其接收两个值，分别为代表i的8号Phi节点，以及代表输入第0个参数的1号P(0)节点。
关于8号Phi节点，前面讲过，它将根据不同的执行路径选择不同的值。如果是从5号End节点进入的，则选择常量0；如果是从20号LoopEnd节点跳转进入的，则选择19号+节点。
你可以自己分析一下代表sum的7号Phi节点，根据不同的执行路径都选择了哪些值。
浮动节点的位置并不固定。在编译过程中，编译器需要（多次）计算浮动节点具体的排布位置。这个过程我们称之为节点调度（node scheduling）。
节点调度是根据节点之间的依赖关系来进行的。举个例子，在前面的IR图中，10号<节点是16号if节点用来判断是否跳转的条件，因此它需要排布在16号if节点（注意这是一个固定节点）之前。同时它又依赖于8号Phi节点的值以及1号P(0)节点的值，因此它需要排布在这两个节点之后。
需要注意的是，C2没有固定节点这一概念，所有的IR节点都是浮动节点。它将根据各个基本块头尾之间的控制依赖，以及数据依赖和内存依赖，来进行节点调度。
这里的内存依赖是什么一个概念呢？假设一段程序往内存中存储了一个值，而后又读取同一内存，那么显然程序希望读取到的是所存储的值。即时编译器不能任意调度对同一内存地址的读写，因为它们之间存在依赖关系。
C2的做法便是将这种时序上的先后记录为内存依赖，并让节点调度算法在进行调度时考虑这些内存依赖关系。Graal则将内存读写转换成固定节点。由于固定节点存在先后关系，因此无须额外记录内存依赖。
3. Global Value Numbering
下面介绍一种因Sea-of-Nodes而变得非常容易的优化技术 —— Global Value Numbering（GVN）。
GVN是一种发现并消除等价计算的优化技术。举例来说，如果一段程序中出现了多次操作数相同的乘法，那么即时编译器可以将这些乘法并为一个，从而降低输出机器码的大小。如果这些乘法出现在同一执行路径上，那么GVN还将省下冗余的乘法操作。
在Sea-of-Nodes中，由于只存在值的概念，因此GVN算法将非常简单：如果一个浮动节点本身不存在内存副作用（由于GVN可能影响节点调度，如果有内存副作用的话，那么将引发一些源代码中不可能出现的情况） ，那么即时编译器只需判断该浮动节点是否与已存在的浮动节点的类型相同，所输入的IR节点是否一致，便可以将这两个浮动节点归并成一个。
public static int foo(int a, int b) {
int sum = a * b;
if (a > 0) {
sum += a * b;
}
if (b > 0) {
sum += a * b;
}
return sum;
}
我们来看一个实际的案例。在上面这段代码中，如果a和b都大于0，那么我们需要做三次乘法。通过GVN之后，我们只会在B0中做一次乘法，并且在接下来的代码中直接使用乘法的结果，也就是4号*节点所代表的值。
我们可以将GVN理解为在IR图上的公共子表达式消除（Common Subexpression Elimination，CSE）。
这两者的区别在于，GVN直接比较值的相同与否，而CSE则是借助词法分析器来判断两个表达式相同与否。因此，在不少情况下，CSE还需借助常量传播来达到消除的效果。
总结与实践
今天我介绍了即时编译器的内部构造。
即时编译器将所输入的Java字节码转换成SSA IR，以便更好地进行优化。
具体来说，C2和Graal采用的是一种名为Sea-of-Nodes的IR，其特点用IR节点来代表程序中的值，并且将源程序中基于变量的计算转换为基于值的计算。
此外，我还介绍了C2和Graal的IR的可视化工具IGV，以及基于IR的优化GVN。
今天的实践环节，你可以尝试使用IGV来查看上一篇实践环节中的代码的具体编译过程。
你可以通过该页面下载当前版本的IGV。解压后，可运行脚本位于bin/idealgraphvisualizer中。IGV启动完成后，你可以通过下述指令将IR图打印至IGV中。（需附带Graal编译器的Java 10或以上版本。）
// java -XX:+UnlockExperimentalVMOptions -XX:+UseJVMCICompiler -XX:CompileCommand='dontinline,CompilationTest::hash' -Dgraal.Dump=:3 -Dgraal.MethodFilter='CompilationTest.hash' -Dgraal.OptDeoptimizationGrouping=false CompilationTest
public class CompilationTest {
public static int hash(Object input) {
if (input instanceof Exception) {
return System.identityHashCode(input);
} else {
return input.hashCode();
}
}
public static void main(String[] args) throws InterruptedException {
for (int i = 0; i < 500000; i++) {
hash(i);
}
Thread.sleep(2000);
}
}
- ext4 👍（7） 💬（1）
除了你上面提到的内存依赖，我看到C2的ideal graph里面还有一种依赖叫做I/O dependency，这个在Graal的graph里似乎也没有了。可以解释一下C2的这个I/O dependency是做什么的，以及Graal是如何替代这种依赖的表示的么？
2018-08-31 - Shine 👍（4） 💬（1）
IR图有点看不懂。基本块是根据什么原则划分的？ 有些块有start,begin, end等等，有些块却没有？ 为什么GVN代码中，都是判断a,b是否大于0，图中B3来了一个Merge节点?
2018-09-03 - Ken张云忠 👍（3） 💬（1）
郑老师,本节中第一张IR图和下面的Control Flow图是使用http://ssw.jku.at/General/Staff/TW/igv.html的IdealGraphVisualizer查看的吧. 这个工具使用jdk7启动起来后,但是在执行时必须要使用debug版的jdk7才能执行参数-XX:PrintIdealGraphLevel=2 -XX:PrintIdealGraphFile=ideal.xml,一直困扰在获取不到debug版的jdk7,下载openjdk7自己编译过程中遇到了太多问题,尤其是build-debug/hotspot中太多代码编译不过去的问题. 老师是怎么样一步步得到debug版的jdk7的?
2020-01-17 - likun 👍（0） 💬（1）
你好 我这边找不到bebug版本的jdk10，好像无法查看ir图
2018-10-22 - 夜行观星 👍（17） 💬（6）
看懂这篇文章，已经是一年之后，时间真快
2019-11-19 - 编程的德彪 👍（13） 💬（0）
看不太懂。哈哈哈...可能基础还不到这个水平吧，多看多思考吧。
2018-12-09 - the geek 👍（8） 💬（0）
这篇文章最好还是看懂，后面的方法内联章节会经常出现IR图，我一开始也是看了个大概，看了方法内联后，回来静下心一看，还是比较简单的 主要就是将方法的执行流程转换为IR图。 IR图中一些符号解释(以下是个人简单理解，仅供参考): 1. 常量值:C(0)、C(1)。就是常量值1、2 (类型是i32) 2. 参数值P(0)、P(1)。就是方法参数0和方法参数1=>上面int a,int b 3.Phi(IR节点1,IR节点2,内存类型)。(i32可能是说int 32位 ，方便分配内存吧?个人猜测老师指正)
2020-02-05 - neohope 👍（5） 💬（3）
想问一下老师，idealgraphvisualizer中，有没有办法看到全局的IR图？开启后，好像有很多次优化，每次都只能看到一部分哦。 此外： 1、官网下载的idealgraphvisualizer是2011年版本，没法用，要用直接在github上下载的版本 2、idealgraphvisualizer当前版本，好像只支持JDK1.8？ 3、从graal官网下载的版本只有JDK1.8，下载了也没有用。直接下载Oracle JDK11就可以了 4、最后例子的Demo，JDK11参数要调整一下： java -XX:+UnlockExperimentalVMOptions -XX:+UseJVMCICompiler -XX:CompileCommand=dontinline,"CompilationTest.hash()" -Dgraal.Dump=:3 -Dgraal.OptDeoptimizationGrouping=false CompilationTest 5、前面两个例子，需要用Debug版本的JDK。最后一个不需要。
2019-09-02 - 房艳 👍（4） 💬（0）
看了好几遍，边看边整理思路，看懂个大概。这是我边看边画的知识点： java源代码---java编译器--->java字节码---即时编译器--->机器码 编译器：前端：IR（词法分析、语法分析、语义分析--->生成中间表达形式） 后端：IR优化--->生成目标代码 即时编译器直接将java字节码作为一种IR，即时编译器将java字节码转为SSA IR(IR图) 静态单赋值IR(SSA IR)：每个变量只能被赋值一次，而且只有当变量被赋值之后才能使用 SSA IR存在的问题：不同执行路径会对同一个变量设置不同的值 解决方法：Phi函数-能够根据不同的执行路径选择不同的值 1.C2采用Sea-of-Nodes的SSA IR，去除变量的概念，直接采用变量所指向的值进行运算。 如：Phi(y1,y2) ---> Phi(1,0) C2没有固定节点的概念，所有的IR节点都是浮动节点。将根据各个基本块头尾之间的控制依赖，以及数据依赖和内存依赖，来进行节点调度。 节点调度：在编译过程中，编译器需要（多次）计算浮动节点具体的排布位置。这个过程称为节点调度。 内存依赖：假设一段程序往内存中存储了一个值，而后又读取同一内存，那么显然程序希望读取到的是所存储的值。 即时编译器不能任意调度对同一内存地址的读写，因为它们之间存在依赖关系。 C2的做法便是将这种时序上的先后记录为内存依赖，并让节点调度算法在进行调度时考虑这些内存依赖关系。 2.Graal的IR也是Sea-of-Nodes类型，可理解为是C2 IR的精简版本 Graal将内存读写转换成固定节点。由于固定节点存在先后关系，因此无需额外记录内存依赖。 IR的可视化工具 IGV：被控制流边所连接的是固定节点，其他的皆属于浮动节点。 IR图是竖着看，然后遇到if分支就会有两个流程（满足与不满足），hpi函数里面用了节点上的编号，我理解是这样。 GVN是一种发现并消除等价计算的优化技术。例如如果一段程序中出现多次相同的乘法，那么即时编译器可以将这些乘法合并为一个。 在 Sea-of-Nodes 中，由于只存在值的概念，因此 GVN 算法将非常简单： 如果一个浮动节点本身不存在内存副作用（由于 GVN 可能影响节点调度，如果有内存副作用的话，那么将引发一些源代码中不可能出现的情况） ， 那么即时编译器只需判断该浮动节点是否与已存在的浮动节点的类型相同，所输入的 IR 节点是否一致，便可以将这两个浮动节点归并成一个。 有个问题：内存副作用是什么意思？有点不理解，麻烦帮我解答一下。
2021-01-19 - 鱼肚 👍（3） 💬（0）
原本里的 IGV 用不了，用这个 https://github.com/oracle/graal/releases/tag/idealgraphvisualizer-543
2019-09-03 - Ken张云忠 👍（1） 💬（0）
用debug版jdk8的导出的ideal.xml只能在jdk7旧版的IGV中打开，打开后与老师的IR图差异很大，完全看不出老师所讲的内容。 后来想使用jdk11的graal来查看，按照实践中指令方式来运行，指令并没有把IR图打印至IGV中，不知道怎么来查看IR图了？ public class Practice { public static void main(String[] args){ foo(5); } public static int foo(int count) { int sum = 0; for (int i = 0; i < count; i++) { sum += i; } return sum; } } java -XX:+UnlockExperimentalVMOptions -XX:+UseJVMCICompiler -XX:CompileCommand='dontinline,Practice::hash' -Dgraal.Dump=:3 -Dgraal.MethodFilter='Practice.hash' -Dgraal.OptDeoptimizationGrouping=false Practice
2020-02-16 - 草戊 👍（1） 💬（0）
有好多编译原理的东西
2019-05-21 - 熊能 👍（0） 💬（0）
学习了
2022-11-16 - dominiczhu 👍（0） 💬（0）
pass了，ir图那块解释得实在看不懂，各个节点是什么，每个节点是怎样导致执行顺序流转的，都没有。
2021-08-27 - 丁小明 👍（0） 💬（0）
结合了第三版的java虚拟机，终于懂了！
2020-10-14