技术文章:scf编译器对C语言的逻辑运算符的优化

在各种编程语言里,逻辑运算符都是要短路的。

C语言为例:

if (p && p->x > 0) p->x++;

当指针p是NULL的时候,对成员变量p->x的读写会导致段错误,所以如果&&之前的条件p是NULL就要把后面的p->x跳过去。

这样才能保证代码的正常运行。

如果语言本身不支持逻辑运算符的短路,那么代码就只能这么写了:

if (p) {

if (p->x > 0) p->x++;

}

要多写一个if条件。

逻辑运算符的结果只有0或1两种。

在编程里,逻辑运算符既可以作为if / while / for的条件表达式还可以参与普通运算

if (i > 0 && j > 1 && k > 2) return -1; // 条件表达式

n = i > 0 && j > 1 && k > 2; // 普通运算

在对逻辑运算符进行优化时,必须同时考虑这两种情况

第2种情况下,如果逻辑运算符在计算前2个条件时短路了,必须把计算结果写入最后一个逻辑运算符对应的临时变量

最后一个逻辑运算符的计算结果,才是整个表达式的结果,也是对n赋值的结果。

如果只是在if语句里作为条件表达式,逻辑运算的结果不需要写到临时变量里,直接根据比较结果跳转到对应的分支就可以了。

赋值运算的语法树

第2种情况的语法树如图,参与赋值运算的是第2个&&对应的临时变量。

如果在i > 0 或 j > 1时短路的话,它们设置的是第1个&&的值:编译器在短路跳转时必须给第2个&&设置运算结果,否则之后的n = ...的结果就不对了。

逻辑运算符生成中间代码的时候,实际上并不知道它的结果以后会被怎么使用[捂脸]

从上图中也可以看出=号在更上面(if也是在更上面),实际上,在处理&&运算符时只能看到它的2个条件表达式,看不到更上层的程序逻辑。

if条件的语法树

如果硬要去看更高层的逻辑,就会破坏模块封装性,让遍历语法树生成中间代码的代码变得复杂、难看。

scf框架在这里的处理是:

1,先给所有逻辑运算符的临时变量设置上结果,把进一步的优化放到以后

if的情况

最初的中间代码是这样的,可以看到每个cmpteq运算之后都紧跟着setcc

其中cmp是比较大小,结果可以是>、==、<、>=、<=、!=。

teq是比较是不是0,结果只有2种:== 0,!= 0。

赋值的情况

在有逻辑运算符的情况下,在cmp之后必然跟着teq去判断逻辑结果是不是0。

例如上图中的:

cmp i, 0

setgt v_8_16/&&

jle : teq v_8_16/&&

跳转的目标代码是:

teq v_8_16/&&

setnz v_8_25/&&

jz : assign v_8_6/n; v_8_25/&&

数字表示的是行列号,v_8_16/&&表示第8行第16列的&&运算符对应的临时变量

可以看出,在最初的中间代码里,逻辑运算符并没有“真正的短路”:虽然跳过了第2个比较条件,但并没有跳过逻辑运算。

之所以这样,就是因为(生成中间代码时)没法确定逻辑结果接下来还有没有用。

既然没法确定,编译器就只能先当它有用:代码里遇到这种情况,是一定会做保守处理的。

所以说,不管是程序员还是数学家,一般都是悲观主义者[捂脸]

2,跳转优化时,对这个问题进一步的优化。

如果一个跳转的目标位置是一个绝对跳转,就可以把它优化成跳转到这个绝对跳转的目标位置。

if a jcc's destination is a jmp, then optimize its destination to the jmp's.

这是对跳转的基本优化。

实际上,如果跳转之前对逻辑结果设置了false,而跳转的目标又是检测这个结果的话,那么检测结果也是false[呲牙]这是跳转优化的另一条规则。

所以说,在cmp触发了jle (<=) 的情况下,那么它俩之间的setgt (>) 就肯定是0

进而导致目标位置的teq也是0

进而导致目标位置的setnz也是0

进而导致目标位置的jz被触发,

所以,jle的地址就是jz的地址

但在jle之前要把setnz的目标变量也设置一下,使用的设置指令是setgt:与最初触发跳转的条件一致。

跳转优化之后的中间代码

从上图可以看出,经过跳转优化之后,测试逻辑结果的teq运算消失了,与teq对应的jz跳转也消失了:

逻辑运算符被短路到了接下来的赋值运算。

赋值运算只使用最后一个临时变量v_8_25。

对中间临时变量v_8_16的设置是多余的,接下来的问题是怎么消除它。

如果逻辑运算只是作为if的条件的话,那么最后一个逻辑结果也是不需要的

3,基于活跃变量分析的优化,

算术运算会使用最后一个逻辑结果的临时变量,if条件不使用任何逻辑结果的临时变量,这在临时变量的活跃度上可以体现出来。

不活跃的临时变量DAG上去掉就行了。

最终的优化结果

对n的赋值运算只使用临时变量v_8_25,可以看出它是前面基本块的出口活跃变量,被保留了下来。

如果是if条件,因为所有的临时变量都不活跃,在DAG优化之后就只剩下比较和跳转了[呲牙]

如下图:

if最终的图

上图是if条件的最终的图,下图是跳转优化之后、DAG优化之前的图。

可以看到,所有的setgt都被去掉了。

if之前的图