在各种编程语言里,逻辑运算符都是要短路的。
以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的情况
最初的中间代码是这样的,可以看到每个cmp或teq运算之后都紧跟着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之前的图