起底方舟编译器的引用计数！
10月8日，是中国国庆假期后的第一个工作日，人们告别假日的休闲，再次返回工作岗位，准备为Q4摩拳擦掌。
这天早上，大洋彼岸传来消息，美国东部时间10月7日，美国商务部产业安全局（BIS）把28家中国实体加入“实体清单”，包括大华科技、海康威视、科大讯飞等8家中国企业。
清单中的实体，须在有许可证的情况下，才可购买美国技术与产品，但美政府有权拒绝许可申请。
故技重施的美国，让历史呈现惊人的相似，2019年5月17日，美国政府正式宣布将华为列入贸易黑名单。
铁血宰相俾斯麦曾说：“ 真理永远只在大炮的射程内。”
科技也是同理，
中国，需要有自主创新和
基础研究的能力！
几个月前，很多人都为华为感到不公，华为却没有过多抱怨，而是继续埋头搞科研。
因为开源，更多方舟编译器的细节，得以公开给开发者们。
比如，方舟编译器引用计数的设计和实现，到底有怎样的技术背景？又有哪些案例？想知道答案的你，快往下看吧~
技术背景
在程序运行过程中，内存是一种有限的资源，通常是在内存被分配的同时配置一个外部引用指向这块内存，当全部外部引用不存在时，表示相应的内存无法访问变成了“垃圾”。
这些“垃圾”需要被释放，否则就会有内存耗尽的风险。为了提高开发效率，现代编程语言大多支持自动内存管理，无需程序员干预。
自动内存管理通常有两种垃圾回收策略：一种是引用追踪垃圾回收（Tracing Garbage Collection，Tracing GC），另一种是基于引用计数（Reference Counting，RC）垃圾回收。
在引用追踪方案中，垃圾回收器集中识别系统中活的内存对象，从活的对象出发能够访问到的对象也是活对象，其它访问不到的内存对象都可以直接回收，这个追踪过程通常依赖整个系统中多线程的间歇同步和停顿，也就是俗称的卡顿。
在引用计数方案中，系统为每一个内存单元维护一个计数器，对每个内存单元的外部引用进行统计，当引用计数为零（即不存在任何外部引用）时即可释放内存单元。
引用计数相比引用追踪能够更及时释放内存空间，使得浮动垃圾更少，也将集中的垃圾回收的时间分散开来避免集中的卡顿。
但是，引用计数的实现需要编译器识别出外部引用对应的引用变量，并对每一次引用变量的赋值和离开作用范围（例如函数返回时或异常退出时）都要插入计数操作，这些计数操作会给程序执行带来很大的额外开销，降低程序的执行效率。
方舟编译器采用引用计数（Reference Counting, RC）对内存进行管理，这是在Java上进行RC的有义尝试。
方舟编译器使用编译优化方法与引用计数方法结合，使得开销降低到可接受的范围内。
RC设计和实现主要包括：对源代码进行变量使用定义分析获取所述源代码的中间表达；对所述中间表达进行分析确定需要进行RC的引用变量和对所述引用变量要进行的RC操作，所述RC操作包括计数加一INCREF操作或计数减一DECREF操作；
对所述RC操作进行消除优化获取优化后的RC操作；在所述中间表达中插入所述优化后的RC操作。具体流程参考图1：
RC插入
对应图1中的步骤101，首先需要对源代码进行变量使用定义分析，建立源代码的中间表达（Intermediate Representation，IR），IR是介于源代码和机器代码之间的一种编译器中间表达方式。
程序变量使用定义（Use-Def）是编译器中用于表达一个变量的定义（即赋值）和使用的对应关系的方式，通过对源代码进行变量使用定义分析可以获取变量的使用和定义之间的精确对应关系。
常用的Use-Def信息构建的实现方式为静态单赋值（Static Single Assignment，SSA），通过对一个变量的不同定义指定不同的版本，从而显式表达了变量定义到变量使用的对应关系。
方舟编译器中端IR基于SSA方式，编译器采用SSA方式对源代码进行转换得到中间表达，最终翻译得到机器可执行的机器代码。
对应图1中的步骤102，基于SSA中间表示，分析确定需要进行RC的引用变量和对引用变量要进行的RC操作。
RC操作包括计数加一（INCREF）操作或计数减一（DECREF）操作。为了实现自动资源管理，编译器可以采用基于RC的垃圾回收，针对某个资源，如果对其增加了一个引用就会对该资源的引用计数加一，如果对其删除了一个引用就会对该资源的引用计数减一。
具体到Java语言，需要进行RC的引用变量为中间表达中定义的指向对象的引用变量，包括本地引用变量、全局变量和栈上变量等。
如果中间表达中有对这类变量的赋值语句，可以认为对某一对象增加了一个引用，因此要对该资源的引用计数加一，即对被赋值的引用变量执行计数加一操作。
同时由于前述引用变量进行了新的赋值，其指向的对象发生了变化，因此需要在赋值前先对该引用变量执行计数减一操作，即对赋值前的引用变量指向的资源删除了一个引用，对其引用计数减一。
另外，为了确保对象的引用计数与实际情况相符，在中间表达的方法退出语句或方法返回语句之前，需要对在本方法中定义的本地引用变量执行计数减一操作，确保在本方法中定义的本地引用变量在退出函数前占用的资源记录被清零。
RC优化
对应图1中的步骤103，编译器识别出中间表达中的冗余的RC操作并进行消除，既可以减少程序执行的额外开销，提高程序的执行效率，也可以缩减代码量，节省存储空间。
方舟编译器在保证多线程安全和异常处理的前提下，以计数减一操作可以延缓，计数加一操作可以提前为原则，对RC操作进行消除优化。
其中，计数减一延缓对引用计数的影响是引用对象可能会延缓释放，计数加一提前只是确保引用对象不会被释放，所以这两个操作在不改变程序行为（例如异常发生的副作用）的前提下是正确安全的。
方舟编译器可以基于对空引用对象的计数减一操作可以删除的原则对RC操作进行消除优化，包括：消除对第一引用变量的计数减一操作，第一引用变量为中间表达中没有被定义过的本地引用变量，第一引用变量也可以被定义为是被赋值的引用变量在初始化阶段的旧值；消除对第二引用变量的计数减一操作，第二引用变量为在中间表达中的函数退出语句或函数返回语句之前没有被赋值过的本地引用变量。
编译器还可以根据变量的使用和定义之间的对应关系对RC操作进行消除优化，包括：消除对第三引用变量的计数加一操作和对第四引用变量的计数减一操作，第三引用变量和第四引用变量为指向同一个资源的引用变量，对第三引用变量的计数加一操作为对第三引用变量赋值之后进行的RC操作，对第四引用变量的计数减一操作包括对第四引用变量赋值之前的RC操作或者在中间表达中的函数退出语句或函数返回语句之前的RC操作。
编译器还可以根据引用变量的取值对RC操作进行消除优化，包括：消除对第一执行路径中的第五引用变量的计数减一操作，第五引用变量为第一执行路径中取值为空的本地引用变量，第一执行路径为中间表达的任一执行路径；
消除对第二执行路径中的第六引用变量的计数加一操作和/或计数减一操作，第六引用变量为在第二执行路径中取值不在资源管理范围内的本地引用变量，第二执行路径为中间表达的任一执行路径。
对应图1中的步骤104，最后编译器将优化后的RC操作实际插入中间表达中，以便机器运行程序的过程中在相应的位置调用RC操作函数，实现对资源的引用计数调整。优化后的RC操作明显少于步骤102中确定出的对引用变量要进行的RC操作。
举例
图2给出了一段源代码的逻辑，其中定义了三个本地引用变量p、q和r，还有一个全局引用变量g，这四个引用变量分别为指向四个内存的指针。
在该源代码中，（2.1）将p赋值给r，（2.2）判断r是否为空，若r为空，则（2.3）给p赋值，（2.4）将p赋值给q，（2.5）返回q；若r不为空，则（2.6）给r赋值，（2.7）将r赋值给g，（2.8）返回0。
图2
图3给出了编译器对上述源代码进行Use-Def信息构建后得到的中间表达的逻辑，（3.1）将p1赋值给r1（p和r第一次出现，且p和r为本地引用变量，版本号为1），（3.2）判断r1是否为空，若r1为空（Y），则（3.3）给p2赋值（由于给p重新定义（即赋值），p的版本号加1变为2）；
（3.4）将p2赋值给q1（q第一次出现，且q为本地引用变量，版本号为1），（3.5）返回q1；若r1不为空（N），则（3.6）给r2赋值（由于给r重新定义（即赋值），r的版本号加1变为2）；
（3.7）将r2赋值给g2（由于给g重新定义（即赋值），且g为全局引用变量在进入该源代码的函数之前已经被定义过，g的版本号加1变为2），（3.8）返回0。
图3
图4给出了编译器在构建SSA得到上述中间表达后，插入RC操作后的逻辑，可以看出程序中增添了大量的计数加一操作（incref）和计数减一操作（decref）。
（4.1）对r0进行decref操作（r的版本号0对应SSA中变量的特殊版本，由于下一步骤4.2要对r赋值，其指向的内存会发生变化，因此要提前对r原本指向的内存的引用计数减一）；
（4.3）对r1进行incref操作（r指向的内存发生变化，需要对r最新指向的内存的引用计数加一）；
（4.4）判断r1是否为空，若r1为空（Y），则（4.5）对p1进行decref操作（由于下一步骤4.6要对p重新赋值，其指向的内存会发生变化，因此要提前对p原本指向的内存的引用计数减一）；
（4.6）给p2赋值，（4.7）对p2进行incref操作（p指向的内存发生变化，需要对p最新指向的内存的引用计数加一）；
（4.8）对q0进行decref操作（q的版本号0对应SSA中变量的特殊版本，由于下一步骤4.9要对q赋值，其指向的内存会发生变化，因此要提前对q原本指向的内存的引用计数减一）；
（4.9）将p2赋值给q1，（4.10）对q1进行incref操作（q指向的内存发生变化，需要对q最新指向的内存的引用计数加一）；
（4.11）对p2进行decref操作（由于执行到了函数返回语句，出了该函数在函数内定义的本地引用变量将失效，需要提前将本函数中定义的本地引用变量指向的内存的引用计数减一）；
（4.12）对r1进行decref操作（由于执行到了函数返回语句，出了该函数在函数内定义的本地引用变量将失效，需要提前将本函数中定义的本地引用变量指向的内存的引用计数减一）；
（4.13）返回q1；若r1不为空（N），则（4.14）对r1进行decref操作（由于下一步骤4.15要对r重新赋值，其指向的内存会发生变化，因此要提前对r原本指向的内存的引用计数减一）；
（4.15）给r2赋值，（4.16）对r2进行incref操作（r指向的内存发生变化，需要对r最新指向的内存的引用计数加一）；
（4.17）对g1进行decref操作（由于下一步骤4.18要对g重新赋值，其指向的内存会发生变化，因此要提前对g原本指向的内存的引用计数减一）；
4.18）将r2赋值给g2，（4.19）对g2进行incref操作（g指向的内存发生变化，需要对g最新指向的内存的引用计数加一）；
（4.20）对p1进行decref操作（由于执行到了函数返回语句，出了该函数在函数内定义的本地引用变量将失效，需要提前将本函数中定义的本地引用变量指向的内存的引用计数减一）；
（4.21）对q0进行decref操作（由于执行到了函数返回语句，出了该函数在函数内定义的本地引用变量将失效，需要提前将本函数中定义的本地引用变量指向的内存的引用计数减一）；
（4.22）对r2进行decref操作（由于执行到了函数返回语句，出了该函数在函数内定义的本地引用变量将失效，需要提前将本函数中定义的本地引用变量指向的内存的引用计数减一），（4.23）返回0。
图4
图5示出了编译器根据Use-Def信息消除一个或多个引用变量的RC操作的逻辑，编译器消除对第一引用变量（r0和r1为空的路径中的q0）的计数减一操作（消除步骤4.1和4.8），该第一引用变量（r0和r1为空的路径中的q0）为中间表达中没有被定义过的本地引用变量；
消除对第二引用变量（r1不为空的路径中的q0）的计数减一操作（消除步骤4.21），该第二引用变量（r1不为空的路径中的q0）为在中间表达的执行路径（r1为空和r1不为空两条路径）中没有被赋值过的本地引用变量。
通过对源代码进行SSA构建能够识别出冗余的RC操作。对于函数内定义的本地引用变量，在第一次对引用变量赋值前，其旧值为空（例如r0和r1为空的路径中的q0），因此不需要对旧值（r0和r1为空的路径中的q0）进行decref操作。
另外如果一个本地引用变量在某一个执行路径中没有被赋值（例如r1不为空的路径中的q0），则在该路径结束（退出作用域或返回变量值）时对该引用变量（r1不为空的路径中的q0）的计数减一操作可以删除。
图5
图6给出了编译器根据Use-Def信息消除一个或多个引用变量的RC操作后的逻辑，（6.1）将p1赋值给r1，（6.2）对r1进行incref操作（r指向的内存发生变化，需要对r最新指向的内存的引用计数加一）；
（6.3）判断r1是否为空，若r1为空（Y），则（6.4）对p1进行decref操作（由于下一步骤6.5要对p重新赋值，其指向的内存会发生变化，因此要提前对p原本指向的内存的引用计数减一）；
（6.5）给p2赋值，（6.6）对p2进行incref操作（p指向的内存发生变化，需要对p最新指向的内存的引用计数加一），（6.7）将p2赋值给q1，（6.8）对q1进行incref操作（q指向的内存发生变化，需要对q最新指向的内存的引用计数加一）；
（6.9）对p2进行decref操作（由于执行到了函数返回语句，出了该函数在函数内定义的本地引用变量将失效，需要提前将本函数中定义的本地引用变量指向的内存的引用计数减一）；
（6.10）对r1进行decref操作（由于执行到了函数返回语句，出了该函数在函数内定义的本地引用变量将失效，需要提前将本函数中定义的本地引用变量指向的内存的引用计数减一）；
（6.11）返回q1；若r1不为空（N），则（6.12）对r1进行decref操作（由于下一步骤6.13要对r重新赋值，其指向的内存会发生变化，因此要提前对r原本指向的内存的引用计数减一）；
（6.13）给r2赋值，（6.14）对r2进行incref操作（r指向的内存发生变化，需要对r最新指向的内存的引用计数加一），（6.15）对g1进行decref操作（由于下一步骤6.16要对g重新赋值，其指向的内存会发生变化，因此要提前对g原本指向的内存的引用计数减一）；
（6.16）将r2赋值给g2，（6.17）对g2进行incref操作（g指向的内存发生变化，需要对g最新指向的内存的引用计数加一）；
（6.18）对p1进行decref操作（由于执行到了函数返回语句，出了该函数在函数内定义的本地引用变量将失效，需要提前将本函数中定义的本地引用变量指向的内存的引用计数减一）；
（6.19）对r2进行decref操作（由于执行到了函数返回语句，出了该函数在函数内定义的本地引用变量将失效，需要提前将本函数中定义的本地引用变量指向的内存的引用计数减一），（6.20）返回0。
图6
图7给出了编译器继续根据Use-Def信息消除一个或多个引用变量的RC操作的逻辑，编译器在r1为空的路径中，消除对第三引用变量（r1为空的路径中的q1）的计数加一操作和对第四引用变量（r1为空的路径中的p2）的计数减一操作。
此处第三引用变量和第四引用变量为指向同一个资源的引用变量（步骤6.7中的赋值让q1和p2指向同一内存，因此前后相继对这两个引用变量分别进行的计数加一和计数减一操作可以相互抵消，编译器可以消除步骤6.8和6.9）。
编译器在r1不为空的路径中，消除对第三引用变量（r1不为空的路径中的g2）的计数加一操作和对第四引用变量（r1不为空的路径中的r2）的计数减一操作。
此处第三引用变量和第四引用变量为指向同一个资源的引用变量（步骤6.16中的赋值让g2和r2指向同一内存，因此前后相继对这两个引用变量分别进行的计数加一和计数减一操作可以相互抵消，编译器可以消除步骤6.17和6.19）。
编译器可以基于SSA构建识别出对同一个内存地址的RC操作，在保证多线程安全和异常处理的前提下，合并消除对同一个内存的计数加一和计数减一操作。
消除的基本原则是：计数加一操作可以提前，计数减一操作可以延缓。例如对q的最后一次赋值（步骤6.7）造成对q1的一次计数加一操作（步骤6.8），而在函数返回前的步骤6.9对p2进行一次计数减一操作，p2和q1指向同一个内存，因此这两个操作可以相互抵消。
但是图7的这种优化的前提是：引用变量从定义到最后一次使用之间不能出现抛出异常的情形；引用变量的最后一次使用必须是在从定义到函数退出的所有可能路径上。
图7
图8给出了编译器继续根据Use-Def信息消除一个或多个引用变量的RC操作后的逻辑，（8.1）将p1赋值给r1，（8.2）对r1进行incref操作（r指向的内存发生变化，需要对r最新指向的内存的引用计数加一）；
（8.3）判断r1是否为空，若r1为空（Y），则（8.4）对p1进行decref操作（由于下一步骤8.5要对p重新赋值，其指向的内存会发生变化，因此要提前对p原本指向的内存的引用计数减一）；
（8.5）给p2赋值，（8.6）对p2进行incref操作（p指向的内存发生变化，需要对p最新指向的内存的引用计数加一），（8.7）将p2赋值给q1，（8.8）对r1进行decref操作（由于执行到了函数返回语句，出了该函数在函数内定义的本地引用变量将失效，需要提前将本函数中定义的本地引用变量指向的内存的引用计数减一）；
（8.9）返回q1；若r1不为空（N），则（8.10）对r1进行decref操作（由于下一步骤8.11要对r重新赋值，其指向的内存会发生变化，因此要提前对r原本指向的内存的引用计数减一）；
（8.11）给r2赋值，（8.12）对r2进行incref操作（r指向的内存发生变化，需要对r最新指向的内存的引用计数加一），（8.13）对g1进行decref操作（由于下一步骤8.14要对g重新赋值，其指向的内存会发生变化，因此要提前对g原本指向的内存的引用计数减一）；
（8.14）将r2赋值给g2，（8.15）对p1进行decref操作（由于执行到了函数返回语句，出了该函数在函数内定义的本地引用变量将失效，需要提前将本函数中定义的本地引用变量指向的内存的引用计数减一），（8.16）返回0。
图8
图9示出了编译器对中间表达的控制流进行分析确定引用变量的取值，根据取值消除不必要的RC操作的逻辑，编译器消除对第五引用变量（r1为空的路径中的p1和r1）的计数减一操作，第五引用变量为在中间表达的执行路径中取值为空的本地引用变量；
消除对第六引用变量的计数加一操作和/或计数减一操作，第六引用变量的取值在中间表达的执行路径中不在资源管理范围内。
编译器基于约束求解和符号执行来删除不必要的incRef和decRef操作，包括：如果确定某个引用变量的取值为空（r1为空的路径中的r1），在对该引用变量赋新值之前，对该变量的decRef操作是不必要的（步骤8.8），可以删除。
而如果将该引用变量赋值给其他引用变量，那么被赋值的引用变量的取值也为空，或者通过赋值关系可以确定其他引用变量的取值为空（r1为空的路径中的p1），在对该引用变量赋新值之前，对该变量的decRef操作也是不必要的（步骤8.4），可以删除。
另外，如果确定某个引用变量的取值范围不在内存管理范围内，例如，将全局引用变量g赋值给本地引用变量r，此时r的取值范围就不在函数的内存管理范围内，因此对r的incRef操作和decRef操作都是不必要的，可以删除。
再来如果某个引用变量的取值大概率为空或者不在内存管理范围内，则分别生成两个判断分支，在各自的分支内依据前述方法消除不必要的RC操作。
在内存管理系统中，通常有一个地址范围可以判断出不同的用途，例如有些地址空间是不需要单独释放的，就不需要进行RC操作，而变量的取值范围就使得这种优化成为可能。
图9
图10给出了编译器对中间表达的控制流进行分析确定引用变量的取值，根据取值消除不必要的RC操作后的逻辑，（10.1）将p1赋值给r1，（10.2）对r1进行incref操作（r指向的内存发生变化，需要对r最新指向的内存的引用计数加一）；
（10.3）判断r1是否为空，若r1为空（Y），则（10.4）给p2赋值，（10.5）对p2进行incref操作（p指向的内存发生变化，需要对p最新指向的内存的引用计数加一）；
（10.6）将p2赋值给q1，（10.7）返回q1；若r1不为空（N），则（10.8）对r1进行decref操作（由于下一步骤10.9要对r重新赋值，其指向的内存会发生变化，因此要提前对r原本指向的内存的引用计数减一）；
（10.9）给r2赋值，（10.10）对r2进行incref操作（r指向的内存发生变化，需要对r最新指向的内存的引用计数加一），（10.11）对g1进行decref操作（由于下一步骤10.12要对g重新赋值，其指向的内存会发生变化，因此要提前对g原本指向的内存的引用计数减一）；
（10.12）将r2赋值给g2，（10.13）对p1进行decref操作（由于执行到了函数返回语句，出了该函数在函数内定义的本地引用变量将失效，需要提前将本函数中定义的本地引用变量指向的内存的引用计数减一）；
（10.14）返回0。图10给出逻辑中的incref和decref的即为编译器最终确定的需要插入的RC操作，编译器将这些RC操作插入中间表达中的相应位置。
可以看出图10与图4相比，步骤从23个减少到了14个，一共优化了9个RC操作，大大加少了程序执行的额外开销，提高程序的执行效率，也缩减了代码量，节省存储空间。
图10
小结
综上，编译器对中间表达中的RC操作的优化主要体现在对代码中没有被使用过、赋值过或定义过的引用变量的RC操作的消除，对函数定义的生命周期确定的常量引用变量（例如类中的static final类型的引用变量）或取值范围不在资源管理范围内的引用变量的RC操作的消除，以及对本地引用变量中指向同一资源的两个引用变量的先后计数加一操作和计数减一操作的相互抵消消除。
需要说明的是，上述用例中提到的全局引用变量只是非本地引用变量的一种，还可以是堆上引用，因为堆上对象的域也可以是一个引用。
例如变量r指向一个对象，对象的域包括r.x和r.y也可以是引用，编译器在对其进行优化时可以类似全局引用变量的方式分别按照上述方法对r.x和r.y进行RC操作的优化。
另外，在多线程的场景下，编译器可以利用跨函数的分析，跟踪对象在创建之后每个引用域的赋值（例如识别创建对象r之后在对r.x赋值之前调用的函数内是否可能更改r.x的值），编译器通过这种跨函数的分析仍然可以对冗余的RC操作进行优化。
文章到这里就结束啦，内容比较“技术”，希望对读文章的你有帮助哈。
点击阅读原文，输入关键词，即可搜索您想要的 CSDN 文章。
标签:
