当前位置：网站首页>Bi Sheng Compiler Optimization: Lazy Code Motion

Bi Sheng Compiler Optimization: Lazy Code Motion

2022-08-09 21:04:00 【InfoQ】

本文分享自华为云社区《

编译器优化那些事儿（3）：Lazy Code Motion

》,作者：毕昇小助手.

导语

本文中,我们将介绍通过代码移动（插入）的方式消除冗余计算的一个典型方法.

下图给出的简要程序流图中, ①是我们想要优化的代码,②和③是优化后的代码,让我们先思考下面几个问题：

②和③哪个优化效果更好一点？

③ 更好一点,相比 ② 寄存器生存周期更短

（3）这种情况,在 p 点直接插入 t=b+c 会带来安全或性能问题吗？会改变程序的行为吗?

这里不会引入冗余的计算,也没有改变程序行为.但如果 p 是下文介绍的 非预期的 点,我们就需要使用在 临界边上增加合成块的方式避免这个问题了.

能否由编译器来完成一个算法,找到一个通用的、寻找到合适的插入点的方法以消除冗余计算？

这是本文要介绍的内容,我们会在下面算法章节引入四个定义,为程序在各个点上打上标签,通过这些点的集合之间的运算,得到插入点的集合.

0.1 开始之前

介绍算法之前,我们来看三个在写应用层代码时可能会遇到的问题.

（1）我们可以把计算移动到不会重复计算的路径吗？

答案已在图中给出：

左边例子是可以的.这也是下文算法要找的情景.当然实际应用程序中会更复杂,以致我们不能明显看出或不经意间引入冗余的计算,比如《Lazy code motion》
1
 里给出的例子.
中间不可以,因为 b 被重新定义了,所以 a = b + c 不是冗余计算了.
右边不可以,因为 a = b + c 可能一次也没执行,移动到循环前可能会改变程序的行为.

（2）左图到右图的变化有优化效果吗

有的,这也是下面算法中要寻找的情景,左边的路径消除了一次冗余计算,右边为了保持程序正确性插入了一个计算,但并没有引入冗余的计算,所以总体是有优化的.

（3）下图中,能否在 block d 的父项 p 上插入表达式 t=b+c：

不能,因为插入不能改变程序的行为: 这里 t=b+c 可能难以看出问题,但如果表达式换成 b/c (c==0) 或 b^c 就能明显的看到造成了运行问题或性能问题.

解决方法

：可在 临界边(Critical Edge)上增加 合成块(Synthetic Block).

0.2 临界边(Critical Edge)的定义

定义：源基本块有多个后继,目标基本块有多个前驱,连接它们的边就叫临界边(Critical Edge).

临界边如上图红色部分所示.

打破临界边(Critical Edge)的办法：增加合成块(Synthetic Block)

步骤：

为每个指向拥有多个前置的基本块添加一个基本块(不仅仅是在 临界边 上).

为了保持算法简单,将每个语句视为其自己的基本块,并将指令的放置限制在基本块的开头.

上图中我们插入了两个合成块,其中一个是多余的,但不用担心,我们可以在最后消除它.

1、算法

上文中,我们介绍了一个可以放心插入表达式而不会引入安全问题的方法,下面我们将正式介绍导语中提到的算法.

部分冗余消除算法要尽可能延迟计算, 这也是标题中 lazy 的含义.

程序流程图如下：

算法步骤：

首先计算预期表达式（Anticipated）集合

计算将可用的表达式（Will-be-Available）集合

从 AVAIL 和 ANT ,我们为每个表达式计算出最早的插入位置（Earliest）集合,这最大限度地消除了冗余,但可能会增大寄存器生存期

再计算延迟表达式（Postponable）集合

经过上面的计算,引入最新的定义,计算最晚插入的点的集合,With the earliest 相同数量的冗余消除,但缩短了保存表达式值的寄存器的生存期

计算使用表达式（Used）

计算最后的插入位置的集合,替换冗余表达式

我们会以下图为例,说明整个计算过程.根据以往的经验,下面给出的几个公式,必须结合图例去理解,文字无法阐述清楚准确定义.

1.1 预期表达式（预期）

预期：If the final from Start all path calculation（从 In the available 操作数值）,Says expression in a program is expected.

预期表达式（Anticipated）的分析方向为后向（backword）.

图示说明：

1 表示该点是可预期的（Anticipated）,0 表示不是.该算法的方向是后向（backword）的,对应到图中,我们要从 p1 开始判断：对于表达式 b+c 而言,p1 是非预期的,因为到该点为止,没有 b+c 的计算,继续往上,看到了 b+c 的计算,所以 p2 点是可预期的（Anticipated）,这情况一直持续到 p3,到 p4,由于该点看到了 b=1,b 被重新定义了,就是公式里被 Kill 的表达式,所以 p4 点不是可预期的（Anticipated）点.

1.2 将可用的表达式

Will-be-available：If the expression is expected,And then not get along all paths were killed,Says the expression in a program, available.

将可用的表达式（Will-be-Available）的分析方向为前向（forward）.

图中绿色的 1 表示表达式 b+c 该点是将可用的（Will-be-Available）,0 表示不是.该算法方向是前向的,就是分析时,我们从 p4 开始看,根据公式的定义,该点不是可预期的（Anticipated）,No expression calculation b+c,所以该点不是将可用的（Will-be-Available）,p3 虽然是可预期的（预期）,但因为 b=1 ,所以 p3 点对表达式 b+c 来说是 Ekillp ,所以该点仍不是将可用的,p5 点是可预期的（Anticipated）,且该点没有 kill 的操作,该点是将可用的（Will-be-Available）,后续的点类似.

接下来可以通过以下公式进行最早插入点的计算：

根据公式,最早可插入的点的集合是可预期点的（Anticipated）集合（图中红色1部分）减去将可用点的（Will-be-Available）集合,得到图中标记的点.

目前为止我们已经找了一种通用的消除重复计算的方法,就是在上图中标注 The first point the insert expression t=b+c, 然后在后面所有用到 b+c 的地方替换成 t,但这样做会带来一个问题,就是寄存器的生存期会很长.通过下一小节引入的定义,我们可以解决这个寄存器生存期的问题.