4.表达式传播与公共子表达式消除(CSE)

公共子表达式消除 Common Sub-Expression optimization

公共子表达式消除(CSE)是编译器中的一个优化技术,可以通过消除重复的计算来提高代码的性能。它的原理是在表达式中查找重复的计算,并将其替换为一个变量,以避免重复计算的开销。

编译器:公共子表达式消除(CSE)

考虑到下列代码:

a = b * c + g;
d = b * c + e;

可以观察到 b * c 是两项表达式中的公共子表达式。

如果计算这个子表达式并将其计算结果存储起来的开销,低于重复计算这个子表达式的开销,则能够将以上代码转换成以下代码:

   temp = b * c;
   a = temp + g;
   d = temp + e;

示例1:

#include <stdio.h>
int main(){
	long x,y,z;
	scanf("%ld %ld", &x, &y);
	z = (x + y) * (x + y);
	printf("%ld", z);
	return 0;
}

编译 : clang -O3 ./test.c

对于编译器来说

z = (x + y) * (x + y);

这句话经过CAS(公共子表达式消除)后会变成

tmp = x + y
z = tmp * tmp

可以通过查看LLVM翻译后的IR:clang -S -emit-llvm -O3 ./test.c

进行确认。这里我省略了很多生命周期以及函数调用的代码,并与源码的对应关系进行注释

; Function Attrs: nounwind uwtable
define dso_local i32 @main() local_unnamed_addr #0 {
  %1 = alloca i64, align 8
  %2 = alloca i64, align 8
  %3 = bitcast i64* %1 to i8*
  %4 = bitcast i64* %2 to i8*
  %5 = call i32 (i8*, ...) @__isoc99_scanf(...) //scanf("%ld %ld", &x, &y);
  %6 = load i64, i64* %1, align 8, !tbaa !2
  %7 = load i64, i64* %2, align 8, !tbaa !2
  **%8 = add nsw i64 %7, %6  //**tmp = x + y
  **%9 = mul nsw i64 %8, %8  //**z = tmp * tmp
  %10 = call i32 (i8*, ...) @printf(...) // printf("%ld", z);
  ret i32 0 //return 0;
}

反编译器:表达式传播

了解了编译器的这一技术,反编译器只要逆着来就行了,将临时变量的表达式给填充回去

这一技术称为:Expression Propagation (表达式传播)

也就是将

tmp = x + y
z = tmp * tmp

反向转换为

z = (x + y) * (x + y);

这里需要补充一点点的理论知识

对于 x := expression 语句到y点,满足以下两个条件即可执行expression 化简

1、在到达y点时,x的定义有且只有expression一个(类似到达定值分析)

2、在到达y点时,x的expression 不会在任何路径中被重定义(类似变量存活分析,x不能被kill掉)

3、在到达y点后,x不再其它地方使用(x被kill掉了)

那么化简一定是好的吗?不一定,化简后的语句可读性反而会降低,尤其是在大型代码中。

因为Expression Propagation这一技术不仅会对公共子表达式消除(CSE)技术起效,可能也会影响其它的部分。

例如以下的伪代码

int a = test_1()
int b = test_2()
int c = <很长的一个表达式>
if(a && b && c) {
	//some function
}

反编译器可能会将所有的代码全部优化到if语句中去,将所有的中间变量全部消除掉,十分的难懂

if(test_1() && test_2() && <很长的一个表达式>) 

在大型软件中这种情况很常见,尤其是对于结构体的操作,例如下面这段反编译后的IDA代码:

它本身的含义大概长下面这个样子,但是IDA会使用表达式传播技术,将下面这一大串的表达式压成一行:

tmp_edx = v4[84]
tmp_edx = tmp_edx & 0xFE

tmp_ecx = *(v3+36)
tmp_ecx = tmp_ecx & 0xF
tmp_eax = 19283 >> (~ tmp_ecx)

tmp_edx = tmp_edx | tmp_eax 
tmp_edx = tmp_edx + tmp_edx 

这也导致了IDA-debugger调试的时候,如果断点在F5代码里,会出现问题,例如我在IDA中的110行下断点。

但是,其实如果调试时,需要的是**v4[84]**这个数据值;就出问题了,因为,这一行代码是好多个汇编语言压成的;

无法确定这个断点会在哪个汇编执行后;可能v4[84]这个数据已经被覆盖了。

这种情况,建议把断点下在汇编上。这么看,表达式传播这种技术也有很多值得优化的部分。

Last updated