> For the complete documentation index, see [llms.txt](https://tommy-3.gitbook.io/my_reverse_book/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tommy-3.gitbook.io/my_reverse_book/my_reverse_notes/4.-biao-da-shi-chuan-bo-yu-gong-gong-zi-biao-da-shi-xiao-chu-cse.md).

# 4.表达式传播与公共子表达式消除（CSE）

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

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

## 编译器：公共子表达式消除（CSE）

考虑到下列代码：

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

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

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

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

示例1：

```c
#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

对于编译器来说

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

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

```c
tmp = x + y
z = tmp * tmp
```

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

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

```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 （表达式传播）**

也就是将

```c
tmp = x + y
z = tmp * tmp
```

反向转换为

```c
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）技术起效，可能也会影响其它的部分。

例如以下的伪代码

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

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

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

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

<figure><img src="/files/nAHxdzaUjYziFT7v4Vkc" alt=""><figcaption></figcaption></figure>

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

```c
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]**&#x8FD9;个数据已经被覆盖了。

<figure><img src="/files/VZp4eF3wQexF9in2lB6Z" alt=""><figcaption></figcaption></figure>

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