提升代码中的死存储消除优化

作为Trail of Bits春季实习项目的一部分，我开发了一系列基于数据流的优化技术，用于消除McSema提升程序中模拟机器码寄存器写入的"死"存储。例如，在Apache httpd上应用死存储消除(DSE)优化后，成功移除了117,059次存储操作，相当于Remill寄存器状态结构中50%的存储操作。

提升时发生了什么

Remill/McSema提升代码的核心是State结构体，它模拟机器的寄存器状态。Remill通过LLVM的load/store指令来模拟寄存器的读写操作。例如一个简化版x86架构的State结构：

1

%struct.State = type { i32, i32 }

考虑以下机器码：

1
2

mov eax, ebx
add eax, 10

对应的LLVM IR简化表示中，我们可以发现：

1. 从%ebx_0到%eax_ptr的存储后立即从同一位置加载%eax_0是冗余的
2. 后续的%eax_1存储会使之前的存储变为死存储

构建消除器

槽位划分

DSE过程将State结构划分为"槽位"，每个槽位大致对应一个寄存器。通过计算指针偏移量，我们可以确定每条指令引用的具体槽位。

槽位别名分析

我们使用ForwardAliasVisitor(FAV)来识别指向相同槽位的指令别名。FAV维护两个映射：

1. 访问映射：记录访问状态偏移的指令
2. 偏移映射：跟踪所有可能引用状态结构的指针

消除死指令

1. LiveSetBlockVisitor(LSBV)：通过反向遍历基本块进行活跃变量分析，确定哪些存储可以被安全消除
2. ForwardingBlockVisitor：通过替换存储-加载-使用序列为直接使用原值来优化指令

优化效果验证

在amd64架构的Apache httpd上，我们获得了以下优化结果：

• 候选存储：210,855
• 死存储消除：117,059
• DSE移除指令：273,322
• 转发优化：3,348

未来优化方向

虽然当前DSE已取得显著效果，但仍有改进空间：

1. 处理分支中槽位仅在一侧活跃的情况
2. 更精确地处理函数调用
3. 将活跃区域提升为allocas以利用LLVM的mem2reg优化