c++ - 使用 llvm 和局部值编号算法删除冗余表达式

Question

所以我的 C 代码是:

#include <stdio.h>

void main(){
    int a, b,c, d;
    b = 18, c = 112;
    b = a - d;
    d = a - d;
}

其 IR 的一部分是:

  %5 = load i32, i32* %1, align 4
  %6 = load i32, i32* %4, align 4
  %7 = sub nsw i32 %5, %6
  store i32 %7, i32* %2, align 4

  %8 = load i32, i32* %1, align 4
  %9 = load i32, i32* %4, align 4
  %10 = sub nsw i32 %8, %9
  store i32 %10, i32* %4, align 4

我已经实现了 LVN 算法来检测 d = a - d 的冗余表达式。现在为了优化，我需要操纵指令并使其成为 d = b。我不确定如何使用 llvm 执行此操作以及如何操作 IR。

我是 llvm 的新手，所以这可能是一个愚蠢的问题，但我真的很困惑。因为，llvm 在 IR 上工作，我知道当它看到“d = a - d”时，它会首先加载 a 和 d，但是需要更改 IR 中的二进制操作和存储指令，以便 %4 从 % 获取值2.任何人都可以帮助我检查我是否正确理解这一点以及如何操作 IR 来优化代码。

Answer 1

首先，让我们用一个不会调用未定义行为(由于访问未初始化的变量)的示例程序替换您的示例程序，这样 UB 就不会混淆问题:

void f(int a, int b, int c, int d){
    b = a - d;
    d = a - d;
    // Code that uses b and d
}

(我也删除了这两个赋值，因为它们没有任何效果，并且无论如何都会在 mem2reg 之后消失。)

现在实际回答您的问题:大多数优化在 mem2reg 传递之后运行，它尽可能将内存访问转换为寄存器。这很重要，因为与内存位置不同，LLVM 寄存器只能从源中的单个点分配，因此 mem2reg 将代码转换为 SSA 形式，这是许多优化工作所必需的。

如果我们将 mem2reg 应用于示例代码，我们会得到:

define void @f(i32, i32, i32, i32) #0 {
  %5 = sub nsw i32 %0, %3
  %6 = sub nsw i32 %0, %3
  ; Code that uses b and d
}

现在我们将应用您的分析来发现 %6 等同于 %5。有了这些信息，我们可以删除 %6 的定义，并将所有出现的 %6 替换为 %5(请注意，这会更如果 %5 和 %6 位于不同的基本 block 中，其中一个不支配另一个)。为此，您可以使用 uses() 方法找到 %6 的所有用法，该方法会告诉您哪些指令将 %6 作为操作数.然后您可以将该操作数设置为对 %5 的引用。