4.表达式传播与公共子表达式消除(CSE)
公共子表达式消除 Common Sub-Expression optimization
公共子表达式消除(CSE)是编译器中的一个优化技术,可以通过消除重复的计算来提高代码的性能。它的原理是在表达式中查找重复的计算,并将其替换为一个变量,以避免重复计算的开销。
编译器:公共子表达式消除(CSE)
考虑到下列代码:
可以观察到 b * c
是两项表达式中的公共子表达式。
如果计算这个子表达式并将其计算结果存储起来的开销,低于重复计算这个子表达式的开销,则能够将以上代码转换成以下代码:
示例1:
编译 : clang -O3 ./test.c
对于编译器来说
这句话经过CAS(公共子表达式消除)后会变成
可以通过查看LLVM翻译后的IR:clang -S -emit-llvm -O3 ./test.c
进行确认。这里我省略了很多生命周期以及函数调用的代码,并与源码的对应关系进行注释
反编译器:表达式传播
了解了编译器的这一技术,反编译器只要逆着来就行了,将临时变量的表达式给填充回去
这一技术称为:Expression Propagation (表达式传播)
也就是将
反向转换为
这里需要补充一点点的理论知识
对于 x := expression 语句到y点,满足以下两个条件即可执行expression 化简
1、在到达y点时,x的定义有且只有expression一个(类似到达定值分析)
2、在到达y点时,x的expression 不会在任何路径中被重定义(类似变量存活分析,x不能被kill掉)
3、在到达y点后,x不再其它地方使用(x被kill掉了)
那么化简一定是好的吗?不一定,化简后的语句可读性反而会降低,尤其是在大型代码中。
因为Expression Propagation这一技术不仅会对公共子表达式消除(CSE)技术起效,可能也会影响其它的部分。
例如以下的伪代码
反编译器可能会将所有的代码全部优化到if语句中去,将所有的中间变量全部消除掉,十分的难懂
在大型软件中这种情况很常见,尤其是对于结构体的操作,例如下面这段反编译后的IDA代码:
它本身的含义大概长下面这个样子,但是IDA会使用表达式传播技术,将下面这一大串的表达式压成一行:
这也导致了IDA-debugger调试的时候,如果断点在F5代码里,会出现问题,例如我在IDA中的110行下断点。
但是,其实如果调试时,需要的是**v4[84]**这个数据值;就出问题了,因为,这一行代码是好多个汇编语言压成的;
无法确定这个断点会在哪个汇编执行后;可能v4[84]这个数据已经被覆盖了。
这种情况,建议把断点下在汇编上。这么看,表达式传播这种技术也有很多值得优化的部分。
Last updated