反编译器-如何构造循环

Question

我正在为一种简单的脚本语言编写反编译器。这是我所做的:

基本块

创建了基本块的集合，如下所示:

http://www.backerstreet.com/decompiler/basic_blocks.php

控制流程图，支配树和循环集

由此，我可以创建控制流程图。

http://www.backerstreet.com/decompiler/control_flow_graph.php

通过CFG，我创建了统治者树，这又使我能够在CFG中找到循环集，如下所述:

http://www.backerstreet.com/decompiler/loop_analysis.php

这是一张到目前为止包含我所有数据的图像:

结构循环

我的下一步应该是:

http://www.backerstreet.com/decompiler/creating_statements.php

这就是我提出问题的地方，因为我完全被困住了。在我给定的数据中，结构化循环算法将如何应用？我不明白为什么它会首先尝试将所有内容构造为do while循环-在我的示例中，这意味着块3中的“temp5_14 = temp5_14 + 16”将始终至少执行一次，这不是原始代码的作用完全没有。

它将如何工作，以及将其从do-while转换为while循环的下一个步骤实际上将如何工作？对于以块6结尾的循环3，看起来应该是while(true)-但是当它的头块是if语句时，它将如何与算法一起使用？

TL; DR-有人请举例说明“结构循环”算法实际上是如何工作的。

Answer 1

结构化是反编译器开发中最困难的部分(至少对于高级语言而言)。那是一个相当简单的算法，所以这是一个很好的起点，但是如果您正在使用真正的反编译器，则可能需要使用更好的算法或自行编写算法。

这样一来，您链接到的页面上就已经回答了有关如何使用do-while循环而不是while循环的实际问题的答案。

Every loop can be described with a "do-while" statement.

The "while" loop (pre-tested loop) is a special case of a "do-while" loop, where the bottom condition is always true, and the first statement of the loop is an "if" that jumps out of the loop.

说你有类似的东西

beforeloop
while(foo) {
stmt1
stmt2
}
afterloop

它将被编译成类似以下内容的东西

beforeloop

LOOPBEGIN:
if !foo goto LOOPEND
stmt1
stmt2
goto LOOPBEGIN

LOOPEND:
afterloop

反编译器算法将其转换为

beforeloop
do {
if (!foo) {break}
stmt1
stmt2
} while (true)
afterloop

我希望这一点可以解决。如果没有，请随时询问其他任何问题。

编辑:示例2，显示了如何折叠具有相同入口点的多个循环。

for(;;) { while(foo) {} while(bar){} }

首先， for(;;)与 while(true)等效，因此我将使用以下(伪)代码代替

while(true) { while(foo) {stmt1} while(bar){stmt2} }

令外部循环为循环A，内部循环为循环B和C。这将编译为类似于以下伪汇编的内容。

LOOP_A_BEGIN:
LOOP_B_BEGIN:
if !foo goto LOOP_B_END
stmt1
goto LOOP_B_BEGIN
LOOP_B_END:
LOOP_C_BEGIN:
if !bar goto LOOP_C_END
stmt2
goto LOOP_C_BEGIN
LOOP_C_END:
goto LOOP_A_BEGIN

但是标签当然不会占用任何空间。因此，当相同的标签折叠时，它变成

POINT1:
if !foo goto POINT2
stmt1
goto POINT1
POINT2:
if !bar goto POINT3
stmt2
goto POINT2
POINT3
goto POINT1

现在，有两个带有后沿的点-点1和点2。我们可以为每个节点创建一个循环，为清楚起见，使用带标记的中断。转换并不是那么简单，因为您必须弄乱if语句，但是它仍然很容易。

LOOP1: while(true) {
    IF1: if (!foo) {
        break IF1;
    }
    else {
        stmt1;
        continue LOOP1;
    }

    LOOP2: while(true) {
        if (!bar) {
            break LOOP2;
        }
        else {
            stmt2;
            continue LOOP2;
        }
    }

    continue LOOP1;
}

现在，带有不必要标签的相同代码得以简化

while(true) {
    if (!foo) {
    }
    else {
        stmt1;
        continue;
    }

    while(true) {
        if (!bar) {
            break;
        }
        else {
            stmt2;
        }
    }
}

现在有了if语句简化了

while(true) {
    if (foo) {
        stmt1;
        continue;
    }

    while(true) {
        if (!bar) {
            break;
        }
        stmt2;
    }
}

最后，您可以将 while(true) if(!x)转换应用于内部循环。外部循环无法像这样进行转换，因为它不是合并循环的结果，所以它不是一个简单的while(cond)循环。

while(true) {
    if (foo) {
        stmt1;
        continue;
    }

    while(bar) {
        stmt2;
    }
}

因此，希望如此，这演示了如何始终通过将它们合并到单个循环中来处理具有相同入口点的多个循环的情况，而这可能也必须重新安排一些if语句。