将 CIL 代码反编译成一些高级代码——在数据流分析过程中是否需要引入新变量？

Question

我正在编写一个从 .NET CIL 代码到某种高级语言的编译器。过程类似于反编译。我做了一些控制流分析——检测循环、ifs 等等。在数据流分析方面，我通过模拟一些涉及评估堆栈的指令来完成简单的表达式传播——我将评估堆栈视为隐藏变量，在其上推送更复杂的表达式，并且每当对某个变量有任何赋值指令时（例如 starg 或 stloc) - 我弹出并将传播的表达式从堆栈分配给此变量，并将此表达式转换为高级语言代码中的语句。当然现在它是如此简单以至于它会产生故障。考虑一个用 C# 编写的函数：

int GCD(int n1, int n2)
{
    while(n2 != 0)
    {
        int c = n1 % n2;
        n1 = n2;
        n2 = c;
    }

    return n1;
}

此函数编译为 IL：

.method private hidebysig 
    instance int32 GCD (
        int32 n1,
        int32 n2
    ) cil managed 
{
    .maxstack 8

    IL_0000: br.s IL_000a
        IL_0002: ldarg.1    // load n1 on eval stack
        IL_0003: ldarg.2    // load n2 on eval stack
        IL_0004: rem        // pop n1 and n2 from stack, compute n1 % n2 and push it on stack
        IL_0005: ldarg.2    // load n2 on stack
        IL_0006: starg.s n1 // pop n2 from stack and store it in n1
        IL_0008: starg.s n2 // pop n1 % n2 from stack and store it in n2

        IL_000a: ldarg.2
        IL_000b: brtrue.s IL_0002

    IL_000d: ldarg.1
    IL_000e: ret
}

通过这个简单的传播，我们将 n1 % n2 压入堆栈，然后将 n2 加载到堆栈，然后我们有 starg 指令，因此我们从堆栈弹出表达式并将赋值转换为语句.然后我们再次弹出，并做同样的事情。结果代码如下所示：

GCD(n1, n2) {
    while (n2) { 
        n1 = n2;
        n2 = (n1 % n2); 
    }
    return n1;
}

翻译的代码已经改变了语义并且没有做它应该做的事情，因为 n1 在计算 n1 % n2 之前被改变了。需要在某个地方存储 n1 % n2 的中间结果，例如局部变量，就像在原始 C# 代码中一样。这表明我必须做一些与消除死代码相反的事情，可能被称为“必要的代码引入”。我搜索了一些关于在反编译中引入新变量的方法的资源，但我没有找到任何资源。你有什么想法吗？

Answer 1

您可以尝试从字节码构建 SSA 表单。大多数现代编译器和反编译器都使用 SSA 形式作为中间表示。

在 SSA 形式中，对变量的每次赋值都会产生新变量，因此您将始终能够引用正确的值。

这里是构建 SSA 的算法描述：https://pp.info.uni-karlsruhe.de/uploads/publikationen/braun13cc.pdf

之后您将需要 return 返回非 SSA 表单。算法可以在尚未完成的 SSA 书中找到：http://ssabook.gforge.inria.fr/latest/book.pdf

查找第 3.2 章和第 17 章。

将 CIL 代码反编译成一些高级代码——在数据流分析过程中是否需要引入新变量？

Decompilation of CIL code into some high level code - do I need to introduce new variables during data flow analysis?

cil

decompiling

compilation

compiler-optimization

decompiler