assembly - 如何从汇编生成控制流图？

Question

对于上下文，我正在尝试编写一个从 AVM2(ActionScript 虚拟机 2)字节码/程序集到高级 ActionScript 3 代码的反编译器。据我所知，这需要我分析程序集并从中生成结果控制流图，以便推断出循环和条件分支 (if/else) 等结构。

给定一些 assembly ，例如:

0         getlocal0         
1         pushscope         
2         findpropstrict    {, private, }::trace
4         pushstring        "one"
6         callproperty      {, private, }::trace (1)
9         pop               
10        pushbyte          5
12        pushbyte          3
14        ifngt             L1

18        findpropstrict    {, private, }::trace
20        pushstring        "two"
22        callproperty      {, private, }::trace (1)
25        pop               

L1: 
26        findpropstrict    {, private, }::trace
28        pushstring        "three"
30        callproperty      {, private, }::trace (1)
33        coerce_a          
34        setlocal1         
35        getlocal1         
36        returnvalue       
37        kill              1

生成控制流图的算法是什么？

Answer 1

我想通了。基本上，保留一个标签列表(在我的例子中是数组中指令的索引)。标签之间的每个指令列表都是 block (它们是图中的顶点)。在每个分支之后标记指令(以便分支是 block 的最后一条指令，这样您就可以弄清楚它是哪种边缘。或者，您可以在分支类型上标记边缘。)，以及目标每个分支。

有了标签后，只需将它们分成 block 即可。我遍历标签中的每个排序索引，如果最后一个 block 的最后一条指令是一个分支，我从它添加一条边到目标。如果不是，我会从它添加一条边到当前 block (作为 fall-through 节点)。