# 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="https://2050902342-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FFIjush9EwySt5d8KqOoI%2Fuploads%2Ffg3PxLPR1RndrxTdJo2n%2Fimage.png?alt=media&#x26;token=9473a6c8-3ccd-47dc-a66e-917e86684dd3" 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="https://2050902342-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FFIjush9EwySt5d8KqOoI%2Fuploads%2FUOYkHsJJlTzRNoh20seo%2Fimage.png?alt=media&#x26;token=5eb66de4-e4b5-434d-8c0f-9631b29c4ad8" alt=""><figcaption></figcaption></figure>

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET 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?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.