编译理论基础

C1和C2编译器涉及很多编译原理的概念与常识，下面将简单描述这些基本概念。

中间表示

中间表示（Intermediate Representation，IR）是编译器内部用到的表示源码的数据结构。根据它的表达能力，又可以分为高级中间表示（HIR），中级中间表示（MIR）和低级中间表示（LIR）。正如之前提到的，控制流图也是一种相对高级的中间表示，对它的分析和优化无须考虑机器架构的细节，只需要关注控制流本身的意义。

中间表示是编译的灵魂，作为一架中间桥梁，它消弭了源码缺少细节和机器代码过度细节的沟壑，整个编译流程都是围绕中间表示进行的。HotSpot VM的C1使用HIR和LIR两种中间表示，C2使用理想图。C1和C2的中间表示如图7-3所示。

中间表示决定了编译器优化的实现复杂度和可能性：过度简单的IR导致编译器前端花费大量时间生成中间代码，而复杂的IR导致后端代码生成变得更为困难。中间表示的设计在很大程度上是艺术而不是科学：如果不用现存的中间表示，在新的设计中就会有许多要决定的问题，如果使用现存的中间表示，就需要考虑它对新编译器的各种适应性问题。

基本块与控制流图

基本块（Basic Block）是指只能从第一条指令进入，并从最后一条指令离开的最长的指令序列，即一个基本块的代码中间不能包含跳转指令。基本块的第一条指令只能是方法的入口，或者跳转的目标，该指令又被称为首领（Leader）指令。基本块的这些限制使得它很适合各类编译器分析和编译优化，以代码清单7-4为例：

代码清单7-4 循环的Java示例

public static int sum(){int sum = 0;for(int i = 0; i < 255; i++){sum += i;}return sum;}

将它转换为基本块后如图7-4所示，方框表示基本块，代码清单7-4中有三个跳转的可能：进入循环头，循环条件不满足跳出循环，循环结束跳转到循环头。根据定义，这三个跳转分别发生在B0、B1和B2基本块的结束处。

读者可能已经发现，多个基本块通过边连接，可以组成一个有向图，这个有向图就是控制流图（Control Flow Graph，CFG），用于表示程序在运行时所有可能的程序执行路径。

CFG是控制流分析的核心结构，它包含了很多特性。比如CFG中如果不存在到达某个基本块的路径，那个基本块及其子块构成的子图就是死代码，可以被安全移出；如果从起始基本块出发无法到达退出基本块，就说明方法中存在一个死循环，通过基本块可以很容易地检测到；

如果达到A基本块的所有路径都必须经过B基本块，那么B基本块支配（Dominate）A基本块，A基本块反向支配B基本块，寻找基本块的支配树可以找出CFG中的所有循环，以便后续优化。CFG非常重要，所以现代优化编译器几乎都将代码转化为基本块然后构造CFG作为后端编译优化的第一步。

静态单赋值

假设存在一个赋值操作a=b+c，如果编译器想知道a是否是常量，就必须先知道b和c是否是常量，但编译器不知道任何关于b和c这两个变量的有用信息，所以必须向上查找所有b和c的使用处和定义处，或者将它们缓存起来。另一种更方便的方式是使用静态单赋值（Static SingleAssignment，SSA）形式，关于SSA的最简单的定义是所有变量只定义一次，但是可以多次使用。因为变量只赋值一次，只需要查找一次b和c的定义处即可确认它是否是常量，继而确认c是否是常量。

大多数对同一个变量的多次赋值都可以转换为SSA形式，但的确存在对同一个变量多次赋值且难以用SSA形式表示的情况，为此SSA引入了φ函数（phi function）。如图7-3所示的B1基本块，i8表示代码清单7-1的变量i，它有一次初始赋值0，每次循环结束i会递增。SSA使用i8 =phi(i4,i13)合并这两次赋值，用来表示变量i，这样i8的值会根据程序执行时实际选择的路径等于i4或者i13的其中一个。SSA的每个变量相当于包含了显式的Use-Def信息，该特性使得可轻松地在它上面进行数据流分析。

规范化

规范化（Canonicalize）是指将代码转化为一种简洁、统一的表示，即Canonical Form。假设有一个值是负数，如果一元减法运算符作用于该负数，那么可以消除运算符，只留下原始值，即--x==x，这便是规范化。规范化的另一个示例如代码清单7-5所示，它们都表示一个意思：

代码清单7-5 x+4的四种写法

X + 2 + 24 + X2 + (X + 2)X + 4

规范化会选择一种统一形式如X+4，然后将其他形式都优化为统一形式。规范化的关键不是当前形式变形带来的收益，而是将代码转化为统一形式以便后续可以高效、简单地进行优化，因为后续的优化只需要知道加法的一种统一形式是变量+常量的形式，不需要再考虑常量+变量的情况。

值编号

值编号（Value Numbering）是一种常见的编译优化技术。值编号分为局部值编号（Local Value Numbering，LVN）和全局值编号（GlobalValue Numbering，GVN），前者作用于一个基本块，后者作用于整个函数，可以发现更多的优化机会。

值编号的目的是尽量找出程序中哪些表达式在执行时总是具有相同的值。工作机制是为每个SSA值赋予一个独一无二的编号，在后续分析中，如果发现两个表达式的值编号相同（参数值的编号和操作符都是相同的），则两个表达式应该拥有相同的编号，即两个表达式在执行时会有相同的计算结果。利用这些等价信息，再加上表达式之间的控制流关系，编译器就可以以某种方式（CSE、PRE、CCP等）消除冗余计算，使得程序更加高效地执行。关于局部值编号的例子如图7-5所示。

原始代码b0和c0的计算存在重复。通过值编号为每个值赋予一个独一无二的编号，由于a0、b0、c0的编号都是3，可以使用同一个值代替，所以后续变形中b0和c0复用a0的计算结果。

但在实际应用中，还需要结合实际情况具体分析。假如v1和v2都是读取同一个数组相同索引的元素，它们不一定能拥有相同的值编号，但是如果v1、v2中间的某些操作可以改变v2再次读取的值，那么v2显然不能使用v1代替。

自顶向下重写系统

重写系统表示一系列诸如a->b重写规则的集合，其中a和b表示树模式，a->b还可以关联一个成本Cost。作为重写系统的一种，自底向上重写系统（Button-Up Rewrite System，BURS）是指令选择（InstructionSelection）常用的方法。BURS的目标是给定输入树，在重写系统中找到一系列重写规则，使得输入树能通过系列规则后匹配，同时成本最小。

循环不变代码外提概述

循环不变代码外提（Loop Invariant Code Motion）可以将一个循环中的循环不变代码提出到循环外面。循环不变代码是指每次计算结果都相同的变量/值，将不会改变的代码提出到循环外面可以减少计算次数，尤其是当循环次数较多时，不变代码外提效果显著。代码清单7-6中包含了一个不会随着循环而改变的invariant变量：

代码清单7-6 循环不变代码外提示例

int code_motion(int val){int sum = 0;for(int i=0;i<100;i++){int invariant = 15 + val*val*val; // 循环不变的变量sum += invariant + i;}return sum;}

使用循环不变代码外提优化后，对应的控制流图如图7-6所示。

如图7-6所示，.L3表示循环，当优化后invariant被提出到.L3外面的@3处，无须在循环中反复计算。

本文给大家讲解的内容是深入解析java虚拟机：编译概述，编译理论基础下篇文章给大家讲解的是深入解析java虚拟机：编译概述，调试方法；觉得文章不错的朋友可以转发此文关注小编；感谢大家的支持!