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]这个数据已经被覆盖了。

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